An Efficient Algorithm for One-Step Planar Compliant
Motion Planning with Uncertainty
Amy Judith Briggs
Abstract
Uncertainty in the execution of robot motion plans must be accounted
for in the geometric computations from which plans are obtained,
especially in the case where position sensing is inaccurate. We give
an O(n^2 log n) algorithm to find a single commanded motion
direction that will guarantee a successful motion in the plane from a
specified start to a specified goal whenever such a one-step motion is
possible. The plans account for uncertainty in the start position and
in robot control, and anticipate that the robot may stick on or slide
along obstacle surfaces with which it comes in contact. This bound
improves on the best previous bound by a quadratic factor, and is
achieved in part by a new analysis of the geometric complexity of the
backprojection of the goal as a function of commanded motion
direction.
A gzip'ed postscript version of this paper
is available.
Back to Amy Briggs' home page