Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

ON THE COMBINATORIAL COMPLEXITY OF MOTION COORDINATION

IP.com Disclosure Number: IPCOM000128225D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 18 page(s) / 48K

Publishing Venue

Software Patent Institute

Related People

Paul Spirakis: AUTHOR [+4]

Abstract

We investigate the complexity of the problem of coordinating the motion of many planar rigid objects in a two dimensional space. Each object has a simple geometrical description (it is a box or a circle). The number of objects to be moved is part of the problem size. The plane where objects.move is partitioned into two regions: The region of forbidden points, being a finite union of areas each bounded by a polygonal line, and its complement. During motion, objects are not allowed to overlap or to intersect the region of forbidden points, but they are allowed to be in contact with the boundary of obstacles or other objects. We analyze several variants of the above problem of motion planning and prove that they are ATP-hard, in the strong sense. We also consider simple combinatorial planar graph-and-pebble models which capture certain non-geometric aspects of coordinated motion. We provide an algorithm for planning the motion of k pebbles in an n-vertex planar graph, which is 0(nk). We also show that coordination of motion of n-1 distinct pebbles in an n-vertex graph, from a set of n-1 distinct initial to n-1 distinct final positions, can be decided and planned in polynomial time in n. Finally, we show that certain problems of planning the motion of many pebbles, when the motion is nonsymmetric, or when the final positions are required to satisfy a combinatorial property, are NP-hard in the strong sense.

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

Page 1 of 18

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON THE COMBINATORIAL COMPLEXITY OF MOTION COORDINATION

by

Paul Spirakis & Chee Yap Technical Report No. 76 Robotics Report No. April, 1983

Abstract

We investigate the complexity of the problem of coordinating the motion of many planar rigid objects in a two dimensional space. Each object has a simple geometrical description (it is a box or a circle). The number of objects to be moved is part of the problem size. The plane where objects.move is partitioned into two regions: The region of forbidden points, being a finite union of areas each bounded by a polygonal line, and its complement. During motion, objects are not allowed to overlap or to intersect the region of forbidden points, but they are allowed to be in contact with the boundary of obstacles or other objects. We analyze several variants of the above problem of motion planning and prove that they are ATP-hard, in the strong sense. We also consider simple combinatorial planar graph-and-pebble models which capture certain non- geometric aspects of coordinated motion. We provide an algorithm for planning the motion of k pebbles in an n-vertex planar graph, which is 0(nk). We also show that coordination of motion of n-1 distinct pebbles in an n-vertex graph, from a set of n-1 distinct initial to n-1 distinct final positions, can be decided and planned in polynomial time in n. Finally, we show that certain problems of planning the motion of many pebbles, when the motion is nonsymmetric, or when the final positions are required to satisfy a combinatorial property, are NP-hard in the strong sense.

1. Introduction

1.1. The problem

This paper examines the complexity of the problem of planning the motion of many simple rigid objects in the plane. The objects are either boxes or circles. The number of objects to be moved is part of the problem size. The plane where objects move is partitioned into two regions : (a) The region F of forbidden points, being a finite union of (not necessarily convex or finite) areas Fi, each of which is bounded by a polygonal line. (b) The complement of F, called the region of legal points. A position, p(Oj), of an object Oj is a valid position if the area of

(Equation Omitted)

is zero, and also if the area of

(Equation Omitted)

is zero for each k 0 j and where p(Ok) is the position of object Ok at some instant of the motion.
(i.e. we allow objects to come in contact with walls - the boundaries of F - or other objects during

New York University Page 1 Dec 31, 1983

Page 2 of 18

ON THE COMBINATORIAL COMPLEXITY OF MOTION COORDINATION

motion, but we do not allow them to be able to enter into a wall or overlap with other objects). In some of the problems to be examined F can be empty or may have a particularly simple geometric description (e.g. the number of the polygonal lines is a small constant). In addition, we are given an initial set I of valid positions,

(Equation Omitted)

is the initial...