A "retraction" method for planning the motion of a disc

Colm Ó'Dúnlaing; Chee K. Yap

doi:10.1016/0196-6774(85)90021-5

A "retraction" method for planning the motion of a disc

Colm Ó'Dúnlaing, Chee K. Yap

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalized Voronoi diagram, and reduces the search for a collision-free continuous motion to a search for a connected path along the edges of such a diagram. This approach yields an O(n log n) algorithm for planning an obstacle-avoiding motion of a single circular disc amid polygonal obstacles. Later papers will show that extensions of the approach can solve other motion-planning problems, including those of moving a straight line segment or several coordinated discs in the plane amid polygonal obstacles.

Original language	English (US)
Pages (from-to)	104-111
Number of pages	8
Journal	Journal of Algorithms
Volume	6
Issue number	1
DOIs	https://doi.org/10.1016/0196-6774(85)90021-5
State	Published - Mar 1985

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/0196-6774(85)90021-5

Cite this

@article{4a2977c700db4516b0835bb1f9cf52c9,

title = "A {"}retraction{"} method for planning the motion of a disc",

abstract = "A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalized Voronoi diagram, and reduces the search for a collision-free continuous motion to a search for a connected path along the edges of such a diagram. This approach yields an O(n log n) algorithm for planning an obstacle-avoiding motion of a single circular disc amid polygonal obstacles. Later papers will show that extensions of the approach can solve other motion-planning problems, including those of moving a straight line segment or several coordinated discs in the plane amid polygonal obstacles.",

author = "Colm {\'O}'D{\'u}nlaing and Yap, {Chee K.}",

note = "Funding Information: was supported in part by the ONR under Contract NOOO14-82-K-0381.",

year = "1985",

month = mar,

doi = "10.1016/0196-6774(85)90021-5",

language = "English (US)",

volume = "6",

pages = "104--111",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - A "retraction" method for planning the motion of a disc

AU - Ó'Dúnlaing, Colm

AU - Yap, Chee K.

N1 - Funding Information: was supported in part by the ONR under Contract NOOO14-82-K-0381.

PY - 1985/3

Y1 - 1985/3

N2 - A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalized Voronoi diagram, and reduces the search for a collision-free continuous motion to a search for a connected path along the edges of such a diagram. This approach yields an O(n log n) algorithm for planning an obstacle-avoiding motion of a single circular disc amid polygonal obstacles. Later papers will show that extensions of the approach can solve other motion-planning problems, including those of moving a straight line segment or several coordinated discs in the plane amid polygonal obstacles.

AB - A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalized Voronoi diagram, and reduces the search for a collision-free continuous motion to a search for a connected path along the edges of such a diagram. This approach yields an O(n log n) algorithm for planning an obstacle-avoiding motion of a single circular disc amid polygonal obstacles. Later papers will show that extensions of the approach can solve other motion-planning problems, including those of moving a straight line segment or several coordinated discs in the plane amid polygonal obstacles.

UR - http://www.scopus.com/inward/record.url?scp=34748864359&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34748864359&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(85)90021-5

DO - 10.1016/0196-6774(85)90021-5

M3 - Article

AN - SCOPUS:34748864359

SN - 0196-6774

VL - 6

SP - 104

EP - 111

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

A "retraction" method for planning the motion of a disc

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this