Computer Science Department
School of Computer Science, Carnegie Mellon University


Simultaneous Mapping and Localization With
Sparse Extended Information Filters:
Theory and Initial Results

Sebastian Thrun, Daphne Koller*, Zoubin Ghahmarani**,
Hugh Durrant-Whyte***, Andrew Y. Ng

October 2002
(Revision from July and September 2002)

Keywords: Robot mapping, Kalman filters, Kalman filter, information filter, Bayesian techniques, robot navigation, robot localization, sparse information filter

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.

26 pages

*Stanford University
**University College London
***University of Syndey

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by