Full Text:   <1227>

Summary:  <967>

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: 2421

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Zheng Chen

https://orcid.org/0000-0002-3573-1546

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2021 Vol.22 No.5 P.732-740

http://doi.org/10.1631/FITEE.2000041


A descent method for the Dubins traveling salesman problem with neighborhoods


Author(s):  Zheng Chen, Chen-hao Sun, Xue-ming Shao, Wen-jie Zhao

Affiliation(s):  State Key Laboratory of Fluid Power and Mechatronic Systems, School of Aeronautics and Astronautics, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   z_chen@zju.edu.cn, mecsxm@zju.edu.cn

Key Words:  Dubins vehicle, Descent method, Dubins traveling salesman problem


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.

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

陈征,孙晨浩,邵雪明,赵文杰
流体动力与机电系统国家重点实验室,浙江大学航空航天学院,中国杭州市,310027

摘要:由于带邻域的Dubins旅行商问题(Dubins traveling salesman problem with neighborhoods, DTSPN)是无人机执行多目标区域侦察任务需要解决的核心问题,国内外学者对DTSPN问题的快速求解方法进行了广泛研究。本文针对目前已有方法存在计算资源消耗大等情况,设计了一种用于求解DTSPN问题的无梯度坐标下降方法。该方法的核心步骤是将DTSPN问题分解为一系列子问题,对于每个子问题仅需计算从初始点经过一个区域到达目标点的最短路径。通过研究子问题最短路径的几何特征,并将几何特征与二分法相结合,可得到快速计算子问题的鲁棒算法。然后,将子问题计算方法与坐标下降法相结合,构建了能快速求解DTSPN问题的计算方法。最后,为验证所提方法的有效性和快速性,将所提方法与几种传统算法进行仿真对比。

关键词:Dubins飞行器;坐标下降法;Dubins旅行商问题

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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE