# Probabilistic Robotics Tutorial AAAI-2000

#### 8/3/00

Probabilistic Robotics Tutorial AAAI-2000
Collaborators and Funding
Tutorial Goal
Tutorial Outline
Robotics Yesterday
Robotics Today
Robotics Tomorrow?
Current Trends in Robotics
Robots are Inherently Uncertain
Probabilistic Robotics
Probabilistic Robotics
Pitfalls
Trends in Robotics
Example: Museum Tour-Guides Robots
Rhino (Univ. Bonn + CMU, 1997)
Minerva (CMU + Univ. Bonn, 1998)
“How Intelligent Is Minerva?”
“Is Minerva Alive?"
“Is Minerva Alive?"
Nature of Sensor Data
Technical Challenges
PPT Slide
Tutorial Outline
PPT Slide
Probabilistic Localization
Bayes Filters
Bayes Filters are Familiar to AI!
Markov Assumption
Localization With Bayes Filters
Xavier: (R. Simmons, S. Koenig, CMU 1996) Markov localization in a topological map
Markov Localization in Grid Map
What is the Right Representation?
Idea: Represent Belief Through Samples
PPT Slide
PPT Slide
PPT Slide
PPT Slide
Particle Filters
Monte Carlo Localization
Monte Carlo Localization, cont’d
Performance Comparison
Monte Carlo Localization
Pitfall: The World is not Markov!
Avoiding Collisions with Invisible Hazards
Tracking People
Tracking People
Multi-Robot Localization
Probabilistic Localization: Lessons Learned
Tutorial Outline
The Problem: Concurrent Mapping and Localization
The Problem: Concurrent Mapping and Localization
On-Line Mapping with Rhino
Concurrent Mapping and Localization
Mapping: Outline
Mapping as Posterior Estimation
Kalman Filters
Underwater Mapping
Underwater Mapping - Example
Mapping with Extended Kalman Filters
The Key Assumption
Mapping Algorithms - Comparison
Mapping: Outline
Mapping with Expectation Maximization
PPT Slide
PPT Slide
PPT Slide
CMU’s Wean Hall (80 x 25 meters)
EM Mapping, Example (width 45 m)
Mapping Algorithms - Comparison
Mapping: Outline
Incremental ML Mapping, Online
Incremental ML: Not A Good Idea
ML* Mapping, Online
ML* Mapping, Online Courtesy of Kurt Konolige, SRI
ML* Mapping, Online
Mapping with Poor Odometry
Mapping Without(!) Odometry
Localization in Multi-Robot Mapping
Localization in Multi-Robot Mapping Courtesy of Kurt Konolige, SRI
3D Mapping
3D Structure Mapping (Real-Time)
3D Texture Mapping
3D Texture Mapping
Mapping Algorithms - Comparison
Mapping: Outline
Occupancy Grids: From scans to maps
Occupancy Grid Maps
Example
Mapping Algorithms - Comparison
Mapping: Lessons Learned
Tutorial Outline
The Decision Making Problem
Planning under Uncertainty
Classical Situation
MDP-Style Planning
Stochastic, Partially Observable
Stochastic, Partially Observable
Stochastic, Partially Observable
Outline
Robot Planning Frameworks
MDP-Style Planning
Markov Decision Process (discrete)
Value Iteration
Value Iteration for Motion Planning (assumes knowledge of robot’s location)
Continuous Environments
Approximate Cell Decomposition [Latombe 91]
Parti-Game [Moore 96]
Robot Planning Frameworks
Stochastic, Partially Observable
A Quiz
Introduction to POMDPs
Value Iteration in POMDPs
Missing Terms: Belief Space
Value Iteration in Belief Space
Why is This So Complex?
Augmented MDPs:
Path Planning with Augmented MDPs
Robot Planning Frameworks
Decision Making: Lessons Learned
Tutorial Outline
Exploration: Maximize Knowledge Gain
Practical Implementation
Real-Time Exploration
Coordinated Multi-Robot Exploration
Collaborative Exploration and Mapping
San Antonio Results
Benefit of Cooperation
Exploration: Lessons Learned
Tutorial Outline
Problem Summary
Key Idea
Examples Covered Today
Successful Applications of Probabilistic Robotics
Relation to AI
Open Research Issues
Author: SCS

Email: thrun@cs.cmu.edu