FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem with Unknown Data Association

Abstract

Simultaneous Localization and Mapping (SLAM) is an essential capability for mobile robots exploring unknown environments. The Extended Kalman Filter (EKF) has served as the de-facto approach to SLAM for the last fifteen years. However, EKF-based SLAM algorithms suffer from two well-known shortcomings that complicate their application to large, real-world environments: quadratic complexity and sensitivity to failures in data association. I will present an alternative approach to SLAM that specifically addresses these two areas. This approach, called FastSLAM, factors the full SLAM posterior exactly into a product of a robot path posterior, and N landmark posteriors conditioned on the robot path estimate. This factored posterior can be approximated efficiently using a particle filter. The time required to incorporate an observation into FastSLAM scales logarithmically with the number of landmarks in the map. In addition to sampling over robot paths, FastSLAM can sample over potential data associations. Sampling over data associations enables FastSLAM to be used in environments with highly ambiguous landmark identities. This dissertation will describe the FastSLAM algorithm given both known and unknown data association. The performance of FastSLAM will be compared against the EKF on simulated and real-world data sets. Results will show that FastSLAM can produce accurate maps in extremely large environments, and in environments with substantial data association ambiguity. Finally, a convergence proof for FastSLAM in the linear-Gaussian case and an extension of FastSLAM to dynamic worlds will be presented.