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

Xavier Goaoc, Hyo-Sil Kim, Sylvain Lazard

SIAM Journal on Computing · 2013 · 57 citations · 21 references

DOIFull text

Open access

Concepts

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 subproblem 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 a distance of at least four apart, this question reduces to a family of convex optimization problems over polyhedra in $\mathbb{R}^n$.

References

21