Abstract
Coordinated motion planning for a large number af three-di mensional objects in the presence of obstacles is a computa tional problem whose complexity is important to calibrate. In this paper we show that even the restricted two-dimensional problem for arbitrarily many rectangles in a rectangular region is PSPACE-hard. This result should be viewed as a guide to the difficulty, of the general problem and should lead researchers to consider more tractable restricted classes of motion problems of practical interest.
Get full access to this article
View all access options for this article.
