Using local information in a non-local way \\
for mapping graph-like terrains

This paper appears in the Proceedings of 
Int'l Joint Conference of Artificial Intelliegence,
Chambery, France, Aug. 1993.

Gregory Dudek
Paul Freedman
Souad Hadjres

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 terrains can be fully explored and described
using a single movable marker even if there are no spatial
metrics and almost no sensory ability on the 
part of the robot.  
Here we present an approach to the exploration of unknown terrains
without such a movable marker which is simply based on the structure of the 
world itself.  

Locations in the
world are identified by a non-unique
``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.   
By 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 terrains additional information 
is required).