20 10 0 10 20 30 40 50 60 70 0 20 40 60 80 100 Autonomous Large Scale Mapping John J Leonard MIT In collaboration with H J Feder R Rikoski P Newman M Bosse S J Kim J D Tard s J Neira H Schmidt and S Teller Outline 1A Introduction Autonomous underwater vehicles Concurrent mapping and localization aka SLAM Review of the basic theory Local mapping Large scale mapping Experimental validation Conclusion MIT Dept of Ocean Engineering J Leonard MIT Autonomous Underwater Vehicles AUVs Odyssey II 1995 MIT Dept of Ocean Engineering Odyssey III 2002 J Leonard Under ice mission in the Arctic 1994 Goal Explore and Return Generic Ocean Array Technology Sonar GOATS NATO SACLANT Undersea Research Centre NATO Research Cruise Italy May June 2002 Dual Vehicle Launch Aft bridge Operations Center Remote Controlled Mission Start Remote Controlled Coming Home Current methods for AUV navigation Dead reckoning magnetic compass inertial navigation systems INS Doppler velocity sonar DVS error grows without bound GPS global positioning system available only at the surface impossible or impractical for many missions of interest Acoustic navigation long baseline LBL and ultrashort baseline USBL transponder arrays costly and time consuming to deploy and calibrate MIT Dept of Ocean Engineering J Leonard Outline 1B Introduction Autonomous underwater vehicles Concurrent mapping and localization aka SLAM Review of the basic theory Local mapping Large scale mapping Experimental validation Conclusion MIT Dept of Ocean Engineering J Leonard Concurrent mapping and localization CML Goal enable one or more mobile robots to build a map of a large scale unknown environment while concurrently using that map to navigate Potential benefits achieve AUV navigation with a bounded error in an unknown environment without use of transponders Technical challenges uncertainty noise ambiguity and navigation errors feature detection and modeling data association state estimation the map scaling problem MIT Dept of Ocean Engineering J Leonard Why is CML difficult The key scientific and technological issue in robotics is that of coping with uncertainty In fact the uncertainty is such that one of the most challenging activities for a mobile robot is simply going from point A to point B Tomas Lozano Perez 1990 4MIT February Dept of Ocean Engineering 2000 J Leonard Example consider the challenge of autonomously mapping the buildings of the MIT campus using multiple robots http whereis mit edu Odometry error growth Sonar data in corridor Laser data in corridor Polaroid sonar vs SICK Laser Scanner Typical Polaroid sonar scan Typical SICK Laser Scan Outline 1C Introduction Autonomous underwater vehicles Concurrent mapping and localization aka SLAM Review of the basic theory Local mapping Large scale mapping Experimental validation Conclusion MIT Dept of Ocean Engineering J Leonard Review of the theory underpinning CML CML is a hybrid state estimation problem Assignment search high dimensional nonlinear state estimation and action selection high level control Elements of algorithms AI and control LCS AI LIDS MIT Dept of Ocean Engineering J Leonard Choosing a representation The type of representation we use determines what information is made explicit in the model the purposes for which a model can be used and the efficiency with which those purposes can be accomplished follow directly from the choice of representation K Stewart MIT WHOI PhD Thesis 1988 Choices grid based Moravec 1985 Elfes 1988 feature based Ayache and Faugeras 1989 Moutarlier and Chatila 1989 no representation Brooks 1986 discrete Bayesian Thrun 1998 topological Kuipers 1991 4MIT February Dept of Ocean Engineering 2000 J Leonard Illustration of CML a b c The stochastic mapping process 1 Move 2 Sense 3 Associate measurements with known features 4 Pass data to Kalman filter for new state estimate 5 Find new features from unassociated measurements 6 Initialize new features State estimation formulation of CML MIT Dept of Ocean Engineering J Leonard Full Bayesian Solution to CML MIT Dept of Ocean Engineering J Leonard General Recursive Bayesian Formula for SLAM Thrun IJRR 2001 MIT Dept of Ocean Engineering J Leonard Multiple Target Tracking Multiple Hypothesis Tracking Reid 1979 Chang Chong and Mori 1986 MIT Dept of Ocean Engineering J Leonard Outline 2A Introduction Local mapping Real time feature based CML using Laser Newman et al Sonar mapping using perceptual grouping and deferred feature initialization 3 D mapping using omnidirectional video Large scale mapping Experimental validation Conclusion MIT Dept of Ocean Engineering J Leonard June 2001 Real time CML using Laser MIT Lobby 7 Overhead view of scene MIT Lobby 7 CML software Starting position View from the robot Return to home Final adjustment Movies available on the web at http oe mit edu pnewman click on Explore and Return Real time Concurrent Mapping and Localization MIT s Lobby 7 June 2001 Outline 2B Introduction Local mapping Feature based CML using Laser Sonar mapping using perceptual grouping and deferred feature initialization Rikoski et al 3 D mapping using omnidirectional video Large scale mapping Experimental validation Conclusion MIT Dept of Ocean Engineering J Leonard Mapping Partially Observable Features from Multiple Uncertain Vantage Points Key idea add past vehicle states to the state vector maintain correlations between current and past vehicle states Potential drawback increased computational burden Benefits feature initialization function g can now involve data from multiple vantage points improved data association strategies can be developed composite features and more complex objects can be modeled extends readily to multiple vehicles data referenced to odometry data referenced to CML trajectory measurements associated with points and lines Mapping Partially Observable Features from Multiple Uncertain Vantage Points Mapping Partially Observable Features from Multiple Uncertain Vantage Points Sonar Mapping using RANSAC and Delayed Decision Making Outline 2C Introduction Local mapping Feature based CML using Laser Sonar mapping using perceptual grouping and deferred feature initialization 3 D mapping using omnidirectional video Bosse et al Large scale mapping Experimental validation Conclusion MIT Dept of Ocean Engineering J Leonard SFM from Omnidirectional Video PhD Thesis of Mike Bosse MIT AI Lab Summary of key ideas Estimate vanishing points VPs by finding sets of parallel lines in omni cam