| Robot motion planning has been a central problem of robotics research since its early stages, yet no satisfactory solution has been found to date. The difficulty stems from the fact that the real world is too complex to be modelled accurately. The details that are omitted from a model create uncertainty. More detailed models have less uncertainty, but increase computational complexity; less detailed models may result in incorrect and/or incomplete planners. 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.;Uncertainty makes the execution of motion plans non-deterministic. Sensing is used to help the robot identify its state, but measurement errors interfere with the process of state identification. Reasoning about potential states during plan execution is what makes planning with uncertainty a difficult problem. To keep the complexity of the problem polynomial, we represent all possible states with a limited number of equivalence classes. We present a model of a robot and its workspace, which yields a polynomial, correct, and complete motion planning algorithm. The key idea is the existence of regions in the workspace (landmark regions), where the robot has perfect position sensing and can navigate without error. Outside such regions the robot is bound to control and sensing uncertainty.;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. |
