Using Local Information in a Non-Local Way for Mapping Graph-Like Worlds

Abstract

This paper describes a technique whereby an autonomous agent such as a mobile robot can explore an unknown environment and make a topological map of it. It is assumed that the environment can be represented as a graph, that is, as a fixed set of discrete locations or regions with an ordered set of paths between them. In previous work, it has been shown that such worlds can be fully explored and described using a single movable marker even if there are no spatial metrics and almost. no sensory abil' ity on the part of the robot.. Here we present an approach to the explora t.ion of nnkrrown worlds without such a movable marker which is simp ly based on the structure of the world itself . Locations in the worlrl are identified by a nonunique "signature" that serves as an abstraction for a percept that might. be obtained from a robotic sensor. While the signature of any single location may not be unique, under appropriate conditions the distinctiveness of a particular set of signatures in a neighborhood increases with neighborhood size. 11y using a collection of non-unique local signatures we can thereby construct an "extended" signature that uniquely determines the robot's position (although in certain degenerate worlds additional information is required).