CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

Modeling and Controlling Uncertainty in SLAM

Edwin Olson, John Leonard & Seth Teller


In preparation for human arrival, a robot might be sent to Mars to survey the surface for suitable landing sites, assemble habitat structures, deploy equipment, and collect rock specimens for analysis. Currently, Spirit and Opportunity are primarily teleoperated by humans on Earth, resulting in enormous inefficiency: after more than a year on Mars, Opportunity had traveled a total distance of 2.2km-- about half as far as Opportunity could theoretically travel in a single day. Of course the rovers are performing time-consuming experiments in addition to moving around, but the point remains that having humans involved in simple navigation tasks has had an enormous impact on efficiency. Since the rovers have a limited lifespan and are enormously expensive to send to Mars, this inefficiency is very costly.

A generated map of Stata's 7th
floor Building plans of Stata's 7th floor

Our work addresses this inefficiency by improving the reliability of autonomous map building and navigation. Building maps and navigating with them is known as Simultaneous Localization and Mapping (SLAM). We are modeling the structure of uncertainty of a robot's map, allowing an understanding of which areas are uncertain and why: one area might be uncertain because of uncertainty in a different area. Using this model, we show how robots can take an active role in controlling uncertainty by modifying their exploration strategies. These approaches improve mapping and navigation performance, allowing robots to operate in more difficult environments than is currently possible.


While many SLAM algorithms have been developed, the problem remains difficult: existing algorithms fail when the environment is either too feature rich (cluttered) or feature poor (desolate), some fail or become intractable when open-loop uncertainties become too great, and some consume too much memory or CPU time as the map grows. In addition to studying uncertainty, we are exploring simplifications to SLAM algorithms which are possible when a few weak assumptions are made. Our approach, like several others, constructs a graph of robot poses; loop closure constraints are represented by cycles in the graph. We are pursuing a number of optimization approaches, including Gauss-Seidel style relaxation [1].

Hypothetical graph representing a map and its constraints

Existing approaches to exploration are minimally aware of uncertainty; they typically optimize a local measure of information gain, or simply head towards unexplored space. Improving the quality of a map often requires re-traversing a large loop, yet modeling uncertainty on this macroscopic scale seems to have escaped study. In fact, humans often control robots when collecting data for a SLAM algorithm, removing any possibility of uncertainty-aware exploration.

Ultimately, the quality of a SLAM implementation often is dependent on both the quality and quantity of the data association that can be made. Each assertion that two observations were of the same feature adds a constraint to the map. Like any over-determined system, additional constraints generally lead to greater accuracy. While data-association algorithms like the Joint Compatibility Test [2] provide good results, its exponential runtime can be a major limitation. We continue to extend our work on Single Cluster Graph Partitioning [3], which can provide an approximate answer in polynomial time.


[1] T. Duckett, S. Marsland, and J. Shapiro. Learning Globally Consistent Maps by Relaxation. ICRA 2000.

[2] J. Neira and J. D. Tardos. Data Association in Stochastic Mapping using the Joint Compatibility Test. TRA 2001.

[3] E. Olson, S. Teller, and J.Leonard. Single Cluster Graph Partitioning for Robotics Applications. RSS 2005.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)