Computer Science

Coping with Uncertainty in Map Learning

Document Type

Article

Abstract

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 approaches to learning maps under such conditions based on Valiant's probably approximately correct learning model. We focus on the problem of coping with accumulated error in combining local measurements to make global inferences. In one 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 error are reduced to acceptable levels by repeated exploration of the area to be learned. We also suggest some insights into why certain existing techniques for map learning perform as well as they do. The learning problems explored in this paper are quite different from most of the classification and boolean-function learning problems appearing in the literature. The methods described, while specific to map learning, suggest directions to take in tackling other learning problems.

Publication Title

Machine Learning

Publication Date

1997

Volume

29

Issue

1

First Page

65

Last Page

88

ISSN

0885-6125

DOI

10.1023/A:1007418008480

Keywords

inference, learning, maps, graphs, uncertainty, noise

APA Citation

Basye, K., Dean, T., & Vitter, J. S. (1997). Coping with uncertainty in map learning. Machine Learning, 29, 65-88.

Link to Full Text

Share

COinS