A path-space search algorithm for motion planning with uncertainties

This paper describes an algorithm for adjusting a robot motion plan in order to make it feasible in spite of control and sensing uncertainties in the robot configuration. The type of motion plan considered consists of a nominal commanded path, augmented by sensing mode specifications. The algorithm uses a bounding-set representation of uncertainties, which is also described. The control uncertainty is history independent, but the sensing uncertainty at one point in a plan depends on the prior sensing actions and the path traversed. The algorithm is a path-space algorithm, because it adjusts the entire plan simultaneously as it carries out the search