MAPPING IN UNKNOWN GRAPH-LIKE WORLDS

We consider the problem of constructing a map of an unknown environmen t by an autonomous agent such as a mobile robot. Because accurate posi tional information is often difficult to ensure, we consider the probl em of exploration in the absence of metric (positional) information. W orlds are represented by graphs (not necessarily planar) consisting of a fixed number of discrete places linked by bidirectional paths. We a ssume the robot can consistently enumerate the edges leaving a vertex (that is, it can assign a cyclic ordering). A mobile robot is assigned the task of creating a topological map, i.e. a graph-like representat ion of the places in the world and their connectivity, by moving from place to place along the paths it encounters. It can detect edges and count them, but cannot directly sense the labels associated with a pla ce or an edge. In principle, this type of representation could be used for non-spatial environments such as computer networks. We present an approach to the exploration of unknown environments for which local s ensing information alone is insufficient to distinguish distinct place s, based simply on the structure of the world itself. Places are ident ified by a non-unique signature and by using a collection of such non- unique local signatures, an extended signature may be constructed that determines the robot's position (although in certain ''degenerate'' w orlds additional information is required). We describe the ''explorati on tree'' as a representation of a collection of alternative descripti ons of the environment. In addition, heuristics are presented that tan accelerate the search for the correct world model. (C) 1996 John Wile y & Sons, Inc.