Curvature-Constrained Shortest Paths in a Convex Polygon - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

Curvature-Constrained Shortest Paths in a Convex Polygon

Résumé

Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let poly be a convex polygon with n vertices. We study the collision-free, optimal path planning problem for B moving between two configurations inside poly (a configuration specifies both a location and a direction of travel). We present an runtime- time algorithm for determining whether a collision-free path exists for B between xstwo 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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-4063.pdf (730.41 Ko) Télécharger le fichier

Dates et versions

inria-00072573 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00072573 , version 1

Citer

Pankaj K. Agarwal, Thérèse Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, et al.. Curvature-Constrained Shortest Paths in a Convex Polygon. [Research Report] RR-4063, INRIA. 2000, pp.59. ⟨inria-00072573⟩
123 Consultations
191 Téléchargements

Partager

Gmail Facebook X LinkedIn More