NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS.

Published

Journal Article

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.

Duke Authors

Cited Authors

  • Canny, J; Reif, J

Published Date

  • December 1, 1987

Published In

Start / End Page

  • 49 - 60

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus