Report Number: CS-TR-95-1539
Institution: Stanford University, Department of Computer Science
Title: Reasoning About Uncertainty in Robot Motion Planning
Author: Lazanas, Anthony
Date: August 1994
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/95/1539/CS-TR-95-1539.pdf