Landmark-Based Robot Navigation

Achieving goals despite uncertainty in control and sensing may require robots to perform complicated motion planning and execution monitoring. This paper describes a reduced version of the general planning problem in the presence of uncertainty and a complete polynomial algorithm solving it. The planar computes a guaranteed plan (for given uncertainty bounds) by backchaining omnidirectional backprojections of the goal until the set of possible initial positions of the robot is fully contained. The algorithm assumes that landmarks are scattered across the workspace, that robot control and position sensing are perfect within the fields of influence of these landmarks (the regions in which the landmarks can be sensed by the robot), and that control is imperfect and sensing null outside these fields. The polynomiality and completeness of the algorithm derive from these simplifying assumptions, whose satisfaction may require the robot and/or its workspace to be specifically engineered. This leads us to view robot/workspace engineering as a means to make planning problems tractable. A computer program embedding the planner was implemented, along with navigation techniques and a robot simulator. Several examples run with this program are presented in this paper. Nonimplemented extensions of the planner are also discussed.This research was partially funded by DARPA contract DAAA21-89-C0002 and ONR Contract N00014-92-J-1809.