In many applications in mobile robotics, it is important for a robot t
o explore its environment in order to construct a representation of sp
ace useful for guiding movement. We refer to such a representation as
a map, and the process of constructing a map from a set of measurement
s as map learning. In this paper, we develop a framework for describin
g map-learning problems in which the measurements taken by the robot a
re subject to known errors, We investigate approaches to learning maps
under such conditions based on Valiant's probably approximately corre
ct learning model. We focus on the problem of coping with accumulated
error in combining local measurements to make global inferences. In on
e approach, the effects of accumulated error are eliminated by the use
of local sensing methods that never mislead but occasionally fail to
produce an answer. In another approach, the effects of accumulated err
or are reduced to acceptable levels by repeated exploration of the are
a to be learned. We also suggest some insights into why certain existi
ng techniques for map learning perform as well as they do. The learnin
g problems explored in this paper are quite different from most of the
classification and boolean-function learning problems appearing in th
e literature. The methods described, while specific to map learning, s
uggest directions to take in tackling other learning problems.