Abstract
In order to re-use existing models of the environment mobile robots must be able to estimate their position and orientation in such models. Most of the existing methods for position estimation are based on special purpose sensors or aim at tracking the robot's position relative to the known starting point. This paper describes the position probability grid approach to estimating the robot's absolute position and orientation in a metric model of the environment. Our method is designed to work with standard sensors and is independent of any knowledge about the starting point. It is a Bayesian approach based on certainty grids. In each cell of such a grid we store the probability that this cell refers to the current position of the robot. These probabilities are obtained by integrating the likelihoods of sensor readings over time. Results described in this paper show that our technique is able to reliably estimate the position of a robot in complex environments. Our approach has proven to be robust with respect to inaccurate environmental models, noisy sensors, and ambiguous situations.
Introduction
In the mid-90s, most mobile robots relied on "relative" position estimation (dead reckoning) using wheel encoders. However, small errors in wheel rotation accumulate over time, eventually causing the robot to lose its position entirely. This paper addresses the Global Localization problem: determining a robot's absolute position ("Where am I?") without prior knowledge of its starting point. This is critical for initial system startup and for recovery when tracking systems fail due to significant wheel slip or other errors. The challenge lies in the inherent noise of standard sensors like sonar and the prevalence of "perceptual aliasing," where different locations in an environment appear identical.
Methodology: Position Probability Grids
The proposed solution is a Bayesian framework utilizing a 3D grid to represent the robot's state $(x, y, \theta)$. Each cell in this grid stores the probability that the robot is currently at that specific location and orientation.
The system updates this probability distribution through two alternating phases:
- Movement Update: As the robot moves, the probability distribution is shifted and "blurred" using a Markov chain model. This process accounts for the noise inherent in dead reckoning.
- Sensor Update: Upon receiving a sensor reading (e.g., ultrasonic range-finding), the system calculates the likelihood of that measurement from every possible cell in the grid. Bayes' rule is then applied to update the grid's probabilities.
Unlike traditional Kalman filters that track a single unimodal Gaussian distribution, this grid-based approach can maintain multiple probability peaks. This allows the robot to entertain several hypotheses simultaneously until sufficient data is gathered to resolve ambiguities.
Experimental Evaluation
The system was evaluated using the custom-built robot RHINO in two real-world settings: a $4 \times 7\text{m}^2$ department office and the $600\text{m}^2$ AAAI ’94 Arena. The maps used for localization were occupancy grids previously constructed by the robot.
A key insight of this work is the "any-time" characteristic: the system provides a location estimate after the first sensor reading and continuously refines it. By embracing ambiguity, the robot can navigate safely while "somewhere in this hallway" until it encounters a unique landmark.
Results
The technique demonstrated high precision, estimating positions within a few centimeters. In the office environment, an initially multi-modal distribution successfully collapsed into a single clear peak at the correct location after 12 sonar sweeps.
In the larger arena, the robot uniquely determined its position after 12 steps, reaching a 0.96 probability for the correct cell. Computationally, a grid update took approximately 6 seconds on a 90 MHz Pentium processor, which was sufficient for real-time operation at the time.
Conclusion and Future Work
While robust against noisy sensors and minor environmental changes, the method's computational requirements grow linearly with grid size, potentially limiting its use in massive environments. Future work suggested "active" exploration strategies where the robot moves specifically to gain information and resolve ambiguities faster.
Summary updated