Robot Evidence Grids  Martin C. Martin and Hans Moravec tech.
report CMU-RI-TR-96-06, Robotics Institute, Carnegie Mellon
University, March, 1996    • Adobe portable document format
(pdf) (779KB)  The evidence grid representation was formulated
at the CMU Mobile Robot Laboratory in 1983 to turn wide angle
range measurements from cheap robot-mounted sonar sensors into
detailed spatial maps. It accumulates diffuse evidence about the
of a grid of small volumes of nearby space from individual
sensor readings into increasingly confident and detailed maps of
a robot's suuroundings. It worked surprisingly well in the 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
with millions, is underway.  This paper presents the
mathematical and probabilistic f