Cj. Taylor et Dj. Kriegman, VISION-BASED MOTION PLANNING AND EXPLORATION ALGORITHMS FOR MOBILE ROBOTS, IEEE transactions on robotics and automation, 14(3), 1998, pp. 417-426
This paper considers the problem of systematically exploring an unfami
liar environment in search of one or more recognizable targets. The pr
oposed exploration algorithm is based on a novel representation of env
ironments containing visual landmarks called the boundary place graph.
This representation records the set of recognizable objects (landmark
s) that are visible from the boundary of each configuration space obst
acle. No metric information about the scene geometry is recorded nor a
re explicit prescriptions for moving between places stored. The explor
ation algorithm constructs the boundary place graph incrementally from
sensor data. Once the robot has completely explored an environment, i
t can use the constructed representation to carry out further navigati
on tasks. In order to precisely characterize the set of environments i
n which this algorithm is expected to succeed, we provide a necessary
and sufficient condition under which the algorithm is guaranteed to di
scover all landmarks. This algorithm has been implemented on our mobil
e robot platform RT, 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 representatio
ns of the environment.