click image to enlarge

1984
Occupancy Grid Maps: Sonar and Simple Stereo

Robot perception, mapping and navigation work begun at Stanford University continued at the Carnegie Mellon University Mobile Robot Lab, founded by Moravec in 1980. A very inexpensive sonar rangefinder, developed for Polaroid camera autofocus, became available for robot use. It made an ideal obstacle sensor, but was difficult to use for mapping and navigation because, unlike stereoscopic ranging, its 30° wide beams did not pinpoint object locations.

To solve the problem we invented a new approach, that mapped locations rather than objects. The robot’s space was subdivided into a grid. Each grid cell accumulated sensor evidence as to whether it was occupied or not. A single sonar range weakly increased the occupancy evidence over a 30° arc of cells, and strongly decreased it in the wedge from the sensor to the range arc. A single sonar echo did not pinpoint location, but overlapping ones from various points of view trimmed away incorrect portions of each others range arcs, and reinforced consistent portions. The result was surprisingly good. Our first grid program, with ring of 24 Polaroid sonars pinged every 1.5 meters, seemed always to safely guide our robot across our lab (seen above: obstacles varied from run to run). Besides disambiguating sonar beams, the grid approach systematically mitigated errors. It also provided a way to fuse data from different sensors, as briefly shown combining ranges from sonar and a simple stereo vision program, revealing some features neither individual sensor saw well. (In the maps, small dots are initial evidence values indicating “unknown,” lighter dots and white are “empty,” darker marks “occupied.” Labels and outlines for some contents were added by hand.)