基于自适应郊狼算法的无人机离线航迹规划

doi:10.12305/j.issn.1001-506X.2022.02.30

摘要/Abstract

摘要：

针对无人机(unmanned aerial vehicle, UAV)离线航迹规划对算法全局搜索能力和鲁棒性的要求, 设计一种自适应郊狼算法, 从最优化问题角度研究UAV离线航迹规划。建立UAV离线航迹规划的数学模型; 在标准郊狼优化算法的基础上设计4种操作算子和一种自适应学习机制, 使算法在搜索的过程中, 智能选择合适的操作算子, 并设计莱维飞行策略提高算法的全局寻优能力; 最后对自适应郊狼算法进行函数测试和离线航迹规划仿真。函数测试表明自适应郊狼算法具有较强的全局搜索能力, 离线航迹规划仿真表明自适应郊狼优化算法能适应不同维数的离线航迹规划问题。

关键词: 无人机, 航迹规划, 郊狼优化算法, 自适应学习机制, 莱维飞行

Abstract:

To satisfy the requirements of unmanned aerial vehicle (UAV) offline path planning for the algorithm's global search capability and robustness, a self-adaptive coyote optimization algorithm is designed to study UAV offline path planning from the perspective of optimization problems. A mathematical model is established for UAV offline path planning. On the basis of the coyote optimization algorithm, four operators and an adaptive learning mechanism are designed to enable the algorithm to intelligently select the appropriate operator during the search process, and design the Levy flight strategy to improve the algorithm's global search ability. Finally, the function test and offline path planning simulation are carried out for the self-adaptive coyote optimization algorithm. The function test shows that the self-adaptive coyote optimization algorithm has a strong global search ability, and the offline path planning simulation shows that the self-adaptive coyote optimization algorithm can adapt to the offline path planning problem of different dimensions.

Key words: unmanned aerial vehicle (UAV), path planning, coyote optimization algorithm, self-adaptive learning mechanism, Levy flight

中图分类号:

V249

陈都, 孟秀云. 基于自适应郊狼算法的无人机离线航迹规划[J]. 系统工程与电子技术, 2022, 44(2): 603-611.

Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm[J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.

图/表 6

图1

表1

SACOA和其他算法在CEC2017测试函数上的性能对比"

函数		SACOA	COA	PSO	GA	GWO
F1	Mean	1.093 443E-07	2.485 612E-12	1.773 076E+08	5.930 584E+06	9.158 465E+09
	Std.Dev	1.320 844E-07	1.948 230E-12	1.267 548E+08	7.074 796E+05	1.421 094E+09
	Rank	2	1	4	3	5
F2	Mean	2.329 923E+05	7.001 276E+04	4.362 386E+03	1.014 008E+05	1.114 722E+05
	Std.Dev	3.497 036E+04	1.473 092E+04	7.693 032E+02	1.518 693E+04	5.754 088E+03
	Rank	4	2	1	3	5
F3	Mean	2.630 489E+05	8.681 174E+04	5.159 271E+03	3.217 473E+05	1.019 149E+05
	Std.Dev	8.111 693E+04	2.599 363E+04	5.820 278E+02	2.583 825E+04	9.335 723E+03
	Rank	3	2	1	4	5
F4	Mean	1.179 824E-04	3.382 375E-4	1.876 899E+02	4.625 093E+01	1.490 700E+03
	Std.Dev	8.905 905E-05	3.174 470E-4	4.893 446E+01	3.863 320E+01	3.241 449E+02
	Rank	1	2	4	3	5
F5	Mean	2.466 655E+01	4.576 807E+01	2.159 181E+02	1.374 260E+02	2.940 587E+02
	Std.Dev	3.125 048E+00	9.738 384E+00	1.251 324E+01	2.091 182E+01	1.957 262E+01
	Rank	1	2	4	3	5
F6	Mean	6.691 720E-06	4.609 741E-03	2.132 414E-03	7.394 889E-06	1.085 735E-02
	Std.Dev	6.480 619E-06	5.419 744E-03	9.595 713E-04	6.63017 6E-06	2.799 322E-03
	Rank	1	4	3	2	5
F7	Mean	9.534 854E+01	1.477 339E+02	3.796 905E+02	7.519 979E+02	6.151 016E+02
	Std.Dev	9.397 924E+01	2.456 029E+01	1.110 813E+01	1.028 961E+02	3.396 531E+01
	Rank	1	2	3	4	5
F8	Mean	3.413 846E+01	4.865 346E+01	2.333 657E+02	1.233 538E+02	3.120 466E+02
	Std.Dev	7.876 400E+00	8.587 232E+00	1.226 479E+01	2.538 458E+01	1.521 375E+01
	Rank	1	2	4	3	5
F9	Mean	8.081 537E-01	9.136 564E+00	2.398 964E+02	8.4950 25E+02	5.345 025E+03
	Std.Dev	1.112 753E+00	1.380 183E+01	9.508 573E+01	1.873 324E+02	8.238 979E+02
	Rank	1	2	3	4	5
F10	Mean	1.214 608E+02	8.926 982E+03	7.319 038E+03	2.246 446E+03	8.618 090E+03
	Std.Dev	7.988 912E+01	8.627 269E+02	5.779 242E+02	5.056 926E+02	4.602 093E+02
	Rank	1	2	4	3	5
F11	Mean	1.516 405E+01	1.552 135E+01	2.263 788E+02	8.427 811E+01	4.670 863E+03
	Std.Dev	3.847 255E+00	4.318 616E+00	2.010 200E+01	3.388 736E+01	5.982 808E+02
	Rank	1	2	4	3	5
F12	Mean	2.046 781E+03	4.763 678E+02	1.483 114E+07	1.255 844E+06	2.212 823E+09
	Std.Dev	4.033 069E+02	3.560 081E+02	2.654 360E+07	9.493 159E+04	3.462 731E+08
	Rank	2	1	4	3	5
F13	Mean	2.621 488E+02	3.033 726E+02	1.153 537E+03	2.398 642E+05	7.341 457E+08
	Std.Dev	1.832 757E+02	1.988 014E+02	2.339 697E+03	4.925 763E+06	1.745 182E+08
	Rank	1	2	3	4	5
F14	Mean	5.251 672E+01	6.181 658E+01	1.157 832E+02	2.930 826E+02	3.082 443E+05
	Std.Dev	1.529 751E+01	1.809 699E+01	1.848 377E+01	4.983 813E+01	6.407 154E+04
	Rank	1	2	3	4	5
F15	Mean	1.339 617E+02	1.694 319E+02	1.182 831E+03	6.038 352E+04	5.692 922E+07
	Std.Dev	7.066 456E+01	1.737 006E+02	3.093 095E+03	1.185 091E+04	3.210 364E+07
	Rank	1	2	3	4	5
F16	Mean	1.187 990E+01	3.729 244E+01	1.395 410E+03	8.539 923E+02	1.417 066E+03
	Std.Dev	4.661 366E+00	3.541 467E+01	3.019 009E+02	3.847 808E+02	1.112 693E+02
	Rank	1	2	4	3	5
F17	Mean	4.985 393E+01	93.61 160E+01	1.028 323E+03	1.244 953E+03	1.425 701E+03
	Std.Dev	1.819 171E+01	41.94 910E+01	2.054 238E+02	3.151 768E+02	1.616 623E+02
	Rank	1	2	3	4	5
F18	Mean	4.364 206E+01	5.696 849E+01	1.055 646E+02	3.179 190E+03	2.261 037E+06
	Std.Dev	1.915 933E+01	3.355 479E+01	3.656 150E+01	1.192 158E+03	1.403 920E+06
	Rank	1	2	3	4	5
F19	Mean	5.908 400E+01	9.840 528E+01	9.171 463E+01	1.067 872E+04	1.813 256E+07
	Std.Dev	2.858 040E+01	2.939 930E+01	2.615 188E+01	2.563 532E+03	6.407 498E+06
	Rank	1	2	3	4	5
F20	Mean	5.631 365E+01	2.399 107E+02	5.791 148E+02	4.005 540E+02	8.353 983E+02
	Std.Dev	4.907 620E+01	1.656 535E+02	1.303 184E+02	2.036 536E+02	7.414 801E+01
	Rank	1	2	4	3	5
F21	Mean	2.230 077E+02	2.352 440E+02	4.881 213E+02	3.404 398E+02	5.240 545E+02
	Std.Dev	5.362 003E+00	4.171 875E+00	4.194 098E+01	3.060 803E+02	2.049 588E+01
	Rank	1	2	4	3	5
F22	Mean	2.215 014E+03	9.931 407E+03	1.687 351E+03	2.457 653E+03	1.533 249E+03
	Std.Dev	4.166 800E+03	2.534 992E+03	3.001 360E+03	6.142 509E+02	3.145 802E+02
	Rank	3	5	2	4	1
F23	Mean	3.338 374E+02	3.487 951E+02	7.443 997E+02	5.904 565E+02	8.272 068E+02
	Std.Dev	1.153 556E+01	1.027 021E+01	2.985 466E+01	3.533 852E+01	2.886 901E+01
	Rank	1	2	4	3	5
F24	Mean	3.285 980E+02	3.410 099E+02	6.545 900E+02	5.321 738E+02	7.559 693E+02
	Std.Dev	8.559 212E+00	7.540 451E+00	1.816 600E+01	2.400 561E+01	2.439 853E+01
	Rank	1	2	4	3	5
F25	Mean	4.198 295E+02	5.523 856E+02	6.143 588E+02	4.403 527E+02	1.797 553E+03
	Std.Dev	5.387 923E+01	8.034 752E+01	3.907 954E+01	5.469 670E+01	2.568 785E+02
	Rank	1	3	4	2	5
F26	Mean	3.000 000E+02	300.000 0E+02	7.806 914E+02	4.194 289E+03	3.993 395E+03
	Std.Dev	2.862 732E-06	1.192 357E-07	7.056 470E+02	6.529 694E+02	2.668 614E+02
	Rank	1	1	3	5	4
F27	Mean	5.000 112E+02	5.001 008E+02	5.807 666E+02	4.345 845E+02	1.077 033E+03
	Std.Dev	1.275 416E-04	1.556 748E-04	2.026 774E+01	3.612 366E+00	7.535 584E+01
	Rank	2	3	4	1	5
F28	Mean	5.00 0106E+02	5.002 148E+02	5.521 856E+02	5.515 278E+02	1.555 080E+03
	Std.Dev	1.896 448E-03	3.521 018E-02	9.384 375E+01	1.892 590E+01	1.219 588E+02
	Rank	1	2	4	3	5
F29	Mean	2.518 656E+02	3.192 407E+02	1.719 491E+03	1.661 386E+03	3.365 223E+03
	Std.Dev	1.345 417E+01	7.735 786E+01	1.194 623E+02	5.001 756E+02	1.741 382E+02
	Rank	1	2	4	3	5
F30	Mean	2.630 753E+02	2.7386 84E+02	2.614 784E+07	1.004 845E+05	1.884 786E+08
	Std.Dev	3.227 386E+01	5.902 472E+01	6.514 978E+06	1.838 352E+04	2.391 956E+07
	Rank	1	2	4	3	5
Aveage rank		1.30	2.13	3.40	3.27	4.83
Total rank		1	2	4	3	5

表1

图2

图3

图4

图5

参考文献 32

1	郜晨. 多无人机自主任务规划方法研究[D]. 南京: 南京航空航天大学, 2016.
	GAO C. Research on multi-UAV autonomous mission planning method[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016.
2	SALCEDO-SANZ S . Modern meta-heuristics based on nonlinear physics processes: a review of models and design procedures[J]. Physics Reports, 2016, 655, 1- 70. doi: 10.1016/j.physrep.2016.08.001
3	MAVROVOUNIOTIS M , LI C , YANG S . A survey of swarm intelligence for dynamic optimization: algorithms and applications[J]. Swarm and Evolutionary Computation, 2017, 33, 1- 17. doi: 10.1016/j.swevo.2016.12.005
4	WU Y . A survey on population-based meta-heuristic algorithms for motion planning of aircraft[J]. Swarm and Evolutionary Computation, 2021, 62, 100844. doi: 10.1016/j.swevo.2021.100844
5	SILVA A J , SILVA A M , MOTTA T C F , et al. Heuristic and genetic algorithm approaches for UAV path planning under critical situation[J]. International Journal on Artificial Intelligence Tools, 2017, 26 (1): 1760008. doi: 10.1142/S0218213017600089
6	SHAO S K , PENG Y , HE C L , et al. Efficient path planning for UAV formation via comprehensively improved particle swarm optimization[J]. ISA Transactions, 2020, 97, 415- 430. doi: 10.1016/j.isatra.2019.08.018
7	KONATOWSKI S, PAWŁOWSKI P. Ant colony optimization algorithm for UAV path planning[C]//Proc. of the IEEE 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering, 2018: 177-182.
8	ZHOU X J , GAO F , FANG X , et al. Improved bat algorithm for UAV path planning in three-dimensional space[J]. IEEE Access, 2021, 9, 20100- 20116. doi: 10.1109/ACCESS.2021.3054179
9	DEWANGAN R K , SHUKLA A , GODFREY W W . Three dimensional path planning using grey wolf optimizer for UAVs[J]. Applied Intelligence, 2019, 49 (6): 2201- 2217. doi: 10.1007/s10489-018-1384-y
10	钱洲元, 雷明. 面向无人机航迹规划的自适应乌贼算法[J]. 哈尔滨工业大学学报, 2019, 51 (10): 37- 46. doi: 10.11918/j.issn.0367-6234.201805004
	QIAN Z Y , LEI M . Adaptive cuttlefish algorithm for UAV path planning[J]. Journal of Harbin Institute of Technology, 2019, 51 (10): 37- 46. doi: 10.11918/j.issn.0367-6234.201805004
11	HUO L S , ZHU J H , LI Z M , et al. A hybrid differential symbiotic organisms search algorithm for UAV path planning[J]. Sensors, 2021, 21 (9): 3037. doi: 10.3390/s21093037
12	SAXENA P, TAYAL S, GUPTA R, et al. Three dimensional route planning for multiple unmanned aerial vehicles using salp swarm algorithm[J]. arXiv preprint, 2019. arXiv: 1911.10519.
13	GUPTA S , DEEP K . A novel random walk grey wolf optimizer[J]. Swarm and Evolutionary Computation, 2019, 44, 101- 112. doi: 10.1016/j.swevo.2018.01.001
14	YANG L , GUO J , LIU Y . Three-dimensional UAV cooperative path planning based on the MP-CGWO algorithm[J]. International Journal of Innovative Computing Information and Control, 2020, 16, 991- 1006.
15	DAS P K . Hybridization of kidney-inspired and sine-cosine algorithm for multi-robot path planning[J]. Arabian Journal for Science and Engineering, 2020, 45 (4): 2883- 2900. doi: 10.1007/s13369-019-04193-y
16	QU C Z , GAI W D , ZHONG M Y , et al. A novel reinforcement learning based grey wolf optimizer algorithm for unmanned aerial vehicles (UAVs) path planning[J]. Applied Soft Computing, 2020, 89, 106099. doi: 10.1016/j.asoc.2020.106099
17	GHAMBARI S, IDOUMGHAR L, JOURDAN L, et al. A hybrid evolutionary algorithm for offline UAV path planning[C]// Proc. of the International Conference on Artificial Evolution, 2019: 205-218.
18	WU X D , BAI W B , XIE Y E , et al. A hybrid algorithm of particle swarm optimization, metropolis criterion and RTS smoother for path planning of UAVs[J]. Applied Soft Computing, 2018, 73, 735- 747. doi: 10.1016/j.asoc.2018.09.011
19	DAS P K , BEHERA H S , DAS S , et al. A hybrid improved PSO-DV algorithm for multi-robot path planning in a clutter environment[J]. Neurocomputing, 2016, 207, 735- 753. doi: 10.1016/j.neucom.2016.05.057
20	WU Q , SHEN X D , JIN Y Z , et al. Intelligent beetle antennae search for UAV sensing and avoidance of obstacles[J]. Sensors, 2019, 19 (8): 1758. doi: 10.3390/s19081758
21	辛贵州. 无人飞行器航迹规划算法研究[D]. 哈尔滨: 哈尔滨工程大学, 2010.
	XIN G Z. Research on trajectory planning for UAV[D]. Harbin: Harbin Engineering University, 2010.
22	LI G , CHOU W . Path planning for mobile robot using self-adaptive learning particle swarm optimization[J]. Science China Information Sciences, 2018, 61 (5): 052204. doi: 10.1007/s11432-016-9115-2
23	QU C Z , GAI W D , ZHANG J , et al. A novel hybrid grey wolf optimizer algorithm for unmanned aerial vehicle (UAV) path planning[J]. Knowledge-Based Systems, 2020, 194, 105530. doi: 10.1016/j.knosys.2020.105530
24	YU X , LI C , ZHOU J F . A constrained differential evolution algorithm to solve UAV path planning in disaster scenarios[J]. Knowledge-Based Systems, 2020, 204, 106209. doi: 10.1016/j.knosys.2020.106209
25	PIEREZAN J, COELHO L D S. Coyote optimization algorithm: a new metaheuristic for global optimization problems[C]// Proc. of the IEEE Congress on Evolutionary Computation, 2018: 1-8.
26	WEISS G H . Aspects and applications of the random walk[M]. Elsevier Science & Technology, 1994.
27	HUMPHRIES N E , QUEIROZ N , DYER J R M , et al. Environmental context explains Lévy and Brownian movement patterns of marine predators[J]. Nature, 2010, 465 (7301): 1066- 1069. doi: 10.1038/nature09116
28	LEE C Y , YAO X . Evolutionary programming using mutations based on the Lévy probability distribution[J]. IEEE Trans.on Evolutionary Computation, 2004, 8 (1): 1- 13. doi: 10.1109/TEVC.2003.816583
29	HAKLI H , UGUZ H . A novel particle swarm optimization algorithm with Levy flight[J]. Applied Soft Computing, 2014, 23, 333- 345. doi: 10.1016/j.asoc.2014.06.034
30	AYDOGDU I · , AKIN A , SAKA M P . Design optimization of real world steel space frames using artificial bee colony algorithm with Levy flight distribution[J]. Advances in Engineering Software, 2016, 92, 1- 14. doi: 10.1016/j.advengsoft.2015.10.013
31	MANTEGNA R N . Fast, accurate algorithm for numerical simulation of Levy stable stochastic processes[J]. Physical Review E, 1994, 49 (5): 4677. doi: 10.1103/PhysRevE.49.4677
32	AWAD N H, ALI M Z, LIANG J J, et al. Problem definitions and evaluation criteria for the CEC 2017 special session and competition on single objective bound constrained real-parameter numerical optimization[R]. Singapore: Nanyang Technological University, 2016.

[1]	孙田野, 孙伟, 吴建军. 改进Quatre算法的无人机编队快速集结方法[J]. 系统工程与电子技术, 2022, 44(9): 2840-2848.
[2]	余婧, 雍恩米, 陈汉洋, 郝东, 张显才. 面向多无人机协同对地攻击的双层任务规划方法[J]. 系统工程与电子技术, 2022, 44(9): 2849-2857.
[3]	徐星光, 王晓峰, 姚璐, 任章. 固定翼无人机编队构型与通信拓扑优化[J]. 系统工程与电子技术, 2022, 44(9): 2936-2946.
[4]	杨建峰, 肖和业, 李亮, 白俊强, 董维浩. 基于模糊聚类和专家评分机制的无人机多层次模块划分方法[J]. 系统工程与电子技术, 2022, 44(8): 2530-2539.
[5]	卢元杰, 刘志敏, 孙智孝, 阚东. 基于模型的无人机系统架构综合评估方法[J]. 系统工程与电子技术, 2022, 44(4): 1239-1245.
[6]	李洪瑶, 李小强, 韩心中, 谢学立, 席建祥. 基于决策融合的多无人机协同目标检测识别算法[J]. 系统工程与电子技术, 2022, 44(3): 746-754.
[7]	张源原, 高阳, 朱鹏, 刘锦涛, 谷树山. 基于着色Petri网的无人机侦察战术规划[J]. 系统工程与电子技术, 2022, 44(3): 900-907.
[8]	谷旭平, 唐大全. 基于联邦滤波算法的无人机集群分层协同导航[J]. 系统工程与电子技术, 2022, 44(3): 967-976.
[9]	余雪勇, 朱烨, 邱礼翔, 朱洪波. 基于无人机辅助边缘计算系统的节能卸载策略[J]. 系统工程与电子技术, 2022, 44(3): 1022-1029.
[10]	杨兴家, 段克清, 李想, 祁炜. 无人机集群协同探测距离解模糊方法[J]. 系统工程与电子技术, 2022, 44(2): 480-489.
[11]	符小卫, 潘静. 无人机集群规避动态障碍物的分布式队形控制[J]. 系统工程与电子技术, 2022, 44(2): 529-537.
[12]	刘步花, 丁丹, 杨柳, 薛乃阳, 刘仲谦. 基于DNN的无人机数据OFDM传输技术[J]. 系统工程与电子技术, 2022, 44(2): 696-702.
[13]	吴志鹏, 张平, 李震, 黄磊, 刘畅, 高硕. 基于轻小型无人机雷达的植被高度反演方法[J]. 系统工程与电子技术, 2022, 44(12): 3667-3675.
[14]	王玉佳, 方伟, 徐涛, 余应福, 邓博元. 基于遗传模糊树的海空对抗无人机智能决策模型[J]. 系统工程与电子技术, 2022, 44(12): 3756-3765.
[15]	杨文奇, 卢建华, 姜旭, 王元鑫. 基于改进ESO的四旋翼姿态自抗扰控制器设计[J]. 系统工程与电子技术, 2022, 44(12): 3792-3799.