Anthony Lazanas and Jean-Claude Lotombe
This paper describes a reduced version of the general motion planning problem in the presence of uncertainty and a complete polynomial algorithm solving it. This algorithm computes a guaranteed plan by backchaining non-directional preimages of the goal until one fully contains the set of possible initial positions of the robot. It 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 satisfaction of these assumptions 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. The algorithm was implemented in an operational planner and run on many examples. Non-implemented extensions of the planner are also discussed.