Simultaneous Mapping and Localization With Sparse Extended Information Filters: Theory and Initial Results
(original May 14, 2002; revised September 28, 2002)

Sebastian Thrun, Daphne Koller, Zoubin Ghahramani, Hugh Durrant-Whyte, and Andrew Y. Ng

This paper describes a scalable algorithm for the simultaneous mapping and localization (SLAM) problem. SLAM is the problem of determining the location of environmental features with a roving robot. Many of today's popular techniques are based on extended Kalman filters (EKFs), which require update time quadratic in the number of features in the map. This paper develops the notion of sparse extended information filters (SEIFs), as a new method for solving the SLAM problem. SEIFs exploit structure inherent in the SLAM problem, representing maps through local, Web-like networks of features. By doing so, updates can be performed in constant time, irrespective of the number of features in the map. This paper presents several original constant-time results of SEIFs, and provides simulation results that show the high accuracy of the resulting maps in comparison to the computationally more cumbersome EKF solution.

The full paper is available in gzipped Postscript and PDF

@INPROCEEDINGS{Thrun02e,
  AUTHOR         = {Thrun, S. and Koller, D. and Ghahramani, Z. and 
                    Durrant-Whyte, H. and Ng. A.Y.},
  TITLE          = {Simultaneous Mapping and Localization With Sparse 
                    Extended Information Filters},
  YEAR           = {2002},
  BOOKTITLE      = {Proceedings of the Fifth International Workshop on 
                    Algorithmic Foundations of Robotics},
  EDITOR         = {J.-D. Boissonnat and J. Burdick and K. Goldberg and 
                    S. Hutchinson},
  ADDRESS        = {Nice, France},
  NOTE           = {Forthcoming}
}