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.
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: