Anthony Lazanas, Jean-Claude Latombe
To operate in the real world robots must deal with errors in control and sensing. Achieving goals despite these errors requires complex motion planning and plan monitoring. We present a reduced version of the general problem and a complete planner that solves it in polynomial time. The basic concept underlying this planner is that of a landmark. Within the field of influence of a landmark, robot control and sensing are perfect. Outside any such field control is imperfect and sensing is null. In order to make sure that the above assumptions hold, we may have to specifically engineer the robot workspace. Thus, for the first time, workspace engineering is seen as a means to make planning problems tractable. The planner was implemented and experimental results are presented. An interesting feature of the planner is that it always returns a universal plan in the form of a collection of reaction rules. This plan can be used even when the input problem has no guaranteed solution, or when unexpected events occur during plan execution.