Tim Bailey and Hugh Durrant-Whyte

Simultaneous Localisation and Mapping (SLAM):
Part II State of the Art

Robotics and Automation Magazine, September, 2006


 

Description

This is the second of a two-part tutorial on SLAM. It documents and classifies the current techniques developed to address computational complexity, data association, and environmental representation.
 

Abstract

This tutorial provides an introduction to the Simultaneous Localisation and Mapping (SLAM) method and the extensive research on SLAM that has been undertaken. Part I of this tutorial described the essential SLAM problem. Part II of this tutorial (this paper) is concerned with recent advances in computational methods and in new formulations of the SLAM problem for large scale and complex environments.

Download

A modified version of the paper is provided below. It has slightly different content to the published article, reflecting my personal preference and a few corrections.

Updated paper [pdf] (519 kb, 10 pages)
Original paper [pdf] (390 kb, 9 pages)

Addendum

While this paper presents a survey of the state-of-the-art in SLAM methods in 2006, it does not cover all existing variations, and we list here some of the notable missing works.

  • There are several SLAM implementations that are closely related to the sparse information-form SLAM described in our article. These include Graph-SLAM [1], which is a batch mapping algorithm rather than a recursive SLAM algorithm; thin junction tree SLAM [2], which uses a graphical model representation; tree-SLAM [3], which uses a binary-tree data-structure; and Graphical SLAM [4], which optimises its state estimate via (what amounts to) iterated least-squares. While we did not discuss the details of these various contributions, they all share the essential structure of the sparse canonical-form Gaussian representation.
  • There exists a version of recursive SLAM based on grid-maps [5,6]. The problem with this formulation is that there is currently no formal proof of convergence, and, more importantly, it fails to exhibit consistent loop closure. That is, on closing a loop, accumulated errors are not propagated back through the loop, and a discontinuity forms in the map.
  • That is not to say that consistent grid-based SLAM is impossible. FastSLAM hybrids using grids (eg, [7]) are consistent insofar as FastSLAM is consistent. Grids are also suitable for trajectory-based SLAM and as the local-map representation in ATLAS or NCFM; (we presume grid-SLAM exhibits convergent behaviour within local regions). Grids are also well suited to batch map building (eg, [8,9]).
  • For trajectory-based SLAM, an incremental relaxation algorithm has been developed [10].
  • Our section on multiple-hypothesis data association claims there is currently no feasible implementation of MHT for SLAM. However, there is interesting work that appears to offer something similar by permitting association correction over a measurement-history [4,11].

References

  1. S. Thrun, W. Burgard and D. Fox. Probabilistic Robotics. MIT Press, Cambridge, MA, 2005.
  2. M.A. Paskin. Thin junction tree filters for simultaneous localization and mapping. Technical report, University of California, Computer Science Division, 2002.
  3. U. Frese, An O(log n) algorithm for simultaneous localization and mapping of mobile robots in indoor environments, Ph.D. thesis, University of Erlangen-Nurnberg, 2004.
  4. J. Folkesson and H. I. Christensen. Graphical SLAM - a self-correcting map. In IEEE International Conference on Robotics and Automation, pages 791–798, 2004.
  5. B. Yamauchi, A. Schultz, and W. Adams. Mobile robot exploration and map-building with continuous localization. In IEEE International Conference on Robotics and Automation, pages 3715–3720, 1998.
  6. A.C. Schultz, W. Adams, B. Yamauchi, and M. Jones. Unifying exploration, localization, navigation and planning through a common representation. In IEEE International Conference on Robotics and Automation, pages 2651–2658, 1999.
  7. D. Hahnel, W. Burgard, D. Fox, and S. Thrun. An efficient Fast-SLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 206–211, 2003.
  8. S. Thrun. Learning metric-topological maps for indoor mobile robot navigation. Artificial Intelligence, 99(1):21–71, 1998.
  9. W. Burgard, D. Fox, H. Jans, C. Matenar, and S. Thrun. Sonar-based mapping with mobile robots using EM. In International Conference on Machine Learning, 1999.
  10. U. Frese, P. Larsson, and T Duckett. A multigrid relaxation algorithm for simultaneous localization and mapping. IEEE Transactions on Robotics, pages 196-207, 2005.
  11. D. Hahnel, S. Thrun, B. Wegbreit, W. Burgard. Towards lazy data association in SLAM. In International Symposium of Robotics Research, 2003.


[Tim's Homepage]