Mapping in unknown graph-like worlds

摘要

We consider the problem of constructing a map of an unknown environment by an autonomous agent such as a mobile robot. Because accurate positional information is often difficult to ensure, we consider the problem of exploration in the absence of metric (positional) information. Worlds are represented by graphs (not necessarily planar) consisting of a fixed number of discrete places linked by bidirectional paths. We assume 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 representation 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 place 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 sensing information alone is insufficient to distinguish distinct places, based simply on the structure of the world itself. Places are identified 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” worlds additional information is required). We describe the “exploration tree” as a representation of a collection of alternative descriptions of the environment. In addition, heuristics are presented that can accelerate the search for the correct world model. © 1996 John Wiley & Sons, Inc.