On the Dubins Traveling Salesman Problem

被引:116
作者
Jerome Le Ny [1 ]
Feron, Eric [2 ]
Frazzoli, Emilio [3 ,4 ]
机构
[1] Univ Penn, Dept Elect & Syst Engn, Philadelphia, PA 19104 USA
[2] Georgia Inst Technol, Sch Aerosp Engn, Atlanta, GA 30332 USA
[3] MIT, Dept Aeronaut & Astronaut, Cambridge, MA 02139 USA
[4] MIT, Lab Informat & Decis Syst, Cambridge, MA 02139 USA
关键词
Algorithms; motion planning; traveling salesman problem (TSP); unmanned aerial vehicles (UAVs); SALESPERSON PROBLEMS; ALGORITHMS; CURVATURE;
D O I
10.1109/TAC.2011.2166311
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:265 / 270
页数:7
相关论文
共 28 条
[1]   Approximation algorithms for curvature-constrained shortest paths [J].
Agarwal, PK ;
Wang, HY .
SIAM JOURNAL ON COMPUTING, 2001, 30 (06) :1739-1772
[2]   Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].
Arora, S .
JOURNAL OF THE ACM, 1998, 45 (05) :753-782
[3]  
Behzad A., 2002, P 15 INT C SYST ENG
[4]  
Boissonnat J.-D, 1994, 2181 INRIA
[5]  
Boissonnat J.-D., 1993, 2153 INRIA
[6]  
Cormen T., 2001, Introduction to Algorithms
[8]  
Enright J., 2005, P IFAC WORLD C PRAG
[9]   ON THE WORST-CASE PERFORMANCE OF SOME ALGORITHMS FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM [J].
FRIEZE, AM ;
GALBIATI, G ;
MAFFIOLI, F .
NETWORKS, 1982, 12 (01) :23-39
[10]  
Garey R.L., 1976, P 8 ANN ACM S THEOR, P10, DOI DOI 10.1145/800113.803626