A Gradient Descent Method for The Dubins Traveling Salesman Problem
2021
We propose a combination of a bounding procedure and gradient descent method
for solving the Dubins traveling salesman problem, that is, the problem of
finding a shortest curvature-constrained tour through a finite number of points
in the euclidean plane. The problem finds applications in path planning for
robotic vehicles and unmanned aerial vehicles, where a minimum turning radius
prevents the vehicle from taking sharp turns. In this paper, we focus on the
case where any two points are separated by at least four times the minimum
turning radius, which is most interesting from a practical standpoint. The
bounding procedure efficiently determines the optimal order in which to visit
the points. The gradient descent method, which is inspired by a mechanical
model, determines the optimal trajectories of the tour through the points in a
given order, and its computation time scales linearly with the number of
points. In experiments on nine points, the bounding procedure typically
explores no more than a few sequences before finding the optimal sequence, and
the gradient descent method typically converges to within 1\% of optimal in a
single iteration.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
0
Citations
NaN
KQI