Dieter Fox and Frank Dellaert
To navigate reliably in indoor environments, mobile robots must know where they are. Therefore, estimating the position of a robot based on sensor data is one of the fundamental problems of mobile robotics. This problem can be divided into two sub-tasks: global position estimation and local position tracking. Global position estimation is the ability to determine the robot's position in an a priori or previously learned map, given no other information than that the robot is somewhere on the map. Once a robot has been localized in the map, local tracking is the problem of keeping track of that position over time. While existing approaches to position tracking are able to estimate a robot's position eficiently and accurately, they typically fail to globally localize a robot from scratch or to recover from localization failure. Global localization techniques, on the other hand, are less accurate and often require significantly more computational power. In this project we introduce a new representation of the robot's state space based on Monte Carlo sampling. This technique inherits the benefits of our previously introduced position probability grid approach for position estimation, thus providing an extremely efficient technique for global mobile robot localization.
This method will allow robots to operate with a high degree of autonomy, since the initial location of the robot does not have to be specified. Furthermore, even if the initial location is known, this approach provides an additional level of robustness, due to it's ability to recover from localization failure. The proposed techniqe can be applied even on low-cost robots, since it can deal with noisy sensors such as ultra-sound sensors and does not require powerful computer hardware.
In order to deal with uncertain sensor information, most approaches to position estimation use a probabilistic representation of the position of a robot. However, current methods for position estimation still face considerable hurdles. In particular, the problems encountered are closely related to the type of representation used to represent probability densities over the robot's state space. Local approaches aim at tracking the position of a robot once it's starting location is known and usually use Kalman filters to integrate sensor information over time (see e.g. [1,4] for overviews). Existing approaches of this class have shown to be efficient and accurate, but due to the assumptions underlying these methods, they typically are not able to localize the robot globally. Recently, several researchers proposed a new localization paradigm, called Markov localization [9,7,3]. This technique uses a richer representation for the state space of the robot and therefore is able to localize a robot from scratch, i.e. without knowledge of it's starting location. Our previous work belongs to this class of techniques and uses position probability grids to represent the three-dimensional state space of the robot. The disadvantage of this aproaches lies in it's computational complexity, which could only be handled by introducing several dedicated techniques .
The Monte Carlo Localization method takes a new approach to representing uncertainty in mobile robot localization: instead of describing the state space by a probability density function, we represent it by maintaining a set of samples that are randomly drawn from it. To update this density representation over time, we make use of Monte Carlo methods that were invented in the seventies and recently rediscovered independently in the target-tracking , statistical  and computer vision literature .
By using a sampling-based representation we obtain a localization method that has several key advantages with respect to earlier work. In contrast to Kalman filtering based techniques, it is able to represent multi-modal distributions and thus can globally localize a robot. It drastically reduces the amount of memory required compared to grid-based Markov localization, and it can integrate measurements at a considerably higher frequency. It is more accurate than Markov localization with a fixed cell size, as the state represented in the samples is not discretized.
In future work, the reduced memory requirements of the algorithm will allow us to extend the robot's state with velocity information, thus making it possible to project the state of interest into the future. The increased efficiency of the MCL-method will be utilized to apply our approaches to position estimation and map buillding within mulit-robot scenarios. Here, one task is to build consistent maps using information collected by different robots. Furthermore, the localization task of a robot can be significantly accelerated if knowledge about the position of other robot's is used.