Complexity of the Generalized Mover's Problem.

Abstract

This paper concerns the problem of planning a sequence of movements of linked polyhedra through 3 dimensional Euclidean space, avoiding contact with a fixed set of polyhedra obstacles. We prove this generalized mover's problem is polynomial space hard. Our proof provides strong evidence that robot movement planning is computationally intractable, i.e., any algorithm requires time growing exponentially with the number of degrees of freedom. Keywords: Robotics; Mover's problem; Obstacle avoidence; PSPACE; Combinatorial; Geometry; Collision avoidence.