Robot Evidence
Grids
Martin Martin and Hans Moravec
Carnegie Mellon University
Robotics Institute
March 1996
Abstract
The evidence
grid representation was formulated at the CMU Mobile Robot Laboratory
in 1983 to turn wide angle range measurements from cheap mobile
robot-mounted sonar sensors into detailed spatial maps. It
accumulates diffuse evidence about the occupancy of a grid of small
volumes of nearby space from individual sensor readings into
increasingly confident and detailed maps of a robot's surroundings. It
worked surprisingly well in first implementation for sonar navigation
in cluttered rooms. In the past decade its use has been extended to
range measurements from stereoscopic vision and other sensors, sonar
in very difficult specular environments, and other contexts. The most
dramatic extension yet, from 2D grid maps with thousands of cells to
3D grids with millions, is underway.
This paper
presents the mathematical and probabilistic framework we now use for
evidence grids. It gives the history of the grid representation, and
its relation to other spatial modeling approaches. It discusses
earlier formulations and their limitations, and documents several
extensions. A list of open issues and research topics is then
presented, followed by a literature survey.
Download the report
1.2MB PDF file
1MB gzipped postscript file