Exploring Unknown Environments with Mobile Robots using Coverage Maps

Cyrill Stachniss, Wolfram BurgardIJCAI 2003

Abstract

This paper introduces Coverage Maps, a probabilistic framework for robotic mapping that moves beyond traditional binary "occupied vs. free" grids. By representing the degree to which a cell is covered by obstacles as a posterior distribution, robots can more accurately model environments from noisy sensor data. We integrate this representation with information-theoretic exploration strategies to optimize the trade-off between map certainty and travel efficiency.

Introduction

Traditional robotic mapping typically relies on Occupancy Grids, which assume every cell in an environment is either 100% occupied or 100% free. This binary assumption often fails in real-world scenarios. For instance, a wall running diagonally through a grid results in many cells being only partially covered. Standard algorithms eventually force these cells into a binary state, leading to structural inaccuracies and poor reasoning about uncertainty.

Furthermore, many exploration strategies focus on visiting "unscanned" areas without accounting for the quality of information gathered. When using noisy sensors like sonar, a single scan is rarely sufficient to determine an area's structure. This research addresses how to represent partial coverage and how to use that representation to decide where a robot should move next to maximize its knowledge of the environment.

Methodology

Coverage Map Representation

Instead of a single probability value per cell, each cell in a Coverage Map stores a posterior distribution (represented as a histogram) over possible coverage values ranging from 0 (empty) to 1 (fully occupied). This allows the robot to maintain a nuanced understanding of its uncertainty.

A histogram representing the posterior distribution of coverage for a single grid cell.

Probabilistic Sensor Model

The authors developed a specialized model for proximity sensors (e.g., sonars). It utilizes a mixture of a Gaussian distribution, centered on the measured distance, and a uniform distribution to account for noise and max-range readings. This model is used to update the coverage histograms as new data arrives.

Decision-Theoretic Exploration

The robot selects its next viewpoint based on four primary strategies:

  • Closest Location (CL): Move to the nearest cell with high entropy (uncertainty).
  • Maximum Information Gain (IG): Move to the location expected to reduce total map entropy the most.
  • IG-WIN: A local-window variant of IG designed to save travel time.
  • IG-CL (Hybrid): A weighted combination balancing information gain with travel cost.

Experimental Evaluation

Datasets and Setup

The approach was evaluated using both simulation and real-world data. Real-world tests featured a B21r robot named "Albert" equipped with 24 sonar sensors. Experiments were conducted in the Sieg Hall at the University of Washington and a laboratory at the University of Freiburg. Simulation runs (50 iterations) provided statistically significant comparisons between the different exploration strategies.

Key Results

Coverage maps produced significantly more accurate representations of corridors and offices compared to standard occupancy grids, particularly when dealing with noisy sonar data.

The B21r robot "Albert" (a) and the resulting coverage maps generated for a corridor (b) and an office environment (c).

Key findings regarding exploration efficiency include:

  • Information Gain (IG) required the fewest measurements to reach target certainty but resulted in the longest travel paths.
  • Closest Location (CL) resulted in short paths but required many redundant measurements.
  • The Hybrid (IG-CL) strategy (with weight $\alpha = 0.3$) provided the optimal balance, achieving low entropy with reasonable path lengths.

Discussion and Future Work

A critical insight of this work is that entropy serves as a superior termination criterion compared to simple scan counting. Some cells require many scans to resolve due to sensor noise or geometry, while others require few; entropy-based exploration handles this variation automatically.

However, the model currently assumes cell independence, a simplification that future work could address by incorporating spatial dependencies. Additionally, while the "IG-WIN" strategy mitigates some computational costs, scaling global information-gain optimization for very large maps remains a challenge. Future applications may include adapting this framework for high-resolution, high-cost sensors like stereo cameras.

Summary updated

BibTeX
@inproceedings{stachniss2003exploring,
  author = {Cyrill Stachniss and Wolfram Burgard},
  title = {{Exploring Unknown Environments with Mobile Robots using Coverage Maps}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure