Bounded-Curvature Shortest Paths through a Sequence of Points using Convex Optimization - Archive ouverte HAL Access content directly
Journal Articles SIAM Journal on Computing Year : 2013

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

(1) , (2) , (1)
1
2

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$.
Vignette du fichier
2013 Bounded-Curvature Shortest Paths.png (48.39 Ko) Télécharger le fichier Fichier principal
Vignette du fichier
viapoints_final.pdf (330.92 Ko) Télécharger le fichier
Format : Figure, Image
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00927100 , version 1 (10-01-2014)

Identifiers

Cite

Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard. Bounded-Curvature Shortest Paths through a Sequence of Points using Convex Optimization. SIAM Journal on Computing, 2013, 42 (2), pp.662-684. ⟨10.1137/100816079⟩. ⟨hal-00927100⟩
202 View
574 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More