Camillo J. Taylor,
GRASP Lab, University of Pennsylvania - [home]
This paper considers the problem
of systematically exploring an unfamiliar environment in search
of one or more recognizable targets.
The proposed exploration algorithm is based on a novel representation
of environments containing visual landmarks called the boundary
place graph. This representation records the set of recognizable
objects (landmarks) that are visible from the boundary of each
configuration space obstacle. No metric information about the
scene geometry is recorded nor are explicit prescriptions for
moving between places stored. The exploration algorithm constructs
the boundary place graph incrementally from sensor data. Once
the robot has
completely explored an environment, it can use the constructed
representation to carry out further navigation tasks. In order
to precisely characterize the set of environments in which this
algorithm is expected to succeed, we provide a necessary and sufficient
condition under which the algorithm is guaranteed to discover
all of the landmarks. This algorithm has been implemented on our
mobile robot platform RJ, and results from these experiments are
presented. Importantly, this research demonstrates that it is
possible to design and implement provably correct exploration
and navigation algorithms that do not require global positioning
systems or metric representations of the environment.