This is the first year of a three-year continuing award. The research is to study computational complexity of adaptive and robust robot motion planning algorithms which can be effective in situations with incomplete information or in dynamically-changing environments. The planner's performance is to adapt as new information is acquired or the environment changes. The research will also consider movement problems with inherent errors in the sensing and movement control, so that the motion planning algorithms must be robust to lack of information on the position of the robot. The emphasis is on the design of algorithms that give provable optimal or near-optimal performance, focusing especially on some less-investigated motion planning problems. The use of massive parallelism will be explored, to speed up the movement planning algorithms. The results should contribute to a more fundamental understanding of the nature of motion planning problems, and ultimately to more robust planning approaches for less structured environments.
