DocumentCode
1309599
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
Volume
57
Issue
1
fYear
2012
Firstpage
265
Lastpage
270
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);
fLanguage
English
Journal_Title
Automatic Control, IEEE Transactions on
Publisher
ieee
ISSN
0018-9286
Type
jour
DOI
10.1109/TAC.2011.2166311
Filename
6004813
Link To Document