Robot localization has been recognized as one of the most fundamental problems in mobile robotics [Cox & Wilfong1990, Borenstein et al. 1996]. The aim of localization is to estimate the postition of a robot in its environment, given a map of the environment and sensor data. Most successful mobile robot systems to date utilize localization, as knowledge of the robot's position is essential for a broad range of mobile robot tasks.
Localization--often referred to as position estimation or position control--is currently a highly active field of research, as a recent book by Borenstein and colleagues [Borenstein et al. 1996] suggests. The localization techniques developed so far can be distinguished according to the type of problem they attack. Tracking or local techniques aim at compensating odometric errors occurring during robot navigation. They require, however, that the initial location of the robot is (approximately) known and they typically cannot recover if they lose track of the robot's position (within certain bounds). Another family of approaches is called global techniques. These are designed to estimate the position of the robot even under global uncertainty. Techniques of this type solve the so-called wake-up robot problem, in that they can localize a robot without any prior knowledge about its position. They furthermore can handle the kidnapped robot problem, in which a robot is carried to an arbitrary location during it's operation. Please note that the wake-up problem is the special case of the kidnapped robot problem in which the robot is told that it has been carried away. Global localization techniques are more powerful than local ones. They typically can cope with situations in which the robot is likely to experience serious positioning errors.
In this paper we present a metric variant of Markov localization, a technique to globally estimate the position of a robot in its environment. Markov localization uses a probabilistic framework to maintain a position probability density over the whole set of possible robot poses. Such a density can have arbitrary forms representing various kinds of information about the robot's position. For example, the robot can start with a uniform distribution representing that it is completely uncertain about its position. It furthermore can contain multiple modes in the case of ambiguous situations. In the usual case, in which the robot is highly certain about its position, it consists of a unimodal distribution centered around the true position of the robot. Based on the probabilistic nature of the approach and the representation, Markov localization can globally estimate the position of the robot, it can deal with ambiguous situations, and it can re-localize the robot in the case of localization failures. These properties are basic preconditions for truly autonomous robots designed to operate over long periods of time.
Our method uses a fine-grained and metric discretization of the state space. This approach has several advantages over previous ones, which predominately used Gaussians or coarse-grained, topological representations for approximating a robot's belief. First, it provides more accurate position estimates, which are required in many mobile robot tasks (e.g., tasks involving mobile manipulation). Second, it can incorporate raw sensory input such as a single beam of an ultrasound sensor. Most previous approaches to Markov localization, in contrast, screen sensor data for the presence or absence of landmarks, and they are prone to fail if the environment does not align well with the underlying assumptions (e.g., if it does not contain any of the required landmarks).
Most importantly, however, previous Markov localization techniques assumed that the environment is static. Therefore, they typically fail in highly dynamic environments, such as public places where crowds of people may cover the robot's sensors for extended periods of time. To deal with such situations, our method applies a filtering technique that, in essence, updates the position probability density using only those measurements which are with high likelihood produced by known objects contained in the map. As a result, it permits accurate localization even in densely crowded, non-static environments.
Our Markov localization approach has been implemented and evaluated in various environments, using different kinds of robots and sensor modalities. Among these applications are the deployments of the mobile robots Rhino and Minerva (see Figure 1) as interactive museum tour-guide robots ([Burgard et al. 1998a, Burgard et al. 2000, Thrun et al. 1999]) in the Deutsches Museum Bonn and the National Museum of American History in Washington, DC, respectively. Experiments described in this paper illustrate the ability of our Markov localization technique to deal with approximate models of the environment, such as occupancy grid maps and noisy sensors such as ultrasound sensors, and they demonstrate that our approach is well-suited to localize robots in densely crowded environments, such as museums full of people.
The paper is organized as follows. The next section describes the mathematical framework of Markov localization. We introduce our metric version of Markov localization in Section 3. This section also presents a probabilistic model of proximity sensors and a filtering scheme to deal with highly dynamic environments. Thereafter, we describe experimental results illustrating different aspects of our approach. Related work is discussed in Section 5 followed by concluding remarks.