Reducing Multiple Object Motion Planning to Graph Searching
John E. Hopcroft, Gordon Wilfong · SIAM Journal on Computing · 1986
The motion planning problem for multiple objects is studied where an object is a 2-dimensional region whose sides are line segments parallel to the axes of ${\bf R}^2 $ and translations are the only motions allowed. Towards this end we analyze the structure of configuration space, the space of points that correspond to positions of the objects. In particular, we consider CONNECTED, the set of all points in configuration space that correspond to configurations of the objects where the objects form one connected component. We show that CONNECTED consists of faces of various dimensions such that if there is a path in CONNECTED between two 0-dimensional faces (vertices) of CONNECTED then there is a path between them along 1-dimensional faces (edges) of CONNECTED. It is known that if there is a motion between two configurations of CONNECTED then there is a path in CONNECTED between the configurations. Thus the existence of a motion between two vertices of CONNECTED implies a motion corresponding to a path along edges of CONNECTED. Hence the motion planning problem is reduced from a search of a high dimensional space to a graph searching problem. From this result it is shown that motion planning for rectangles in a rectangular boundary is in PSPACE. Since it is known that the problem is PSPACE-hard, we conclude it is a PSPACE-complete problem.