Browse Prior Art Database

ON THE COMPLEXITY OF MOTION PLANNING FOR MULTIPLE INDEPENDENT OBJECTS; PSPACE HARDNESS OF THE "WAREHOUSEMAN'S PROBLEM"

IP.com Disclosure Number: IPCOM000128187D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 13 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

J.E. Hopcroft: AUTHOR [+4]

Abstract

Coordinated motion planning for a large number of three dimensional objects in the presence of obstacles is a computational problem whose complexity it seems important to calibrate. In this paper we show that even the restricted 2- 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 lead researchers to consider more tractable restricted classes of motion problems of practical interest. M Work an this paper by the first author has been supported in pat by National Science Foundation Grant hfCF 81-01220. Work by the second and third authors has been supported in part by Office of Naval Research Grant N00014-82-K-0381, by a Grant from the U.S.-Israeli Binational Science Foundation, and by Cants from the Digital Equipment Corporation and the Sloan Foundation.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON THE COMPLEXITY OF MOTION PLANNING FOR MULTIPLE INDEPENDENT OBJECTS; PSPACE HARDNESS OF THE "WAREHOUSEMAN'S PROBLEM"

by J.E. Hopcroft J.T. Schwartz

M. Sharir Technical Report No. 103 Robotics Report No. 14 February, ON THE COMPLEXITY OF MOTION PLANNING FOR MULTIPLE INDEPENDENT OBJECTS; PSPACE HARDNESS OF THE "WAREHOUSEMAN'S PROBLEM".(') J.E. Hopcrot Computer Science Department, Cornell University J.T. Schwartz Computer Science Department, Courant Institute of Mathematical Sciences and AS. Sharir School of Mathematical Sciences Tel Aviv University

ABSTRACT

Coordinated motion planning for a large number of three dimensional objects in the presence of obstacles is a computational problem whose complexity it seems important to calibrate. In this paper we show that even the restricted 2- 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 lead researchers to consider more tractable restricted classes of motion problems of practical interest. M Work an this paper by the first author has been supported in pat by National Science Foundation Grant hfCF 81-01220. Work by the second and third authors has been supported in part by Office of Naval Research Grant N00014-82-K- 0381, by a Grant from the U.S.-Israeli Binational Science Foundation, and by Cants from the Digital Equipment Corporation and the Sloan Foundation. .2-

1. Introduction

In this paper we prove that the coordinated motion planning problem for a collection of dis-joint 2-dimensional rectangular objects constrained to move within a 2-dimensional rectangular box is PSPACE-hard. The problem considered can be defined as follows: Civen an initial and a final configuration of the objects in question, determine whether there exists a continuous coordinated motion of the objects between the initial and final configurations during which they do not penetrate either the 'walls' of the enclosing box, or each other. Previous work on the complexity of motion planning problems of this sort was begun in [Re], where the motion planning problem for a certain kind of many-jointed 3-D system con-strained to move within a complex system of narrow tunnels was shown to be PSPACE-hard It was subsequently shown in [SSl] that the general motion-planning problem can be solved in poly-nomial time, provided that the number of degrees of freedom of the moving body or bodies is held fixed (and provided that the system is 'algebraic'; see [SSi] for detail). This motivates our attempt to find moving systems (necessarily involving arbitrarily many degrees of freedom) whose geometry is as simple as possible, but for which the motion planning problem is still PSPACE-hard. A simple class of systems having these properties is described in [H7W]; it consists of a fam-ily of systems consisting of many links, all lying in the...