Most of the techniques for mobile robot localization in the literature belong to the class of local approaches or tracking techniques, which are designed to compensate odometric error occurring during navigation. They assume that the initial position of the robot is known (see [Borenstein et al. 1996] for a comprehensive overview). For example, [Weiß et al. 1994] store angle histograms constructed out of laser range-finder scans taken at different locations in the environment. The position and orientation of the robot are calculated by maximizing the correlation between the stored histograms and laser range-scans obtained while the robot moves through the environment. The estimated position, together with the odometry information, is then used to predict the position of the robot and to select the histogram used for the next match. [Yamauchi1996, Schultz et al. 1999] apply a similar technique, but they use hill-climbing to match local maps built from ultrasound sensors into a global occupancy grid map. As in the approach by [Weiß et al. 1994], the location of the robot is represented by the position yielding the best match. These techniques, in contrast to Markov localization, do not represent the uncertainty of the robot in its current belief and therefore cannot deal appropriately with globally ambiguous situations.
A popular probabilistic framework for position tracking are Kalman filters [Maybeck1990, Smith et al. 1990], a signal processing technique introduced by Kalman [Kalman1960]. As mentioned in Section 2.4, Kalman filter-based methods represent their belief of the robot's position by a unimodal Gaussian distribution over the three-dimensional state-space of the robot. The mode of this distribution yields the current position of the robot, and the variance represents the robot's uncertainty. Whenever the robot moves, the Gaussian is shifted according to the distance measured by the robot's odometry. Simultaneously, the variance of the Gaussian is increased according to the model of the robot's odometry. New sensory input is incorporated into the position estimation by matching the percepts with the world model.
Existing applications of Kalman filtering to position estimation for mobile robots are similar in how they model the motion of the robot. They differ mostly in how they update the Gaussian according to new sensory input. [Leonard & Durrant-Whyte1991] match beacons extracted from sonar scans with beacons predicted from a geometric map of the environment. These beacons consist of planes, cylinders, and corners. To update the current estimate of the robot's position, [Cox1991] matches distances measured by infrared sensors with a line segment description of the environment. [Schiele & Crowley1994] compare different strategies to track the robot's position based on occupancy grid maps and ultrasonic sensors. They show that matching local occupancy grid maps with a global grid map results in a similar localization performance as if the matching is based on features that are extracted from both maps. [Shaffer et al. 1992] compare the robustness of two different matching techniques with different sources of noise. They suggest a combination of map-matching and feature-based techniques in order to inherit the benefits of both. [Gutmann & Schlegel1996, Lu & Milios1994] use a scan-matching technique to precisely estimate the position of the robot based on laser range-finder scans and learned models of the environment. [Arras & Vestli1998] use a similar technique to compute the position of the robot with a very high accuracy. All these variants, however, rest on the assumption that the position of the robot can be represented by a single Gaussian distribution. The advantage of Kalman filter-based techniques lies in their efficiency and in the high accuracy that can be obtained. The restriction to a unimodal Gaussian distribution, however, is prone to fail if the position of a robot has to be estimated from scratch, i.e. without knowledge about the starting position of the robot. Furthermore, these technique are typically unable to recover from localization failures. Recently, [Jensfelt & Kristensen1999] introduced an approach based on multiple hypothesis tracking, which allows to model multi-modal probability distributions as they occur during global localization.
Markov localization, which has been employed successfully in several variants [Nourbakhsh et al. 1995, Simmons & Koenig1995, Kaelbling et al. 1996, Burgard et al. 1996, Hertzberg & Kirchner1996, Koenig & Simmons1998, Oore et al. 1997, Thrun1998a], overcomes the disadvantage of Kalman filter based techniques. The different variants of this technique can be roughly distinguished by the type of discretization used for the representation of the state space. [Nourbakhsh et al. 1995, Simmons & Koenig1995, Kaelbling et al. 1996] use Markov localization for landmark-based navigation, and the state space is organized according to the topological structure of the environment. Here nodes of the topological graph correspond to distinctive places in hallways such as openings or junctions and the connections between these places. Possible observations of the robot are, for example, hallway intersections. The advantage of these approaches is that they can represent ambiguous situations and thus are in principle able to globally localize a robot. Furthermore, the coarse discretization of the environment results in relatively small state spaces that can be maintained efficiently. The topological representations have the disadvantage that they provide only coarse information about the robot's position and that they rely on the definition of abstract features that can be extracted from the sensor information. The approaches typically make strong assumptions about the nature of the environments. [Nourbakhsh et al. 1995, Simmons & Koenig1995, Kaelbling et al. 1996], for example, only consider four possible headings for the robot position assuming that the corridors in the environment are orthogonal to each other.
Our method uses instead a fine-grained, grid-based discretization of the state space. The advantage of this approach compared to the Kalman filter based techniques comes from the ability to represent more complex probability distributions. In a recent experimental comparison to the technique by [Gutmann & Schlegel1996, Lu & Milios1994], we found that Kalman filter based tracking techniques provide highly accurate position estimates but are less robust, since they lack the ability to globally localize the robot and to recover from localization errors [Gutmann et al. 1998]. In contrast to the topological implementations of Markov localization, our approach provides accurate position estimates and can be applied even in highly unstructured environments [Burgard et al. 1998a, Thrun et al. 1999]. Using the selective update scheme, our technique is able to efficiently keep track of the robot's position once it has been determined. It also allows the robot to recover from localization failures.
Finally, the vast majority of existing approaches to localization differ from ours in that they address localization in static environments. Therefore, these methods are prone to fail in highly dynamic environments in which, for example, large crowds of people surround the robot [Fox et al. 1998c]. However, dynamic approaches have great practical importance, and many envisioned application domains of service robots involve people and populated environments.