NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS.
Techniques for establishing lower bounds in robot motion planning problems are presented. The method is first applied to the 3-D shortest-path problem and then extended to compliant motion planning with uncertainty in control. Specifically, a point in three dimensions is considered that is commanded to move in a straight line, but whose actual motion may differ from the commanded motion, possibly involving sliding against obstacles. Given that the point initially lies in some start region, the problem of finding a sequence of commanded velocities that is guaranteed to move the point to the goal is shown to be nondeterministic exponential-time hard, thus making it a provably intractable problem.
Start / End Page
International Standard Serial Number (ISSN)