NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS.
Publication
, Journal Article
Canny, J; Reif, J
Published in: Annual Symposium on Foundations of Computer Science (Proceedings)
January 1, 1987
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 Scholars
Published In
Annual Symposium on Foundations of Computer Science (Proceedings)
DOI
ISSN
0272-5428
Publication Date
January 1, 1987
Start / End Page
49 / 60
Citation
APA
Chicago
ICMJE
MLA
NLM
Canny, J., & Reif, J. (1987). NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS. Annual Symposium on Foundations of Computer Science (Proceedings), 49–60. https://doi.org/10.1109/sfcs.1987.42
Canny, J., and J. Reif. “NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS.” Annual Symposium on Foundations of Computer Science (Proceedings), January 1, 1987, 49–60. https://doi.org/10.1109/sfcs.1987.42.
Canny J, Reif J. NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS. Annual Symposium on Foundations of Computer Science (Proceedings). 1987 Jan 1;49–60.
Canny, J., and J. Reif. “NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS.” Annual Symposium on Foundations of Computer Science (Proceedings), Jan. 1987, pp. 49–60. Scopus, doi:10.1109/sfcs.1987.42.
Canny J, Reif J. NEW LOWER BOUND TECHNIQUES FOR ROBOT MOTION PLANNING PROBLEMS. Annual Symposium on Foundations of Computer Science (Proceedings). 1987 Jan 1;49–60.
Published In
Annual Symposium on Foundations of Computer Science (Proceedings)
DOI
ISSN
0272-5428
Publication Date
January 1, 1987
Start / End Page
49 / 60