Estimating the Absolute Position of a Mobile Robot Using Position Probability Grids

Wolfram Burgard, Dieter Fox, Daniel Hennig, Timo SchmidtAAAI 1996 · OpenReview

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:

  1. 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.
  2. 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 setup in an office environment showing the true path (A) and alternative hypotheses (B, C).

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.

Evolution of the position probability distribution over 12 steps, showing the resolution of ambiguity into a single peak.

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

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.
BibTeX
@inproceedings{burgard1996estimating,
  author = {Wolfram Burgard and Dieter Fox and Daniel Hennig and Timo Schmidt},
  title = {{Estimating the Absolute Position of a Mobile Robot Using Position Probability Grids}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
  url = {https://openreview.net/forum?id=BkZxAyZObS},
}
Figure