CLC number: TP242.6; V279
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2020-06-11
Cited: 0
Clicked: 4843
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, 2021, 22(5): 732-740.
@article{title="A descent method for the Dubins traveling salesman problem with neighborhoods",
author="Zheng Chen, Chen-hao Sun, Xue-ming Shao, Wen-jie Zhao",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="22",
number="5",
pages="732-740",
year="2021",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.2000041"
}
%0 Journal Article
%T A descent method for the Dubins traveling salesman problem with neighborhoods
%A Zheng Chen
%A Chen-hao Sun
%A Xue-ming Shao
%A Wen-jie Zhao
%J Frontiers of Information Technology & Electronic Engineering
%V 22
%N 5
%P 732-740
%@ 2095-9184
%D 2021
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.2000041
TY - JOUR
T1 - A descent method for the Dubins traveling salesman problem with neighborhoods
A1 - Zheng Chen
A1 - Chen-hao Sun
A1 - Xue-ming Shao
A1 - Wen-jie Zhao
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 22
IS - 5
SP - 732
EP - 740
%@ 2095-9184
Y1 - 2021
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.2000041
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.
[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.
Open peer comments: Debate/Discuss/Question/Opinion
<1>