Multiple object motion planning (robotics)
Gordon Wilfong · 1984
In this work we study the motion planning problem for multiple objects. 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. First it is shown that for two or three dimensional objects, a motion between configurations in CONNECTED implies a motion in CONNECTED between them. We next consider the case of translational motions of objects whose faces are parallel to the axes of R('2). 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. Combining the two results we conclude that the existence of a motion between two vertices of CONNECTED implies a motion corresponding to a path along edges of CONNECTED. Hence we have reduced the motion planning problem 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. It is known that the problem is PSPACE-hard and so we conclude that the problem is PSPACE-complete. Searching the graph of vertices and edges of CONNECTED for a path has a prohibitive worse-case complexity because of the large number of vertices and edges. However, if the search generates edges and vertices only as they are needed, a practical and efficient algorithm may be possible using some effective heuristic.