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

Xavier Goaoc; Hyo-Sil Kim; Sylvain Lazard

doi:10.1137/100816079

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

Xavier Goaoc ¹ Hyo-Sil Kim ² Sylvain Lazard ¹

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility

Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry

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

Document type :

Journal articles

Domain :

Computer Science [cs] / Computational Geometry [cs.CG]

Liste complète des métadonnées

Cited literature [20 references] Display Hide Download

https://hal.inria.fr/hal-00927100
Contributor : Sylvain Lazard <>
Submitted on : Friday, January 10, 2014 - 7:06:40 PM
Last modification on : Thursday, February 7, 2019 - 5:53:34 PM

viapoints_final.pdf

Files produced by the author(s)

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

Files

Identifiers

Collections

Citation

Export

Metrics

317

475

Contact

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

Files

Identifiers

Collections

Citation

Export

Share

Metrics

317

475

Contact