Similar articles

Abstract: In this study, we focus mainly on the problem of finding the minimum-length path through a set of circular regions by a fixed-wing unmanned aerial vehicle. Such a problem is referred to as the dubins traveling salesman problem with neighborhoods (DTSPN). Algorithms developed in the literature for solving DTSPN either are computationally demanding or generate low-quality solutions. To achieve a better trade-off between solution quality and computational cost, an efficient gradient-free descent method is designed. The core idea of the descent method is to decompose DTSPN into a series of subproblems, each of which consists of finding the minimum-length path of a dubins vehicle from a configuration to another configuration via an intermediate circular region. By analyzing the geometric properties of the subproblems, we use a bisection method to solve the subproblems. As a result, the descent method can efficiently address DTSPN by successively solving a series of subproblems. Finally, several numerical experiments are carried out to demonstrate the descent method in comparison with several existing algorithms.

一种求解带邻域的Dubins旅行商问题的坐标下降法

[1]Arora S, 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM, 45(5):753-782.

[2]Bhargav J, Chen Z, Shima T, 2019. Shortest bounded-curvature paths via circumferential envelope of a circle. IFAC Conf.

[3]Chen Z, Shima T, 2019. Shortest Dubins paths through three points. Automatica, 105:368-375.

[4]Dubins LE, 1957. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am J Math, 79(3):497-516.

[5]Faigl J, Váuňa P, 2018. Surveillance planning with Bézier curves. IEEE Rob Autom Lett, 3(2):750-757.

[6]Goaoc X, Kim HS, Lazard S, 2013. Bounded-curvature shortest paths through a sequence of points using convex optimization. SIAM J Comput, 42(2):662-684.

[7]Isaacs JT, Hespanha JP, 2013. Dubins traveling salesman problem with neighborhoods: a graph-based approach. Algorithms, 6(1):84-99.

[8]Isaacs JT, Klein DJ, Hespanha JP, 2011. Algorithms for the traveling salesman problem with neighborhoods involving a Dubins vehicle. Proc American Control Conf, p.1704-1709.

[9]Isaiah P, Shima T, 2015. Motion planning algorithms for the Dubins travelling salesperson problem. Automatica, 53:247-255.

[10]Lawler EL, Lenstra JK, Kan AHGR, et al., 1985. The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization. Wiley, New York, USA.

[11]Ma X, Castanon DA, 2006. Receding horizon planning for Dubins traveling salesman problems. Proc 45^th IEEE Conf on Decision and Control, p.5453-5458.

[12]Macharet DG, Alves Neto A, da Camara Neto VF, et al., 2012. An evolutionary approach for the Dubins’ traveling salesman problem with neighborhoods. Proc 14^th Annual Conf on Genetic and Evolutionary Computation, p.377-384.

[13]Ny JL, Feron E, Frazzoli E, 2012. On the Dubins traveling salesman problem. IEEE Trans Autom Contr, 57(1):265-270.

[14]Obermeyer KJ, 2009. Path planning for a UAV performing reconnaissance of static ground targets in terrain. Proc AIAA Guidance, Navigation, and Control Conf, p.10-13.

[15]Obermeyer KJ, Oberlin P, Darbha S, 2010. Sampling-based roadmap methods for a visual reconnaissance UAV. Proc AIAA Guidance, Navigation, and Control Conf, Article 21.

[16]Rathinam S, Sengupta R, Darbha S, 2007. A resource allocation algorithm for multivehicle systems with nonholonomic constraints. IEEE Trans Autom Sci Eng, 4(1):98-104.

[17]Sadeghi A, Smith SL, 2016. On efficient computation of shortest Dubins paths through three consecutive points. Proc IEEE 55^th Conf on Decision and Control, p.6010-6015.

[18]Savla K, Frazzoli E, Bullo F, 2005. On the point-to-point and traveling salesperson problems for Dubins’ vehicle. Proc American Control Conf, p.786-791.

[19]Tran DC, 2019. Tsp.zip. www.mathworks.com/matlabcentral/fileexchange/46629-tsp-zip

[20]Tuqan M, Daher N, Shammas E, 2019. A simplified path planning algorithm for surveillance missions of unmanned aerial vehicles. Proc IEEE/ASME Int Conf on Advanced Intelligent Mechatronics, p.1341-1346.

[21]Váuňa P, Faigl J, 2015. On the Dubins traveling salesman problem with neighborhoods. Proc IEEE/RSJ Int Conf on Intelligent Robots and Systems, p.4029-4034.

[22]Xin B, Chen J, Xu D, et al., 2014. Hybrid encoding based differential evolution algorithms for Dubins traveling salesman problem with neighborhood. Contr Theory Appl, 31(7):941-954.

[23]Yeh J, 2006. Real Analysis: Theory of Measure and Integration. World Scientific, Hackensack, New Jersey, USA.

[24]Yu X, Hung JY, 2012. Optimal path planning for an autonomous robot-trailer system. Proc 38^th Annual Conf on IEEE Industrial Electronics Society, p.2762-2767.

[25]Zhang X, Chen J, Xin B, et al., 2014. A memetic algorithm for path planning of curvature-constrained UAVs performing surveillance of multiple ground targets. Chin J Aeron, 27(3):622-633.