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)
CMU-CS-02-112.ps
CMU-CS-02-112.ps.gz
CMU-CS-02-112.pdf
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 This page maintained by [email protected]
School of Computer Science homepage