Occupancy Grids: A Stochastic Spatial Representation for Active Robot Perception

Alberto Elfes

Seminal March 2013

TL;DR Represent the robot's surroundings as a grid of cells, each holding a Bayesian estimate of the probability that it is occupied, updated from noisy range readings taken from many views and sensors. The paper reviews the framework and shows sonar and sonar-plus-stereo maps, path planning and pose-uncertainty handling done directly on the grid, without quantitative metrics.

What they do

Geometric-feature maps built with prior models and heuristics are, Elfes argues, sparse, brittle and blind to sensor uncertainty. The Occupancy Grid instead divides space into cells, each storing the probability that it is occupied, and resolves ambiguity by taking more readings from more viewpoints. This paper reviews the formulation and its use in mobile robot mapping and navigation.

How it works

Sensor model to cells. Bayes’ rule turns a range reading and a sensor model p(r

z) into per-cell occupancy probabilities. Cells are independent with a prior of 1/2, avoiding the 2^(m²) joint configurations of an m×m map. For an ideal sensor, cells before the reading are empty (0), the hit cell occupied (1), cells beyond unknown (1/2).

Incremental updates. Sequential Bayes folds in each reading with the current map as prior; separate sensor maps merge with the Independent Opinion Pool.
Navigation. A* plans on the grid, trading a cost derived from occupancy probability against path length. Correlation matching registers each new Robot View to the Global Map, and the remaining pose uncertainty is applied as a blur before the maps are combined.

Results

With a Gaussian range sensor (reading r = 2.0, grid initialized to 0.5), repeated updates converge towards the ideal-sensor profile.
The Dolphin sonar system mapped a corridor finely enough to tell walls from open doors and to show wall niches.
Integrating a sonar array with a single-scanline stereo module gave improved maps that exploit the two sensors’ complementarity.
In robot-based mapping, the robot’s surroundings stay sharp while older observations blur.

Limitations

No quantitative accuracy is reported; derivations and experiment details are left to the author’s thesis. Independent cells form a zero-order Markov random field, which the author notes is not enough for precise shape recovery. Experiments mostly cover environments that 2D maps describe.

Figures

From Figure 4: The mapping pipeline. Readings from each sensor pass through a probabilistic sensor model into Sensor ... — From Figure 4: The mapping pipeline. Readings from each sensor pass through a probabilistic sensor model into Sensor Views, which are composed into Local Sensor Maps, integrated into a Robot View, and merged into the Global Map.

From Figure 3: Two-dimensional occupancy grid from a single sonar reading, with the sensor at the upper left pointing... — From Figure 3: Two-dimensional occupancy grid from a single sonar reading, with the sensor at the upper left pointing to the lower right. The flat plane is the unknown (1/2) level.

From Figure 6: Occupancy grids from sonar alone, scanline stereo alone, and both integrated. Occupied cells are shade... — From Figure 6: Occupancy grids from sonar alone, scanline stereo alone, and both integrated. Occupied cells are shaded squares, empty areas dots fading to white, unknown cells + signs.

From Figure 8: Robot-based mapping at two stages. The Global Map is blurred by the robot position uncertainty (covari... — From Figure 8: Robot-based mapping at two stages. The Global Map is blurred by the robot position uncertainty (covariance ellipses) before the new Robot View is composed into it.

Abstract

In this paper we provide an overview of a new framework for robot perception, real-world modelling, and navigation that uses a stochastic tesselated representation of spatial information called the Occupancy Grid. The Occupancy Grid is a multi-dimensional random field model that maintains probabilistic estimates of the occupancy state of each cell in a spatial lattice. Bayesian estimation mechanisms employing stochastic sensor models allow incremental updating of the Occupancy Grid using multi-view, multi-sensor data, composition of multiple maps, decision-making, and incorporation of robot and sensor position uncertainty. We present the underlying stochastic formulation of the Occupancy Grid framework, and discuss its application to a variety of robotic tasks. These include range-based mapping, multi-sensor integration, path-planning and obstacle avoidance, handling of robot position uncertainty, incorporation of pre-compiled maps, recovery of geometric representations, and other related problems. The experimental results show that the Occupancy Grid approach generates dense world models, is robust under sensor uncertainty and errors, and allows explicit handling of uncertainty. It supports the development of robust and agile sensor interpretation methods, incremental discovery procedures, and composition of information from multiple sources. Furthermore, the results illustrate that robotic tasks can be addressed through operations performed directly on the Occupancy Grid, and that these operations have strong parallels to operations performed in the image processing domain.

Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.

Matt Strong