Browse Prior Art Database

COORDINATING THE MOTION OF SEVERAL DISCS

IP.com Disclosure Number: IPCOM000149381D
Original Publication Date: 1984-Feb-29
Included in the Prior Art Database: 2007-Apr-01
Document File: 28 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Yap, Chee K.: AUTHOR [+2]

Abstract

Chee K. Yap

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 28

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.

[This page contains 1 picture or other non-text object]

Page 2 of 28

[This page contains 1 picture or other non-text object]

Page 3 of 28

Coonlinating the Motion of Severnl Diacs Chee PC. Yap

Courant Institute of Mathematical Sciences Ncw York University

251, Mercer Street

New York, NY 10012

Wc give an 0(1t2) and m 0 ( n 3 tirs algorithm far the prcbkrn of

coordinating the motion of two and t h e discs (reqxctivdy) moving amidst plygonal obstacles. Our a p c h
is based on the ide3 af rctrac- tion, a d improves previous algurithms by Schwartz and Sharir.

Key Wards: mbotiu, motion pladng, coon;linated motion, efficient algorithms, retrac- don appmach.

[This page contains 1 picture or other non-text object]

Page 4 of 28

Various cornputatid problems arise in mixtics in *k

                                  genczl am of motion plan-
ning [Bra]. Although rn:~tian phmhg problems have ken studied for m y
years from

tbe viewpoiat of heuristic programming or arrifidal inteMge=~e (~2.
M) and mxhmics (eg. [PI), it is only nxerirlj that algari-c and compkxity themetic kchiqucs have been brought to bear. Fur recent pgms dong this h,

sce [SSl,SSZ,WW,QY,O~.

The many body pmbkm b ~ 9 2 ~ 3
phmhg
considered in this ppcr is p o d as follcnvs: Given rn bdies Pt = (B1, B2, . . . , Bin), a stt of obstack S, an initial ph~naent p = (p1,p2,. . . ,pm) and a w t
q = (91,. . . , 4,) of& probh istopfinz(~~motimdBfrarsgtoq(if~e,nists).

A variety of problcms arise &pending oa whether ox consi&;rs this qucstim in two or

tlrree clhensions, whether each Bi is ridd or jointed, whether B is fixed or varies with the input, and whether the obstacles S are aswmed to be plykdral m have mare general shapes. The results of [S]
imply that for my fixed B, whex the bodies and obstacles
are h n M
by algebrzic s& with bounded &p,
the problem is p01ynomh.l time Jolv,lbL. However, for e& specific B, it mmim of inten% to obtain algorithm more
efficient than that which follows from tbc general mlts in [SS2].

   The case where m = 1 has been extensively studied (see the papers cited above). The case m > 1 is relatively new and [SS3] appean to be the first purely algorithmic study of this sort. Note that the only mutual amstmint among the bod'= in El in a 'am-
dinated motion' is nonallision among them (compare this with the mutual constraints among the different links of a jainted mbt arm). An instnncc of camdination is the

important but little-understood problem of making two rcfwt arms cooperate on a task. Another example is that of amdinating many roving rob...