!! Occupancy Maps
MINERVA: Carnegie Mellon's Robotic Tourguide Project Minerva's Image

Occupancy Maps: Where May I Go?

Minerva learns. Among other things, she has successfully acquired a map of her environment. In the following map, which is approximately 65 by 45 meters in size, the color indicates the (subjective) degree of occupancy: dark regions are likely to be occupied, whereas bright regions are most likely free. The blue terrain is plainly unexplored. This map was acquired by maneuvering Minerva through the museum for a few minutes.

Occupancy Map of the Museum

Mapping is a chicken-and-egg problem. If one knew the exact location of the robot beforehand, one could relatively easily determine the location of all obstacles. However, drift and slippage induce error into dead-reckoning, which quickly grows huge. If one knew the location of the obstacles, on the other hand, Minerva's localization routine could be applied to determine the robot's position. Combined localization and mapping, however, is by many considered the holy grail of mobile robotics.

Minerva approaches this problem using a statistical approach. She searches for the most likely map given the data (odometry readings and laser scans). To manage the enormous search space, characteristic for probabilistic methods in high-dimensional space, the "EM algorithm" is employed. EM quickly finds local maxima in likelihood space--maxima that usually are sufficiently close to the correct map. Additional statistical methods are employed to filter out noise in individual laser measurements to separate the occupied from the free.

More information on Minerva's mapping module can be found in the following papers:

Home The Java-Based Image Stream About this project