BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-95-1539
       ENTRY:: January 31, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Reasoning About Uncertainty in Robot Motion Planning
        TYPE:: Thesis
        TYPE:: Technical Report
      AUTHOR:: Lazanas, Anthony
        DATE:: August 1994
       PAGES:: 254
    ABSTRACT:: In this thesis, we investigate the effects of uncertainty on
               the difficulty of robot motion planning, and we study the
               tradeoff between physical and computational complexity. We
               present a formulation of the general robot motion planning
               with uncertainty problem, so that a complete, correct,
               polynomial planner can be derived. The key idea is the
               existence of reduced uncertainty regions in the workspace
               (landmark regions).

               Planning is performed using the preimage backchaining method.
               We extend the standard definition of a ``nondirectional
               preimage'' to the case where a motion command depends on an
               arbitrary number of control parameters. The resulting
               multi-dimensional preimage can be represented with a
               polynomial number of 2-D slices, each computed for a critical
               combination of values of the parameters. We present
               implemented algorithms for one parameter (the commanded
               direction of motion) and for two parameters (the commanded
               direction of motion and the directional uncertainty).

               Experimentation with the algorithm using a real mobile robot
               has been successful. By engineering the workspace, we have
               been able to satisfy all the assumptions of our planning
               model. As a result, the robot has been able to operate for
               long periods of time with no failures.
       NOTES:: [Adminitrivia V1/Prg/19950131]
         END:: STAN//CS-TR-95-1539