FastSLAM

by Montemerlo, Michael; Thrun, Sebastian

• ISBN13: 9783540463993
• ISBN10: 3540463992
• Format: Hardcover
• Copyright: 2007-07-04
• Publisher: Springer Verlag

Summary

This monograph describes a new family of algorithms for the simultaneous localization and mapping problem in robotics (SLAM). SLAM addresses the problem of acquiring an environment map with a roving robot, while simultaneously localizing the robot relative to this map. This problem has received enormous attention in the robotics community in the past few years, reaching a peak of popularity on the occasion of the DARPA Grand Challenge in October 2005, which was won by the team headed by the authors. The FastSLAM family of algorithms applies particle filters to the SLAM Problem, which provides new insights into the data association problem that is paramount in SLAM. The FastSLAM-type algorithms have enabled robots to acquire maps of unprecedented size and accuracy, in a number of robot application domains and have been successfully applied in different dynamic environments, including the solution to the problem of people tracking.

Table of Contents

Introduction	p. 1
Applications of SLAM	p. 1
Joint Estimation	p. 2
Posterior Estimation	p. 3
The Extended Kalman Filter	p. 5
Quadratic Complexity	p. 5
Single-Hypothesis Data Association	p. 6
Structure and Sparsity in SLAM	p. 7
FastSLAM	p. 8
Logarithmic Complexity	p. 10
Multi-hypothesis Data Association	p. 10
Outline	p. 11
The SLAM Problem	p. 13
Problem Definition	p. 13
SLAM Posterior	p. 15
SLAM as a Markov Chain	p. 16
Bayes Filter Derivation	p. 17
Extended Kalman Filtering	p. 18
Scaling SLAM Algorithms	p. 20
Submap Methods	p. 20
Sparse Extended Information Filters	p. 21
Thin Junction Trees	p. 22
Covariance Intersection	p. 22
Graphical Optimization Methods	p. 22
Robust Data Association	p. 23
Local Map Sequencing	p. 24
Joint Compatibility Branch and Bound	p. 24
Combined Constraint Data Association	p. 25
Iterative Closest Point	p. 25
Multiple Hypothesis Tracking	p. 25
Comparison of FastSLAM to Existing Techniques	p. 26
FastSLAM 1.0	p. 27
Particle Filtering	p. 27
Factored Posterior Representation	p. 29
Proof of the FastSLAM Factorization	p. 30
The FastSLAM 1.0 Algorithm	p. 32
Sampling a New Pose	p. 33
Updating the Landmark Estimates	p. 35
Calculating Importance Weights	p. 37
Importance Resampling	p. 38
Robot Path Posterior Revisited	p. 39
FastSLAM with Unknown Data Association	p. 39
Data Association Uncertainty	p. 39
Per-Particle Data Association	p. 41
Adding New Landmarks	p. 43
Summary of the FastSLAM Algorithm	p. 44
FastSLAM Extensions	p. 46
Greedy Mutual Exclusion	p. 46
Feature Elimination Using Negative Evidence	p. 47
Log(N) FastSLAM	p. 48
Garbage Collection	p. 50
Unknown Data Association	p. 51
Experimental Results	p. 51
Victoria Park	p. 52
Comparison of FastSLAM and the EKF	p. 56
Ambiguous Data Association	p. 59
Sample Impoverishment	p. 59
Summary	p. 62
FastSLAM 2.0	p. 63
Sample Impoverishment	p. 63
FastSLAM 2.0	p. 65
The New Proposal Distribution	p. 66
Calculating the Importance Weights	p. 69
FastSLAM 2.0 Overview	p. 71
Handling Simultaneous Observations	p. 71
FastSLAM 2.0 Convergence	p. 74
Convergence Proof	p. 75
Experimental Results	p. 79
FastSLAM 1.0 Versus FastSLAM 2.0	p. 79
One Particle FastSLAM 2.0	p. 81
Scaling Performance	p. 83
Loop Closing	p. 83
Convergence Speed	p. 85
Grid-Based FastSLAM	p. 87
Summary	p. 90
Dynamic Environments	p. 91
SLAM with Dynamic Landmarks	p. 92
Derivation of the Bayes Filter with Dynamic Objects	p. 93
Factoring the Dynamic SLAM Problem	p. 95
Simultaneous Localization and People Tracking	p. 96
Comparison with Prior Work	p. 97
FastSLAP Implementation	p. 97
Scan-Based Data Association	p. 98
Measurement Model	p. 100
Motion Model	p. 101
Model Selection	p. 101
Experimental Results	p. 102
Tracking and Model Selection Accuracy	p. 102
Global Uncertainty	p. 103
Intelligent Following Behavior	p. 103
Summary	p. 105
Conclusions	p. 107
Conclusion	p. 107
Limitations of FastSLAM	p. 108
Future Work	p. 109
References	p. 111
Index	p. 117
Table of Contents provided by Ingram. All Rights Reserved.