ijcai distinguished 01

Probabilistic Algorithms forMobile Robot Mapping: 

Sebastian Thrun Carnegie Mellon & Stanford Wolfram Burgard University of Freiburg and Dieter Fox University of Washington Probabilistic Algorithms for Mobile Robot Mapping

Slide2: 

Based on the paper A Real-Time Algorithm for Mobile Robot Mapping With Applications to Multi-Robot and 3D Mapping Best paper award at 2000 IEEE International Conference on Robotics and Automation (~1,100 submissions) Sponsored by DARPA (TMR-J.Blitch, MARS-D.Gage, MICA-S.Heise) and NSF (ITR(2), CAREER-E.Glinert, IIS-V.Lumelsky) Other contributors: Yufeng Liu, Rosemary Emery, Deepayan Charkrabarti, Frank Dellaert, Michael Montemerlo, Reid Simmons, Hugh Durrant-Whyte, Somajyoti Majnuder, Nick Roy, Joelle Pineau, …

Museum Tour-Guide Robots: 

Museum Tour-Guide Robots With: Greg Armstrong, Michael Beetz, Maren Benewitz, Wolfram Burgard, Armin Cremers, Frank Dellaert, Dieter Fox, Dirk Haenel, Chuck Rosenberg, Nicholas Roy, Jamie Schulte, Dirk Schulz

The Nursebot Initiative: 

The Nursebot Initiative With: Greg Armstrong, Greg Baltus, Jacqueline Dunbar-Jacob, Jennifer Goetz, Sara Kiesler, Judith Matthews, Colleen McCarthy, Michael Montemerlo, Joelle Pineau, Martha Pollack, Nicholas Roy, Jamie Schulte

Mapping: The Problem: 

Mapping: The Problem Concurrent Mapping and Localization (CML) Simultaneous Localization and Mapping (SLAM)

Mapping: The Problem: 

Mapping: The Problem Continuous variables High-dimensional (eg, 1,000,000+ dimensions) Multiple sources of noise Simulation not acceptable

Milestone Approaches: 

Milestone Approaches Mataric 1990 Kuipers et al 1991 Elfes/Moravec 1986 Lu/Milios/Gutmann 1997

3D Mapping: 

3D Mapping Konolige et al, 2001 Teller et al, 2000 Moravec et al, 2000

Take-Home Message: 

Take-Home Message Mapping is the holy grail in mobile robotics.

Bayes Filters: 

Bayes Filters Special cases: HMMs DBNs POMDPs Kalman filters Condensation ... x = state t = time z = measurement u = control  = constant

Bayes Filters in Localization: 

Bayes Filters in Localization [Simmons/Koenig 95] [Kaelbling et al 96] [Burgard, Fox, et al 96]

Bayes Filters for Mapping: 

Bayes Filters for Mapping s = robot pose m = map t = time  = constant z = measurement u = control

Kalman Filters (SLAM): 

Kalman Filters (SLAM) [Smith, Self, Cheeseman, 1990]

Underwater Mapping with SLAMCourtesy of Hugh Durrant-Whyte, Univ of Sydney: 

Underwater Mapping with SLAM Courtesy of Hugh Durrant-Whyte, Univ of Sydney

Large-Scale SLAM MappingCourtesy of John Leonard, MIT: 

Large-Scale SLAM Mapping Courtesy of John Leonard, MIT

SLAM: Limitations: 

SLAM: Limitations Linear Scaling: O(N4) in number of features in map Can’t solve data association problem

Unknown Data Association: EM: 

Unknown Data Association: EM [Dempster et al, 77] [Thrun et al, 1998] [Shatkay/Kaelbling 1997]

CMU’s Wean Hall (80 x 25 meters): 

CMU’s Wean Hall (80 x 25 meters)

EM Mapping, Example (width 45 m): 

EM Mapping, Example (width 45 m)

EM Mapping: Limitations: 

EM Mapping: Limitations Local Minima Not Real-Time

The Goal: 

The Goal ?

Real-Time Approximation (ICRA paper): 

Real-Time Approximation (ICRA paper)

Incremental ML: Not A Good Idea: 

Incremental ML: Not A Good Idea path robot mismatch

Real-Time Approximation: 

Real-Time Approximation Our ICRA Paper 

Real-Time Approximation: 

Real-Time Approximation Yellow flashes: artificially distorted map (30 deg, 50 cm)

Importance of Posterior Pose Estimate: 

Importance of Posterior Pose Estimate Without pose posterior With pose posterior

Online Mapping with PosteriorCourtesy of Kurt Konolige, SRI, DARPA-TMR: 

Online Mapping with Posterior Courtesy of Kurt Konolige, SRI, DARPA-TMR [Gutmann & Konolige, 00]

Accuracy: “The Tech” Museum, San Jose: 

CAD map Accuracy: “The Tech” Museum, San Jose 2D Map, learned

Multi-Robot Mapping: 

Multi-Robot Mapping Every module maximizes likelihood Pre-aligned scans are passed up in hierarchy map map map Cascaded architecture map map … … Aligned map Pre-aligned scans

Multi-Robot Exploration: 

Multi-Robot Exploration DARPA TMR Maryland 7/00 DARPA TMR Texas 7/99 (July. Texas. No air conditioning. Req to dress up. Rattlesnakes)

3D Volumetric Mapping: 

3D Volumetric Mapping

3D Structure Mapping: 

3D Structure Mapping

3D Texture Mapping: 

3D Texture Mapping

Fine-Grained Structure:Can We Do Better?: 

Fine-Grained Structure: Can We Do Better?

Multi-Planar 3D Mapping: 

Multi-Planar 3D Mapping Idea: Exploit fact that buildings posses many planar surfaces Compact models High Accuracy Objects instead of pixels

3D Multi-Plane Mapping Problem: 

3D Multi-Plane Mapping Problem Entails five problems Generative model with priors: Not all of the world is planar Parameter estimation: Location and angle of planar surfaces unknown Outlier identification: Not all measurements correspond to planar surfaces (other objects, noise) Correspondence: Different measurements correspond to different planar surfaces Model selection: Number of planar surfaces unknown

Expected Log-Likelihood Function: 

Expected Log-Likelihood Function [Liu et al, ICML-01]

EM To The Rescue!: 

EM To The Rescue!

Results: 

Results With EM (95% of data explained by 7 surfaces) Without EM With: Deepayan Chakrabarti, Rosemary Emery, Yufeng Liu, Wolfram Burgard, ICML-01 error

The Obvious Next Step: 

The Obvious Next Step 

Underwater Mapping (with University of Sydney): 

Underwater Mapping (with University of Sydney) With: Hugh Durrant-Whyte, Somajyoti Majunder, Marc de Battista, Steve Scheding

Take-Home Message: 

Take-Home Message Mapping is the holy grail in mobile robotics. Every state-of-the-art mapping algorithm is probabilistic. Sebastian has one cool animation!

Open Problems: 

Open Problems 2D Indoor mapping and exploration 3D mapping (real-time, multi-robot) Object mapping (desks, chairs, doors, …) Outdoors, underwater, planetary Dynamic environments (people, retail stores) Full posterior with data association (real-time, optimal)

Open Problems, con’t: 

Open Problems, con’t Mapping, localization Control/Planning under uncertainty Integration of symbolic making Human robot interaction Literature Pointers: “Robotic Mapping” at www.thrun.org “Probabilistic Robotics” AI Magazine 21(4)

Slide52: 

www.appliedautonomy.com