Browse Prior Art Database

COORDINATING THE MOTION OF SEVERAL DISCS

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

Publishing Venue

Software Patent Institute

Related People

Chee K. Yap: AUTHOR [+3]

Abstract

We give an [Equation ommitted] algorithm for the problem of coordinating the motion of two and three discs (r..spccdvcly) moving amidst polygonal obstacles. Our approach is based on the idea of retrac-tion, ::nd improves previous algorithms by Schwartz and Shark. Key Words: robotics, motion planning, coordinated motion, efficient algorithms, retrac-tion approach.

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

Page 1 of 22

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

COORDINATING THE MOTION OF SEVERAL DISCS

Chee K. Yap

----------------------------------------

Technical Report No. 105 Robotics Report No. 16 February, 1984 Work on this paper has been supported in part by Office of Naval Research Grant N00014-82-K-0381, and by grants from the Digital Equipment Corporation,. the Sloan Foundation, the System Develop-ment Foundation, and the IBM Corporation. Coordinating the Motion of Several Discs

* Chee K. Yap Courant Institute of Mathematical Sciences New York University ' 251, Mercer Street New York, NY 10012

ABSTRACT

We give an

(Equation Omitted)

algorithm for the problem of coordinating the motion of two and three discs (r..spccdvcly) moving amidst polygonal obstacles. Our approach is based on the idea of retrac-tion, ::nd improves previous algorithms by Schwartz and Shark. Key Words: robotics, motion planning, coordinated motion, efficient algorithms, retrac-tion approach.

1. Introduction

Various eomputationr1 problems arise in robotics in the gene: ^.l area of motion plan- ning [Bra]. Although motion planning problems have been studied for many years from the viewpoint of heuristic programming or artificial intelligence (eg. [N]) and mechanics (cg. [P]), it is only recently that algorithmic and complexity theoretic techniques have been brought to bear. For recent progress along this line, see [SS1,SS2,HJVV,OY,OSY]. The many body problem 9n motion planning considered in this paper is posed as follows: Given m bodies

(Equation Omitted)

a set of obstacles S, an initial placement

(Equation Omitted)

and a final plant

(Equation Omitted)

of B, the problen is to plan a (coordinated) motion ,^.f B from p to q (if one exists). A variety of problems arise &pending on whether ane considers this question in two or three dimensions, whether each Bi is rigid or jointed, whether B is fused or varies with the input, and whether the

New York University Page 1 Dec 31, 1984

Page 2 of 22

COORDINATING THE MOTION OF SEVERAL DISCS

obstacles S are assumed to be polyhedral or have mare general shapes. The results of [SS2] imply that for any fixed B, where, the bodies and obstacles are bounded by algebraic surfaces with bound degrees, the problem is polynomial time solvable. However, for each specific B, it remains of interest to obtain algorithms more efficient than that which follows from the general results in [SS2]. The case where rn = l has been extensively studied (see the papers cited above). The case m > 1 is relatively new and [SS3]appears to be the first purely algorithmic study of this sort. Note that the only mutual constraint among the bodies in B in a 'coor-dinated motion' is non-collision among them (compare this with the mutual constraints among the different links of a jointed robot arm). An instance of coordination is the =important but little- understood problem of making two robot arms cooperate on a task. Another example is that of c...