Mapping in unknown graph-like worlds 

Gregory Dudek, Paul Freedman, Souad Hadjres 

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 difficulty to assure, 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 which 
determines the robot's position (although in certain degenerate worlds 
additional information is required). We describe the exploration tree: 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.