InforLorV4, PascalFrancis, Corpus, bibRecord, 000814

Curvature-constrained shortest paths in a convex polygon

Identifieur interne : 000814 ( PascalFrancis/Corpus ); précédent : 000813; suivant : 000815

Curvature-constrained shortest paths in a convex polygon

Auteurs : Pankaj K. Agarwal ; Therese Biedl ; Sylvain Lazard ; Steve Robbins ; Subhash Suri ; Sue Whitesides

Source :

SIAM journal on computing [ 0097-5397 ] ; 2002.

RBID : Pascal:03-0157981

Descripteurs français

Pascal (Inist)
- Géométrie algorithmique, Robotique, Commande mouvement, Planification, Système non holonome, Equation mouvement, Robot mobile, Chemin Dubins, Plannification mouvement.

English descriptors

KwdEn :
- Computational geometry, Dubins path, Equation of motion, Mobile robot, Motion control, Motion planning, Non holonomic system, Planning, Robotics.

Abstract

Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let P be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside P. (A configuration specifies both a location and a direction of travel.) We present an O(n² log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0097-5397`
A03		`1`		`@0 SIAM j. comput.`
A05				`@2 31`
A06				`@2 6`
A08	`01`	`1`	`ENG`	`@1 Curvature-constrained shortest paths in a convex polygon`
A11	`01`	`1`		`@1 AGARWAL (Pankaj K.)`
A11	`02`	`1`		`@1 BIEDL (Therese)`
A11	`03`	`1`		`@1 LAZARD (Sylvain)`
A11	`04`	`1`		`@1 ROBBINS (Steve)`
A11	`05`	`1`		`@1 SURI (Subhash)`
A11	`06`	`1`		`@1 WHITESIDES (Sue)`
A14	`01`			`@1 Center for Geometric Computing, Computer Science Department, Duke University, Box 90129 @2 Durham, NC 27708-0129 @3 USA @Z 1 aut.`
A14	`02`			`@1 Department of Computer Science, University of Waterloo @2 Waterloo, ON, N2L 3G1 @3 CAN @Z 2 aut.`
A14	`03`			`@1 INRIA Lorraine - LORIA, 615 rue du jardin botanique, B.P. 101 @2 54602 Villers-les-Nancy @3 FRA @Z 3 aut.`
A14	`04`			`@1 School of Computer Science, McGill University @2 Montreal, PQ, H3A 2T5 @3 CAN @Z 4 aut. @Z 6 aut.`
A14	`05`			`@1 Department of Computer Science, University of California @2 Santa Barbara, CA 93106 @3 USA @Z 5 aut.`
A20				`@1 1814-1851`
A21				`@1 2002`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 16063 @5 354000105666450090`
A44				`@0 0000 @1 © 2003 INIST-CNRS. All rights reserved.`
A45				`@0 43 ref.`
A47	`01`	`1`		`@0 03-0157981`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 SIAM journal on computing`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	@0 Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let P be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside P. (A configuration specifies both a location and a direction of travel.) We present an O(n² log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.
C02	`01`	`X`		`@0 001D02C03`
C03	`01`	`X`	`FRE`	`@0 Géométrie algorithmique @5 01`
C03	`01`	`X`	`ENG`	`@0 Computational geometry @5 01`
C03	`01`	`X`	`SPA`	`@0 Geometría computacional @5 01`
C03	`02`	`X`	`FRE`	`@0 Robotique @5 02`
C03	`02`	`X`	`ENG`	`@0 Robotics @5 02`
C03	`02`	`X`	`SPA`	`@0 Robótica @5 02`
C03	`03`	`X`	`FRE`	`@0 Commande mouvement @5 03`
C03	`03`	`X`	`ENG`	`@0 Motion control @5 03`
C03	`03`	`X`	`SPA`	`@0 Control movimiento @5 03`
C03	`04`	`X`	`FRE`	`@0 Planification @5 04`
C03	`04`	`X`	`ENG`	`@0 Planning @5 04`
C03	`04`	`X`	`SPA`	`@0 Planificación @5 04`
C03	`05`	`X`	`FRE`	`@0 Système non holonome @5 05`
C03	`05`	`X`	`ENG`	`@0 Non holonomic system @5 05`
C03	`05`	`X`	`SPA`	`@0 Sistema no holónomo @5 05`
C03	`06`	`X`	`FRE`	`@0 Equation mouvement @5 06`
C03	`06`	`X`	`ENG`	`@0 Equation of motion @5 06`
C03	`06`	`X`	`SPA`	`@0 Ecuación movimiento @5 06`
C03	`07`	`X`	`FRE`	`@0 Robot mobile @4 CD @5 96`
C03	`07`	`X`	`ENG`	`@0 Mobile robot @4 CD @5 96`
C03	`08`	`X`	`FRE`	`@0 Chemin Dubins @4 CD @5 97`
C03	`08`	`X`	`ENG`	`@0 Dubins path @4 CD @5 97`
C03	`09`	`X`	`FRE`	`@0 Plannification mouvement @4 CD @5 98`
C03	`09`	`X`	`ENG`	`@0 Motion planning @4 CD @5 98`
N21				`@1 090`

Format Inist (serveur)

NO :	PASCAL 03-0157981 INIST
ET :	Curvature-constrained shortest paths in a convex polygon
AU :	AGARWAL (Pankaj K.); BIEDL (Therese); LAZARD (Sylvain); ROBBINS (Steve); SURI (Subhash); WHITESIDES (Sue)
AF :	Center for Geometric Computing, Computer Science Department, Duke University, Box 90129/Durham, NC 27708-0129/Etats-Unis (1 aut.); Department of Computer Science, University of Waterloo/Waterloo, ON, N2L 3G1/Canada (2 aut.); INRIA Lorraine - LORIA, 615 rue du jardin botanique, B.P. 101/54602 Villers-les-Nancy/France (3 aut.); School of Computer Science, McGill University/Montreal, PQ, H3A 2T5/Canada (4 aut., 6 aut.); Department of Computer Science, University of California/Santa Barbara, CA 93106/Etats-Unis (5 aut.)
DT :	Publication en série; Niveau analytique
SO :	SIAM journal on computing; ISSN 0097-5397; Etats-Unis; Da. 2002; Vol. 31; No. 6; Pp. 1814-1851; Bibl. 43 ref.
LA :	Anglais
EA :	Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let P be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside P. (A configuration specifies both a location and a direction of travel.) We present an O(n² log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.
CC :	001D02C03
FD :	Géométrie algorithmique; Robotique; Commande mouvement; Planification; Système non holonome; Equation mouvement; Robot mobile; Chemin Dubins; Plannification mouvement
ED :	Computational geometry; Robotics; Motion control; Planning; Non holonomic system; Equation of motion; Mobile robot; Dubins path; Motion planning
SD :	Geometría computacional; Robótica; Control movimiento; Planificación; Sistema no holónomo; Ecuación movimiento
LO :	INIST-16063.354000105666450090
ID :	03-0157981

Links to Exploration step

Pascal:03-0157981

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Curvature-constrained shortest paths in a convex polygon</title>
<author><name sortKey="Agarwal, Pankaj K" sort="Agarwal, Pankaj K" uniqKey="Agarwal P" first="Pankaj K." last="Agarwal">Pankaj K. Agarwal</name>
<affiliation><inist:fA14 i1="01"><s1>Center for Geometric Computing, Computer Science Department, Duke University, Box 90129</s1>
<s2>Durham, NC 27708-0129</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Biedl, Therese" sort="Biedl, Therese" uniqKey="Biedl T" first="Therese" last="Biedl">Therese Biedl</name>
<affiliation><inist:fA14 i1="02"><s1>Department of Computer Science, University of Waterloo</s1>
<s2>Waterloo, ON, N2L 3G1</s2>
<s3>CAN</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation><inist:fA14 i1="03"><s1>INRIA Lorraine - LORIA, 615 rue du jardin botanique, B.P. 101</s1>
<s2>54602 Villers-les-Nancy</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Robbins, Steve" sort="Robbins, Steve" uniqKey="Robbins S" first="Steve" last="Robbins">Steve Robbins</name>
<affiliation><inist:fA14 i1="04"><s1>School of Computer Science, McGill University</s1>
<s2>Montreal, PQ, H3A 2T5</s2>
<s3>CAN</s3>
<sZ>4 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Suri, Subhash" sort="Suri, Subhash" uniqKey="Suri S" first="Subhash" last="Suri">Subhash Suri</name>
<affiliation><inist:fA14 i1="05"><s1>Department of Computer Science, University of California</s1>
<s2>Santa Barbara, CA 93106</s2>
<s3>USA</s3>
<sZ>5 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name>
<affiliation><inist:fA14 i1="04"><s1>School of Computer Science, McGill University</s1>
<s2>Montreal, PQ, H3A 2T5</s2>
<s3>CAN</s3>
<sZ>4 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">03-0157981</idno>
<date when="2002">2002</date>
<idno type="stanalyst">PASCAL 03-0157981 INIST</idno>
<idno type="RBID">Pascal:03-0157981</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000814</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Curvature-constrained shortest paths in a convex polygon</title>
<author><name sortKey="Agarwal, Pankaj K" sort="Agarwal, Pankaj K" uniqKey="Agarwal P" first="Pankaj K." last="Agarwal">Pankaj K. Agarwal</name>
<affiliation><inist:fA14 i1="01"><s1>Center for Geometric Computing, Computer Science Department, Duke University, Box 90129</s1>
<s2>Durham, NC 27708-0129</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Biedl, Therese" sort="Biedl, Therese" uniqKey="Biedl T" first="Therese" last="Biedl">Therese Biedl</name>
<affiliation><inist:fA14 i1="02"><s1>Department of Computer Science, University of Waterloo</s1>
<s2>Waterloo, ON, N2L 3G1</s2>
<s3>CAN</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation><inist:fA14 i1="03"><s1>INRIA Lorraine - LORIA, 615 rue du jardin botanique, B.P. 101</s1>
<s2>54602 Villers-les-Nancy</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Robbins, Steve" sort="Robbins, Steve" uniqKey="Robbins S" first="Steve" last="Robbins">Steve Robbins</name>
<affiliation><inist:fA14 i1="04"><s1>School of Computer Science, McGill University</s1>
<s2>Montreal, PQ, H3A 2T5</s2>
<s3>CAN</s3>
<sZ>4 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Suri, Subhash" sort="Suri, Subhash" uniqKey="Suri S" first="Subhash" last="Suri">Subhash Suri</name>
<affiliation><inist:fA14 i1="05"><s1>Department of Computer Science, University of California</s1>
<s2>Santa Barbara, CA 93106</s2>
<s3>USA</s3>
<sZ>5 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Whitesides, Sue" sort="Whitesides, Sue" uniqKey="Whitesides S" first="Sue" last="Whitesides">Sue Whitesides</name>
<affiliation><inist:fA14 i1="04"><s1>School of Computer Science, McGill University</s1>
<s2>Montreal, PQ, H3A 2T5</s2>
<s3>CAN</s3>
<sZ>4 aut.</sZ>
<sZ>6 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">SIAM journal on computing</title>
<title level="j" type="abbreviated">SIAM j. comput.</title>
<idno type="ISSN">0097-5397</idno>
<imprint><date when="2002">2002</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">SIAM journal on computing</title>
<title level="j" type="abbreviated">SIAM j. comput.</title>
<idno type="ISSN">0097-5397</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computational geometry</term>
<term>Dubins path</term>
<term>Equation of motion</term>
<term>Mobile robot</term>
<term>Motion control</term>
<term>Motion planning</term>
<term>Non holonomic system</term>
<term>Planning</term>
<term>Robotics</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Géométrie algorithmique</term>
<term>Robotique</term>
<term>Commande mouvement</term>
<term>Planification</term>
<term>Système non holonome</term>
<term>Equation mouvement</term>
<term>Robot mobile</term>
<term>Chemin Dubins</term>
<term>Plannification mouvement</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let P be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside P. (A configuration specifies both a location and a direction of travel.) We present an O(n<sup>2</sup>
 log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0097-5397</s0>
</fA01>
<fA03 i2="1"><s0>SIAM j. comput.</s0>
</fA03>
<fA05><s2>31</s2>
</fA05>
<fA06><s2>6</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>Curvature-constrained shortest paths in a convex polygon</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>AGARWAL (Pankaj K.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>BIEDL (Therese)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>LAZARD (Sylvain)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>ROBBINS (Steve)</s1>
</fA11>
<fA11 i1="05" i2="1"><s1>SURI (Subhash)</s1>
</fA11>
<fA11 i1="06" i2="1"><s1>WHITESIDES (Sue)</s1>
</fA11>
<fA14 i1="01"><s1>Center for Geometric Computing, Computer Science Department, Duke University, Box 90129</s1>
<s2>Durham, NC 27708-0129</s2>
<s3>USA</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>Department of Computer Science, University of Waterloo</s1>
<s2>Waterloo, ON, N2L 3G1</s2>
<s3>CAN</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA14 i1="03"><s1>INRIA Lorraine - LORIA, 615 rue du jardin botanique, B.P. 101</s1>
<s2>54602 Villers-les-Nancy</s2>
<s3>FRA</s3>
<sZ>3 aut.</sZ>
</fA14>
<fA14 i1="04"><s1>School of Computer Science, McGill University</s1>
<s2>Montreal, PQ, H3A 2T5</s2>
<s3>CAN</s3>
<sZ>4 aut.</sZ>
<sZ>6 aut.</sZ>
</fA14>
<fA14 i1="05"><s1>Department of Computer Science, University of California</s1>
<s2>Santa Barbara, CA 93106</s2>
<s3>USA</s3>
<sZ>5 aut.</sZ>
</fA14>
<fA20><s1>1814-1851</s1>
</fA20>
<fA21><s1>2002</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>16063</s2>
<s5>354000105666450090</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2003 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>43 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>03-0157981</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>SIAM journal on computing</s0>
</fA64>
<fA66 i1="01"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let P be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside P. (A configuration specifies both a location and a direction of travel.) We present an O(n<sup>2</sup>
 log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D02C03</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Géométrie algorithmique</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Computational geometry</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Geometría computacional</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Robotique</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Robotics</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Robótica</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Commande mouvement</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Motion control</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Control movimiento</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Planification</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Planning</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Planificación</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Système non holonome</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Non holonomic system</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Sistema no holónomo</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Equation mouvement</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Equation of motion</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Ecuación movimiento</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Robot mobile</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Mobile robot</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Chemin Dubins</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG"><s0>Dubins path</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Plannification mouvement</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Motion planning</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03>
<fN21><s1>090</s1>
</fN21>
</pA>
</standard>
<server><NO>PASCAL 03-0157981 INIST</NO>
<ET>Curvature-constrained shortest paths in a convex polygon</ET>
<AU>AGARWAL (Pankaj K.); BIEDL (Therese); LAZARD (Sylvain); ROBBINS (Steve); SURI (Subhash); WHITESIDES (Sue)</AU>
<AF>Center for Geometric Computing, Computer Science Department, Duke University, Box 90129/Durham, NC 27708-0129/Etats-Unis (1 aut.); Department of Computer Science, University of Waterloo/Waterloo, ON, N2L 3G1/Canada (2 aut.); INRIA Lorraine - LORIA, 615 rue du jardin botanique, B.P. 101/54602 Villers-les-Nancy/France (3 aut.); School of Computer Science, McGill University/Montreal, PQ, H3A 2T5/Canada (4 aut., 6 aut.); Department of Computer Science, University of California/Santa Barbara, CA 93106/Etats-Unis (5 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>SIAM journal on computing; ISSN 0097-5397; Etats-Unis; Da. 2002; Vol. 31; No. 6; Pp. 1814-1851; Bibl. 43 ref.</SO>
<LA>Anglais</LA>
<EA>Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let P be a convex polygon with n vertices. We study the collision-free, optimal path-planning problem for B moving between two configurations inside P. (A configuration specifies both a location and a direction of travel.) We present an O(n<sup>2</sup>
 log n) time algorithm for determining whether a collision-free path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles.</EA>
<CC>001D02C03</CC>
<FD>Géométrie algorithmique; Robotique; Commande mouvement; Planification; Système non holonome; Equation mouvement; Robot mobile; Chemin Dubins; Plannification mouvement</FD>
<ED>Computational geometry; Robotics; Motion control; Planning; Non holonomic system; Equation of motion; Mobile robot; Dubins path; Motion planning</ED>
<SD>Geometría computacional; Robótica; Control movimiento; Planificación; Sistema no holónomo; Ecuación movimiento</SD>
<LO>INIST-16063.354000105666450090</LO>
<ID>03-0157981</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000814 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000814 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:03-0157981
   |texte=   Curvature-constrained shortest paths in a convex polygon
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Curvature-constrained shortest paths in a convex polygon

Curvature-constrained shortest paths in a convex polygon

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri