The Complexity of Fine Motion Planning

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.