The Complexity of Fine Motion Planning
Permanent Link(s)
Collections
Author
Natarajan, B. K.
Abstract
We study the complexity of fine motion planning for robots with position measurement and damping. A reduction from fine motion planning with position measurement only to the "classical piano mover's problem" is developed, thereby showing it to be feasible in polynomial time. We then show that deciding the existence of fine motion plans for robots with damping in three dimensional scenes is PSPACE-hard and, with a view to finding the cause for the jump in the complexity, we identify a restricted subclass of the PSPACE-hard problem that is PSPACE-complete. Finally, we show how to restrict this subclass to permit polynomial time algorithms for the problems in it.
Date Issued
1986-02
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-734
Type
technical report