Simultaneous Localization and Mapping

Our version of SLAM derives from original work by Lu and Milios on Consistent Pose Estimation (CPE).  Their insight was that local constraints among the poses of a robot could be expressed in a probabilistic way, and a near-optimal solution found efficiently using linear methods.  In [Gutmann and Konolige 1999], we solved the loop-closure problem, automating the process of creating high-quality, online indoor maps from laser scans.  In the figures at the right, the robot has started around a loop, but interrupted closing it by going up (off the picture) and coming back.  The red arrows are robot poses, the black lines are scan matches between poses.  In the second figure, the loop closure has been identified, and CPE finds a minimal configuration for the constraints.

A movie of one of our first loop closures can be found here.  We deliberately added more error into the scan matching process, so that the loop closure would be hard to find.

The local constraints of CPE make it easy to put together partial maps from several robots, in an optimal way.  Furthermore, the process can be distributed naturally, so that each robot or robot group can update its map opportunistically when it meets other robots.

The figure at the right is an environment over 100 meters in length, mapped by 5 robots.  There are 1265 scans; only two loop closures were necessary (between different robots!), and the average time to process a scan was 200 ms.  You can view a movie of the process here.

Another movie of an autonomous 2-robot mapping run at Ft AP Hill in January, 2004.

Much of this work was done in the Centibots project.  Relevant papers are [Konolige et al. 2003a], [Konolige et al. 2004b], [Konolige and Chou 1999].

The really hard problem in multi-robot mapping is how to combine partial maps from robots that initially don't know their relative locations.  Imagine two robots that start from opposite ends of a building, sending each other their scans, without knowing how the scans are related.

In the figure at the right, Robot A is trying to estimate Robot B's position in its own map, from the scans B is sending.  Standard localization procedures don't apply, because there's the possibility that B isn't in A's map at all.  By keeping track of an outside-the-map hypothesis, Robot A can make reliable decisions about Robot B's presence in its map [Ko et al. 2003].  Even more reliable decisions can be made by understanding what is novel about an environment; here we use hierarchical Bayesian models to learn about a new environment [Fox et al. 2003],  [Stewart et al. 2003].

Dieter Fox's group at the University of Washington made this movie about the process.

What happens when you try to scale up to 10000 poses?  100000?  We investigated this question by looking at the scaling behavior of the CPE algorithm.  The connection matrix between poses is sparse (see figure at right), and taking advantage of this we found algorithms that scaled as N log N in the number of poses, with a very low initial factor.  The figure at the far right shows a randomly-generated map with over 50K poses and hundreds of loop, which was optimized in several seconds.  There is a paper on the method [Konolige 2004c].