On the complexity of reachability and motion planning questions (extended abstract)

Abstract

In this paper we consider from a theoretical viewpoint the complexity of some reachability and motion planning questions. Specifically, we are interested in determining which generalizations of the basic mover's problem result in computationally intractable problems. It has been shown that for any set of motion-planning problems with bounded degree of freedom, there is a polynomial-time algorithm to solve the motion-planning problem (although the degree of the polynomial may be large), but the two most basic generalizations to the problem, multiple movable obstacles and conformable objects, result in much harder problems. It has been shown that the warehouseman's problem is P-space hard: in this paper we show that the reachability problem for one of the simplest types of conformable objects, a two-dimensional linear (“robot arm”) linkage, is P-space complete. In addition, we demonstrate some motion-planning problems that take exponential time.