Landmark-Based Robot Navigation

摘要

This paper describes a reduced version of the general planning problem in thepresence of uncertainty and a complete polynomial algorithm solving it. The planner computes a guaranteed plan (for given uncertainty bounds) by backchaining non-directional preimages of the goal until one fully contains the set of possible initial positions of the robot. The planner assumes that landmarks are scattered across the workspace, that robot control and sensing are perfect within the fields of influence of these landmarks, 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.