Bounded-Curvature Shortest Paths through a Sequence of Points using Convex Optimization

Xavier Goaoc 1 Hyo-Sil Kim 2 Sylvain Lazard 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry, Inria Nancy - Grand Est
2 KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]
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 is a sub-problem of the Dubins Traveling Salesman Problem and also arises naturally in path planning for point car-like robots in the presence of polygonal obstacles. We show that when consecutive waypoints are distance at least four apart, this question reduces to a family of convex optimization problems over polyhedra in $\mathbb{R}^n$.
Keywords : Convex optimization Bounded curvature Dubins path Path planning
Type de document :
Article dans une revue
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2013, 42 (2), pp.662-684. 〈10.1137/100816079〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00927100
Contributeur : Sylvain Lazard <>
Soumis le : vendredi 10 janvier 2014 - 19:06:40
Dernière modification le : jeudi 11 janvier 2018 - 06:25:24
Document(s) archivé(s) le : vendredi 11 avril 2014 - 09:50:59

Fichier

viapoints_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | UNIV-LORRAINE | LORIA-ALGO | LORIA

Citation

Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard. Bounded-Curvature Shortest Paths through a Sequence of Points using Convex Optimization. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2013, 42 (2), pp.662-684. 〈10.1137/100816079〉. 〈hal-00927100〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

265

Téléchargements de fichiers

395

Contact


archive-ouverte@inria.fr