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.
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 .
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  provide good results, its exponential runtime can be a major limitation. We continue to extend our work on Single Cluster Graph Partitioning , which can provide an approximate answer in polynomial time.