This paper describes a scalable algorithm for the simultaneous mapping and
localization (SLAM) problem. SLAM is the problem of acquiring a map of a
static environment with a mobile robot. The vast majority of SLAM algorithms
are based on the extended Kalman filter (EKF). This paper advocates an
algorithm that relies on the dual of the EKF, the extended information
filter (EIF). We show that when represented in the information form, map
posteriors are dominated by a small number of links that tie together nearby
features in the map. This insight is developed into a sparse variant of the
EIF, called the sparse extended information filters (SEIF). SEIFs represent
maps by graphical networks of features that are locally interconnected,
where links represent relative information between pairs of nearby features,
as well as information about the robot s pose relative to the map. We show
that all essential update equations in SEIFs can be executed in constant
time, irrespective of the size of the map. We also provide empirical results
obtained for a benchmark data set collected in an outdoor environment, and
using a multi-robot mapping simulation.