SIAM Journal on Computing · 2013 · 57 citations · 21 references
ComputingComputer ScienceOptimizationPath PlanningRoboticsCombinatorial OptimizationConvex GeometryGeometric OptimizationRoute PlanningShortest Path AlgorithmsDubins Path PlanningGeometric Path PlanningPath OptimizationRobotic Path PlanningShortest Path OptimizationShortest Path PlanningShortest PathsTraveling Salesman Problem
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$.
21