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: Rn → R that maps (θ1,..., θn) to the length of a shortest curvature-constrained path that visits the points p1,..., pn in order and whose tangent in pi makes an angle θ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 2k 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 pi such that the angle ∠(pi−1, pi, pi+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.