Bounded-Curvature Shortest Paths through a Sequence of Points

Abstract : We consider the problem of computing shortest paths having curvature at most one almost everywhere and visiting a sequence of $n$ points in the plane in a given order. This problem arises naturally in path planning for point car-like robots in the presence of polygonal obstacles, and is also a sub-problem of the Dubins Traveling Salesman Problem. This problem reduces to minimizing the function $F:\R^n\rightarrow\R$ that maps $(\theta_1,\ldots,\theta_n)$ to the length of a shortest curvature-constrained path that visits the points $p_1, \ldots, p_n$ in order and whose tangent in $p_i$ makes an angle $\theta_i$ with the $x$-axis. We show that when consecutive points are distance at least $4$ apart, all minima of $F$ are realized over at most $2^k$ disjoint convex polyhedra over which $F$ is strictly convex; each polyhedron is defined by $4n-1$ linear inequalities and $k$ denotes, informally, the number of $p_i$ such that the angle $\angle(p_{i-1},p_i,p_{i+1})$ is small. A curvature-constrained shortest path visiting a sequence points can therefore be approximated by standard convex optimization methods, which presents an interesting alternative to the known polynomial-time algorithms that can only compute a multiplicative constant factor approximation. Our technique also opens new perspectives for bounded-curvature path planning among polygonal obstacles. In particular, we show that, under certain conditions, if the sequence of points where a shortest path touches the obstacles is known then ``connecting the dots'' reduces to a family of convex optimization problems.
Type de document :
Rapport
[Research Report] RR-7465, INRIA. 2010, pp.53
Liste complète des métadonnées

https://hal.inria.fr/inria-00539957
Contributeur : Xavier Goaoc <>
Soumis le : lundi 29 novembre 2010 - 11:51:57
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : samedi 3 décembre 2016 - 02:53:34

Fichier

RR-7465.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00539957, version 1

Collections

Citation

Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard. Bounded-Curvature Shortest Paths through a Sequence of Points. [Research Report] RR-7465, INRIA. 2010, pp.53. 〈inria-00539957〉

Partager

Métriques

Consultations de la notice

433

Téléchargements de fichiers

222