eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/6455
Title:  Reducing Multiple Object Motion Planning To Graph Searching 
Authors:  Hopcroft, John E. Wilfong, Gordon 
Keywords:  computer science technical report 
Issue Date:  Jun1984 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84616 
Abstract:  In this paper we study the motion planning problem for multiple objects where an object is a 2dimensional body whose faces are line segments parallel to the axes of $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 0dimensional faces (vertices) of CONNECTED then there is a path between them along 1dimensional faces (edges) of CONNECTED. It is known that if there is a motion between the configurations. Thus by the result of this paper 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. Searching the graph of vertices and edges of CONNECTED for a path has a prohibitive worsecase 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. 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 PSPACEhard we conclude it is a PSPACEcomplete problem. 
URI:  http://hdl.handle.net/1813/6455 
Appears in Collections:  Computer Science Technical Reports

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
