ite Automata wit an Application

We assume that it is useful for a robot to construct a spatial representation of its environment for naviga-tion purposes. In addition, we assume that robots, like people, make occasional errors in perceiving the spatial features of their environment. Typical perceptual er-rors include confusing two distinct locations or failing to identify the same location seen at different times. We are interested in the consequences of perceptual uncertainty in terms of the time and space required to learn a map with a given accuracy. We measure accu-racy in terms of the probability that the robot correctly identifies a particular underlying spatial configuration. We derive considerable power by providing the robot with routines that allow it to identify landmarks on the basis of local features. We provide a mathematical model of the problem and algorithms that are guaran-teed to learn the underlying spatial configuration for a given class of environments with probability 1- 5 in time polynomial in l/S and some measure of the struc-tural complexity of the environment and the robot’s ability to discern that structure. Our algorithms ap-ply to a variety of environments that can be modeled as labeled graphs or deterministic finite automata