Monte Carlo Localization for Mobile Robots (MCL-method)

Dieter Fox and Frank Dellaert

Problem:

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.

Impact:

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.

State of the Art:

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 [2].

Approach:

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 [5], statistical [8] and computer vision literature [6].

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.

Future Work:

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.


  
Figure 1: Sonar-based global localization with the MCL-method: map of the environment and distribution of the samples during different stages of localization (20.000 samples were used). The robot starts in the corridor without knowing where it is (left figure). As it enters the upper left room, the samples are already concentrated around two positions according to the symmetry of the environment (center figure). Finally, the robot has been able to uniquely determine its position because the upper left room looks (to the sonars) different from the symmetrically opposed room (right figure).
\begin{figure*}
\leavevmode \hspace*{\fill}
\fbox{\epsfig{file=first.ps,width=...
...dth=0.29\textwidth,clip=}} \hspace*{\fill}
\rule{\textwidth}{.2mm}
\end{figure*}

Bibliography

1
Johann Borenstein, H.R. Everett, and Liqiang Feng.
Navigating Mobile Robots: Systems and Techniques.
A. K. Peters, Ltd., Wellesley, MA, 1996.

2
Wolfram Burgard, Andreas Derr, Dieter Fox, and Armin B. Cremers.
Integrating global position estimation and position tracking for mobile robots: The dynamic markov localization approach.
In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'98), 1998.

3
Wolfram Burgard, Dieter Fox, Daniel Hennig, and Timo Schmidt.
Estimating the absolute position of a mobile robot using position probability grids.
In Proc. of the Thirteenth National Conference on Artificial Intelligence, pages 896-901, 1996.

4
I.J. Cox and G.T. Wilfong, editors.
Autonomous Robot Vehicles.
Springer Verlag, 1990.

5
N J Gordon, D J Salmond, and A F M Smith.
Novel approach to nonlinear/non-Gaussian Bayesian state estimation.
IEE Procedings F, 140(2):107-113, 1993.

6
Michael Isard and Andrew Blake.
Contour tracking by stochastic propagation of conditional density.
In European Conference on Computer Vision, pages 343-356, 1996.

7
Leslie Pack Kaelbling, Anthony R. Cassandra, and James A. Kurien.
Acting under uncertainty: Discrete bayesian models for mobile-robot navigation.
In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 1996.

8
Genshiro Kitagawa.
Monte carlo filter and smoother for non-gaussian nonlinear state space models.
Journal of Computational and Graphical Statistics, 5(1):1-25, 1996.

9
Reid Simmons and Sven Koenig.
Probabilistic robot navigation in partially observable environments.
In Proc. International Joint Conference on Artificial Intelligence, 1995.

About this document...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998).
The translation was performed on 1998-11-20.