Browse Prior Art Database

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]


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


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
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...