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

陈征; 孙晨浩; 邵雪明; 赵文杰

doi:10.1631/FITEE.2000041

Your Location：

Home >

Browse articles >

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

常规文章 | Updated：2022-05-19

- 一种求解带邻域的Dubins旅行商问题的坐标下降法
- A descent method for the Dubins traveling salesman problem with neighborhoods
- 信息与电子工程前沿（英文） 2021年22卷第5期页码：732-740
- Affiliations：
  
  State Key Laboratory of Fluid Power and Mechatronic Systems, School of Aeronautics and Astronautics, Zhejiang University, Hangzhou 310027, China
- Author bio：
  
  [ "", "Zheng CHEN received his PhD degree in applied mathematics from the Université Paris-Saclay in 2016, and his BS and MS degrees in aerospace engineering from the Northwestern Polytechnical University in 2010 and 2013, respectively. He is currently a researcher at the School of Aeronautics and Astronautics at Zhejiang University. His current research interests include guidance and control in aerospace engineering." ]
  Xue-ming SHAO, E-mail: mecsxm@zju.edu.cn
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61903331 and 61703366) and the Fundamental Research Funds for the Central Universities, China (No. 2019FZA4024)
- DOI：10.1631/FITEE.2000041
  中图分类号： TP242.6;V279
- 收稿：2020-01-21，
  
  修回：2020-;6-11，
  
  网络出版：2020-08-13，
  
  纸质出版：2021-05
- Accepted：
Scan QR Code
陈征, 孙晨浩, 邵雪明, 等. 一种求解带邻域的Dubins旅行商问题的坐标下降法[J]. 信息与电子工程前沿（英文）, 2021,22(5):732-740.

Zheng CHEN, Chen-hao SUN, Xue-ming SHAO, et al. A descent method for the Dubins traveling salesman problem with neighborhoods[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(5): 732-740.
陈征, 孙晨浩, 邵雪明, 等. 一种求解带邻域的Dubins旅行商问题的坐标下降法[J]. 信息与电子工程前沿（英文）, 2021,22(5):732-740. DOI： 10.1631/FITEE.2000041.

Zheng CHEN, Chen-hao SUN, Xue-ming SHAO, et al. A descent method for the Dubins traveling salesman problem with neighborhoods[J]. Frontiers of Information Technology & Electronic Engineering, 2021, 22(5): 732-740. DOI： 10.1631/FITEE.2000041.

摘要

由于带邻域的Dubins旅行商问题（Dubins traveling salesman problem with neighborhoods

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

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.

关键词

Keywords

references

S Arora . . Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems . . J ACM , , 1998 . . 45 ( ( 5 ): ): 753 - - 782 . . DOI: 10.1145/290179.290180 http://doi.org/10.1145/290179.290180 . .

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

Z Chen , , , T Shima . . Shortest Dubins paths through three points . . Automatica , , 2019 . . 105 368 - - 375 . . DOI: 10.1016/j.automatica.2019.04.007 http://doi.org/10.1016/j.automatica.2019.04.007 . .

LE Dubins . . On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents . . Am J Math , , 1957 . . 79 ( ( 3 ): ): 497 - - 516 . . DOI: 10.2307/2372560 http://doi.org/10.2307/2372560 . .

J Faigl , , , P Vá${\rm{\breve n}}$a . . Surveillance planning with Bézier curves . . IEEE Rob Autom Lett , , 2018 . . 3 ( ( 2 ): ): 750 - - 757 . . DOI: 10.1109/LRA.2018.2789844 http://doi.org/10.1109/LRA.2018.2789844 . .

X Goaoc , , , HS Kim , , , S Lazard . . Bounded-curvature shortest paths through a sequence of points using convex optimization . . SIAM J Comput , , 2013 . . 42 ( ( 2 ): ): 662 - - 684 . . DOI: 10.1137/100816079 http://doi.org/10.1137/100816079 . .

JT Isaacs , , , JP Hespanha . . Dubins traveling salesman problem with neighborhoods: a graph-based approach . . Algorithms , , 2013 . . 6 ( ( 1 ): ): 84 - - 99 . . DOI: 10.3390/a6010084 http://doi.org/10.3390/a6010084 . .

JT Isaacs , , , DJ Klein , , , JP Hespanha . . Algorithms for the traveling salesman problem with neighborhoods involving a Dubins vehicle . . Proc American Control Conf , , 2011 . . p.1704 - - 1709 . . DOI: 10.1109/ACC.2011.5991501 http://doi.org/10.1109/ACC.2011.5991501 . .

P Isaiah , , , T Shima . . Motion planning algorithms for the Dubins travelling salesperson problem . . Automatica , , 2015 . . 53 247 - - 255 . . DOI: 10.1016/j.automatica.2014.12.041 http://doi.org/10.1016/j.automatica.2014.12.041 . .

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

X Ma , , , DA Castanon . . Receding horizon planning for Dubins traveling salesman problems . . Proc 45 th IEEE Conf on Decision and Control , , 2006 . . p.5453 - - 5458 . . DOI: 10.1109/CDC.2006.376928 http://doi.org/10.1109/CDC.2006.376928 . .

DG Macharet , , , Neto A Alves , , , Camara Neto VF da , , , 等 . . An evolutionary approach for the Dubins' traveling salesman problem with neighborhoods . . Proc 14 th Annual Conf on Genetic and Evolutionary Computation , , 2012 . . p.377 - - 384 . . DOI: 10.1145/2330163.2330218 http://doi.org/10.1145/2330163.2330218 . .

JL Ny , , , E Feron , , , E Frazzoli . . On the Dubins traveling salesman problem . . IEEE Trans Autom Contr , , 2012 . . 57 ( ( 1 ): ): 265 - - 270 . . DOI: 10.1109/TAC.2011.2166311 http://doi.org/10.1109/TAC.2011.2166311 . .

KJ Obermeyer . . Path planning for a UAV performing reconnaissance of static ground targets in terrain . . Proc AIAA Guidance, Navigation, and Control Conf , , 2009 . . p.10 - - 13 . . DOI: 10.2514/6.2009-5888 http://doi.org/10.2514/6.2009-5888 . .

KJ Obermeyer , , , P Oberlin , , , S Darbha . . Sampling-based roadmap methods for a visual reconnaissance UAV . . Proc AIAA Guidance, Navigation, and Control Conf, Article 21 , , 2010 . . DOI: 10.2514/6.2010-7568 http://doi.org/10.2514/6.2010-7568 . .

S Rathinam , , , R Sengupta , , , S Darbha . . A resource allocation algorithm for multivehicle systems with nonholonomic constraints . . IEEE Trans Autom Sci Eng , , 2007 . . 4 ( ( 1 ): ): 98 - - 104 . . DOI: 10.1109/TASE.2006.872110 http://doi.org/10.1109/TASE.2006.872110 . .

A Sadeghi , , , SL Smith . . On efficient computation of shortest Dubins paths through three consecutive points . . Proc IEEE 55 th Conf on Decision and Control , , 2016 . . p.6010 - - 6015 . . DOI: 10.1109/CDC.2016.7799192 http://doi.org/10.1109/CDC.2016.7799192 . .

K Savla , , , E Frazzoli , , , F Bullo . . On the point-to-point and traveling salesperson problems for Dubins' vehicle . . Proc American Control Conf , , 2005 . . p.786 - - 791 . . DOI: 10.1109/ACC.2005.1470055 http://doi.org/10.1109/ACC.2005.1470055 . .

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

M Tuqan , , , N Daher , , , E Shammas . . A simplified path planning algorithm for surveillance missions of unmanned aerial vehicles . . Proc IEEE/ASME Int Conf on Advanced Intelligent Mechatronics , , 2019 . . p.1341 - - 1346 . . DOI: 10.1109/AIM.2019.8868551 http://doi.org/10.1109/AIM.2019.8868551 . .

P Vá${\rm{\breve n}}$a , , , J Faigl . . On the Dubins traveling salesman problem with neighborhoods . . Proc IEEE/RSJ Int Conf on Intelligent Robots and Systems , , 2015 . . p.4029 - - 4034 . . DOI: 10.1109/IROS.2015.7353945 http://doi.org/10.1109/IROS.2015.7353945 . .

B Xin , , , J Chen , , , D Xu , , , 等 . . Hybrid encoding based differential evolution algorithms for Dubins traveling salesman problem with neighborhood . . Contr Theory Appl , , 2014 . . 31 ( ( 7 ): ): 941 - - 954 . . DOI: 10.7641/CTA.2014.40280 http://doi.org/10.7641/CTA.2014.40280 . .

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

X Yu , , , JY Hung . . Optimal path planning for an autonomous robot-trailer system . . Proc 38 th Annual Conf on IEEE Industrial Electronics Society , , 2012 . . p.2762 - - 2767 . . DOI: 10.1109/IECON.2012.6389140 http://doi.org/10.1109/IECON.2012.6389140 . .

X Zhang , , , J Chen , , , B Xin , , , 等 . . A memetic algorithm for path planning of curvature-constrained UAVs performing surveillance of multiple ground targets . . Chin J Aeron , , 2014 . . 27 ( ( 3 ): ): 622 - - 633 . . DOI: 10.1016/j.cja.2014.04.024 http://doi.org/10.1016/j.cja.2014.04.024 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据