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:
- S. Thrun, D. Fox, and W. Burgard, 1998. A Probabilistic Approach to Concurrent Mapping
and Localization for Mobile Robots. Machine Learning 31, 29--53
and Autonomous Robots 5, 253--271, (joint issue).
- S. Thrun. Bayesian Landmark Learning for Mobile Robot Localization, to appear in Machine Learning
- S. Thrun, 1998. Learning Metric-Topological Maps for Indoor Mobile Robot Navigation, AI Journal 99(1), 21--71.
- S. Thrun, 1997. To Know or Not To Know: On the Utility of Models in Mobile Robotics. AI Magazine, 18:1, AAAI, Spring 1997.
- S. Thrun, S. Gutmann, D.Fox, W. Burgard, and B. Kuipers, 1998. Integrating Topological and Metric
Maps for Mobile Robot Navigation: A Statistical Approach. To appear at AAAI-98.
- S. Thrun, 1993. Exploration and Model
Building in Mobile Robot Domains. In Proceedings of the IEEE
International Conference on Neural Networks, IEEE Neural Network
Council.