Title :
On the Dubins Traveling Salesman Problem
Author :
Le Ny, Jerome ; Feron, Eric ; Frazzoli, Emilio
Author_Institution :
Dept. of Electr. & Syst. Eng., Univ. of Pennsylvania, Philadelphia, PA, USA
Abstract :
We study the traveling salesman problem for a Dubins vehicle. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically.
Keywords :
approximation theory; autonomous aerial vehicles; optimisation; path planning; travelling salesman problems; Dubins traveling salesman problem; Dubins vehicle; NP-hard problem; approximation ratio; heading discretization; lower bounds; motion planning; performance evaluation; Approximation algorithms; Approximation methods; Planning; Robots; Traveling salesman problems; Turning; Vehicles; Algorithms; motion planning; traveling salesman problem (TSP); unmanned aerial vehicles (UAVs);
Journal_Title :
Automatic Control, IEEE Transactions on
DOI :
10.1109/TAC.2011.2166311
