To Stephen D. Scott's home page
Abstract
Developing the ability to recognize a landmark from a visual image of a robot's current location is a fundamental problem in robotics. We consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is a configuration of k points on the real line. Each instance is a configuration of n points on the real line, where it is labeled according to whether or not it visually resembles the target pattern. To capture the notion of visual resemblance we use the Hausdorff metric. Informally, two geometric patterns P and Q resemble each other under the Hausdorff metric if every point on one pattern is ``close'' to some point on the other pattern. We relate the concept class of geometric patterns to the landmark matching problem and then present a polynomial-time algorithm that PAC-learns the class of one-dimensional geometric patterns. An interesting feature of this problem is that the target concept is specified by a k-tuple of points on the real line, while the instances are specified by n-tuple of points on the real line where n is potentially much larger than k. Although there are some important distinctions, in some sense, our work illustrates a concept class in a continuous domain in which a large fraction of each instance can be viewed as ``irrelevant''. As in previous work on learning with a large number of irrelevant attributes in the Boolean domain, our algorithm's sample complexity depends polynomially on k and lg n. We also present some experimental results on how our algorithm performs.Keywords: PAC learning, landmark matching, robot navigation
To Stephen D. Scott's home page
Last modified 06 June 2000.