CLC number: TP242.6; V279
On-line Access: 2021-05-17
Received: 2020-01-21
Revision Accepted: 2020-04-28
Crosschecked: 2020-06-11
Cited: 0
Clicked: 4024
Zheng Chen, Chen-hao Sun, Xue-ming Shao, Wen-jie Zhao. A descent method for the Dubins traveling salesman problem with neighborhoods[J]. Frontiers of Information Technology & Electronic Engineering,in press.https://doi.org/10.1631/FITEE.2000041 @article{title="A descent method for the Dubins traveling salesman problem with neighborhoods", %0 Journal Article TY - JOUR
一种求解带邻域的Dubins旅行商问题的坐标下降法流体动力与机电系统国家重点实验室,浙江大学航空航天学院,中国杭州市,310027 摘要:由于带邻域的Dubins旅行商问题(Dubins traveling salesman problem with neighborhoods, DTSPN)是无人机执行多目标区域侦察任务需要解决的核心问题,国内外学者对DTSPN问题的快速求解方法进行了广泛研究。本文针对目前已有方法存在计算资源消耗大等情况,设计了一种用于求解DTSPN问题的无梯度坐标下降方法。该方法的核心步骤是将DTSPN问题分解为一系列子问题,对于每个子问题仅需计算从初始点经过一个区域到达目标点的最短路径。通过研究子问题最短路径的几何特征,并将几何特征与二分法相结合,可得到快速计算子问题的鲁棒算法。然后,将子问题计算方法与坐标下降法相结合,构建了能快速求解DTSPN问题的计算方法。最后,为验证所提方法的有效性和快速性,将所提方法与几种传统算法进行仿真对比。 关键词组: Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article
Reference[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 45th 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 14th 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 55th 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 38th 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. Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou
310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE |
Open peer comments: Debate/Discuss/Question/Opinion
<1>