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

The **M**onte **C**arlo **L**ocalization 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.

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.

**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.

The translation was performed on 1998-11-20.