Coping with uncertainty in map learning

In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a representation as a map, and the process of constructing a map from a set of measurements as map learning. In this paper, we develop a framework for describing map-learning problems in which the measurements taken by the robot are subject to known errors. We investigate two approaches to learning maps under such conditions: one based on Valiant's probably approximately correct learning model, and a second based on Rivest Sz Sloan's reliable and probably nearly almost always useful learning model. Both methods deal with the problem of accumulated error in combining local measurements to make global inferences. In the first approach, the effects of accumulated error are eliminated by the use of reliable and probably useful methods for discerning the local properties of space. In the second, the effects of accumulated error are reduced to acceptable levels by repeated exploration of the area to be learned. Finally, we suggest some insights into why certain existing techniques for map learning perform as well as they do.