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
2 KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]

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$.

Mots clés: Convex optimization; Bounded curvature; Dubins path; Path planning

Domaines: Géométrie algorithmique [cs.CG]

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⟩