基于CEA-GA的多无人机三维协同曲线航迹规划方法

文超; 董文瀚; 解武杰; 蔡鸣

doi:10.13700/j.bh.1001-5965.2021.0787

基于CEA-GA的多无人机三维协同曲线航迹规划方法

doi: 10.13700/j.bh.1001-5965.2021.0787

文超¹,
董文瀚^2, ,,
解武杰²,
蔡鸣²

1.
空军工程大学研究生院，西安 710038
2.
空军工程大学航空工程学院，西安 710038

详细信息

通讯作者:
E-mail：dongwenhan@sina.com

中图分类号: V221⁺.3；TB553
计量
- 文章访问数: 765
- HTML全文浏览量: 409
- PDF下载量: 22
- 被引次数: 0
出版历程
- 收稿日期: 2021-12-27
- 录用日期: 2022-03-11
- 网络出版日期: 2022-03-18
- 整期出版日期: 2023-11-30

Multi-UAVs 3D cooperative curve path planning method based on CEA-GA

1.
School of Graduate，Air Force Engineering University，Xi’an 710038，China
2.
College of Aeronautics Engineering，Air Force Engineering University，Xi’an 710038，China

More Information

Corresponding author: E-mail：dongwenhan@sina.com

摘要

摘要:
针对多无人机协同航迹规划求解计算复杂度高，收敛效率差等问题，提出一种基于混沌精英适应遗传算法（CEA-GA）的多无人机三维协同曲线航迹规划方法。利用层级规划思想，建立基于单机规划层-航迹平滑层-多机协同规划层的多无人机三维协同曲线航迹层级规划模型，将复杂约束规划问题分解为子函数优化求解问题，减小计算量；考虑到遗传算法（GA）求解高维复杂约束优化问题存在的性能局限，采用Tent混沌映射均匀初始化种群，以扩大个体搜索空间，丰富种群多样性，在此基础上，通过引入自适应遗传算子平衡算法的全局搜索与局部开发能力，帮助个体跳出局部最优，并采用适应度动态更新策略进一步提高算法的局部探索能力和收敛速度。将精英保留策略引入GA以更好地保证改进算法的全局收敛性。将CEA-GA应用于模型求解，仿真实验结果表明：CEA-GA具有较强的鲁棒性、较好的寻优性能和收敛效率，且能够为集群规划满足约束条件的协同曲线航迹，从而验证了所提方法的有效性和CEA-GA的优越性。
- 协同航迹规划 /
- 多无人机 /
- 混沌映射 /
- 遗传算法 /
- 精英保留
Abstract:
To address the problems of high computational complexity and poor convergence efficiency of multi-UAVs cooperative path planning, a multi-UAVs 3D cooperative curve path planning method based on chaos elite adaptive genetic algorithm (CEA-GA) is proposed. A multi-UAVs 3D cooperative curve path hierarchical planning model based on single UAV planning layer—path smoothing layer—multiple UAVs cooperative planning layer is established with the idea of hierarchical planning to transform the complex constrained planning problems into the sub-functional optimization solution problems to reduce the computational effort. Considering the performance limitations of genetic algorithm (GA) in solving high-dimensional complex constrained optimization problems, Tent chaotic mapping is used to uniformly initialize the population in order to expand the individual search space and enrich the population diversity. On this basis, the adaptive genetic operators are introduced to balance the global search and local exploitation capability of the algorithm, so as to help individuals jump out of the local optimum. Then, the fitness dynamic update strategy is adopted to further improve the local exploration ability and convergence speed of the algorithm. The elite retention strategy is introduced into the GA to better ensure the global convergence of the improved algorithm. CEA-GA is used to solve the proposed model, and the simulation results show that CEA-GA has strong robustness, good search performance and convergence efficiency, and can plan the cooperative curve path to satisfy the constraints for the swarms, thus verifying the effectiveness of the proposed method and the superiority of CEA-GA.
- cooperative path planning /
- multiple UAVs /
- chaotic mapping /
- genetic algorithm /
- elite retention

HTML全文

图 1 任务环境示意图

Figure 1. Mission environment diagram

下载: 全尺寸图片幻灯片

图 2 威胁体穿越判断

Figure 2. Judgment of crossing threats

下载: 全尺寸图片幻灯片

图 3 B样条曲线平滑效果

Figure 3. B-spline curve smoothing effect

下载: 全尺寸图片幻灯片

图 4 协同抵达时间机制

Figure 4. Mechanism of cooperative arrival time

下载: 全尺寸图片幻灯片

图 5 个体实值编码

Figure 5. Individual real-value encoding

下载: 全尺寸图片幻灯片

图 6 混沌映射对比示意图

Figure 6. Comparison diagram of chaotic mapping

下载: 全尺寸图片幻灯片

图 7 CEA-GA流程

Figure 7. Flowchart of CEA-GA

下载: 全尺寸图片幻灯片

图 8 多无人机协同航迹规划方法总体框架

Figure 8. General framework of multi-UAVs cooperative path planning method

下载: 全尺寸图片幻灯片

图 9 规划结果对比示意图

Figure 9. Comparison diagram of planning results

下载: 全尺寸图片幻灯片

图 10 算法迭代收敛曲线

Figure 10. Iterative convergence curves of algorithms

下载: 全尺寸图片幻灯片

图 11 单机规划层结果

Figure 11. Single UAV planning layer results

下载: 全尺寸图片幻灯片

图 12 多机协同规划层结果

Figure 12. Multi-UAV collaborative planning layer results

下载: 全尺寸图片幻灯片

图 13 空间协同关系

Figure 13. Airspace-coordinated relationship

下载: 全尺寸图片幻灯片

图 14 转弯角变化情况

Figure 14. Turning angle variation

下载: 全尺寸图片幻灯片

图 15 爬升/俯冲角变化情况

Figure 15. Climbing/diving angle variation

下载: 全尺寸图片幻灯片

表 1 威胁源参数

Table 1. Parameters of threats

威胁类型	位置坐标/km	高度/m	威胁半径/km
地空导弹	(80,46)	26	8
探测雷达	(70,20)	0	10
地空导弹	(69,68)	30	6
防空高炮	(36,56)	25	8
禁飞区域	(57,41)	20	6
探测雷达	(70,88)	0	10

下载: 导出CSV

表 2 航程信息统计结果

Table 2. Statistical results of voyage information

算法	最优航程/km	最差航程/km	平均值/km	标准差
GA	148.370	160.475	155.213	4.692
E-GA	146.193	158.868	151.591	5.432
EA-GA	140.822	146.967	143.584	3.585
CEA-GA	136.050	142.756	139.796	2.265
注：加黑数据表示各组实验统计中的最优结果。

下载: 导出CSV

表 3 适应值信息统计结果

Table 3. Statistical results of fitness information

算法	最佳适应	最差适应	平均值	标准差	平均耗时
GA	1.854	1.423	1.548	1.205×10⁻¹	18.829
E-GA	1.872	1.616	1.772	8.198×10⁻²	19.356
EA-GA	2.116	1.659	1.903	1.360×10⁻¹	20.468
CEA-GA	2.293	1.852	2.181	6.931×10⁻²	24.778
注：加黑数据表示各组实验统计中的最优结果。

下载: 导出CSV

表 4 候选航迹组信息统计结果

Table 4. Statistical results of candidate path group information

无人机	最优航程/km	最差航程/km	平均值/km	标准差
UAV-1	121.118	136.653	127.349	3.158
UAV-2	125.963	136.712	129.769	2.990
UAV-3	115.667	126.581	122.004	3.279

下载: 导出CSV

表 5 多机协同规划层信息

Table 5. Information of multi-UAVs collaborative planning layer

无人机	航迹长度/km	抵达时间/s	协同抵达时间/s	协同目标函数
UAV-1	125.495	[615.17,1476.41]	[624.97, 1393.34]	4.945
UAV-2	127.291	[624.97,1499.93]	[624.97, 1393.34]	4.945
UAV-3	118.434	[580.55,1393.34]	[624.97, 1393.34]	4.945

下载: 导出CSV

参考文献(34)

[1]	祁圣君, 井立, 王亚龙. 无人机系统及发展趋势综述[J]. 飞航导弹, 2018(4): 17-21. QI S J, JIN L, WANG Y L. Overview of UAV systems and trends[J]. Aerodynamic Missile Journal, 2018(4): 17-21(in Chinese).
[2]	印骏, 谭玲, 谭绍杰. 美军无人机的作战应用及其发展趋势[J]. 飞航导弹, 2010(8): 26-29. YIN J, TAN L, TAN S J. Operational application and development trend of US army UAV[J]. Aerodynamic Missile Journal, 2010(8): 26-29(in Chinese).
[3]	沈林成, 陈璟, 王楠. 飞行器任务规划技术综述[J]. 航空学报, 2014, 35(3): 593-606. SHEN L C, CHEN J, WANG N. Overview of air vehicle mission planning techniques[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(3): 593-606(in Chinese).
[4]	YU Z, SUN F C, LU X, et al. Overview of research on 3D path planning methods for rotor UAV[C]//2021 International Conference on Electronics, Circuits and Information Engineering (ECIE). Piscataway: IEEE Press, 2021: 368-371.
[5]	钱宇, 祝祯祎. 基于改进动态规划的无人机搜寻航迹规划研究[J]. 计算机仿真, 2021, 38(1): 32-36. QIAN Y, ZHU Z Y. Research on UAV searching path planning based on improved dynamic programming algorithm[J]. Computer Simulation, 2021, 38(1): 32-36(in Chinese).
[6]	MOKRANE A, BRAHAM A C, CHERKI B. UAV path planning based on dynamic programming algorithm on photogrammetric DEMs[C]//2020 International Conference on Electrical Engineering(ICEE). Piscataway: IEEE Press, 2020: 1-5.
[7]	WU X J, XU L, ZHEN R, et al. Biased sampling potentially guided intelligent bidirectional RRT algorithm for UAV path planning in 3D environment[J]. Mathematical Problems in Engineering, 2019, 2019(8): 1-12.
[8]	HUANG J, SUN W. A method of feasible trajectory planning for UAV formation based on bi-directional fast search tree[J]. Optik, 2020, 221(1): 165213.
[9]	聂俊岚, 张庆杰, 王艳芬. 基于加权Voronoi图的无人飞行器航迹规划[J]. 飞行力学, 2015, 33(4): 339-343. NIE J L, ZHANG Q J, WANG Y F. UAV path planning based on weighted-Voronoi diagram[J]. Flight Dynamics, 2015, 33(4): 339-343(in Chinese).
[10]	XIA C, CHEN X. The UAV dynamic path planning algorithm research based on Voronoi diagram[C]//The 26th Chinese Control and Decision Conference (2014 CCDC). Piscataway: IEEE Press, 2014: 1069-1071.
[11]	MANDLOI D, ARYA R, VERMA A K. Unmanned aerial vehicle path planning based on A* algorithm and its variants in 3d environment[J]. International Journal of System Assurance Engineering and Management, 2021, 12(1): 990-1000.
[12]	程凝怡, 刘志乾, 李昱奇. 一种基于Dijkstra的多约束条件下智能飞行器航迹规划算法[J]. 西北工业大学学报, 2020, 38(6): 1284-1290. doi: 10.1051/jnwpu/20203861284 CHENG N Y, LIU Z Q, LI Y Q. Path planning algorithm of Dijkstra-based intelligent aircraft under multiple constraints[J]. Journal of Northwestern Polytechnical University, 2020, 38(6): 1284-1290(in Chinese). doi: 10.1051/jnwpu/20203861284
[13]	YU X B, LI C L, 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
[14]	ZHANG H, DOU L, CAI C, et al. Three-dimensional unmanned aerial vehicle route planning using hybrid differential evolution[J]. Journal of Advanced Computational Intelligence and Intelligent Informatics, 2020, 24(7): 820-828.
[15]	李宪强, 马戎, 张伸, 等. 蚁群算法的改进设计及在航迹规划中的应用[J]. 航空学报, 2020, 41(S2): 213-219. LI X Q, MA R, ZHANG S, et al. Improved design of ant colony algorithm and its application in path planning[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S2): 213-219(in Chinese).
[16]	NAYEEM G M, FAN M, LI S, et al. A Modified particle swarm optimization for Autonomous UAV path planning in 3D environment[C]//ICONCS 2020: Cyber Security and Computer Science. Piscataway: IEEE Press, 2020, 325: 180-191.
[17]	胡中华, 赵敏, 姚敏, 等. 无人机航迹规划技术研究及发展趋势[J]. 航空电子技术, 2009, 40(2): 24-29. doi: 10.3969/j.issn.1006-141X.2009.02.006 HU Z H, ZHAO M, YAO M, et al. Research and development trend of path planning for unmanned air vehicle[J]. Avionics Technology, 2009, 40(2): 24-29(in Chinese). doi: 10.3969/j.issn.1006-141X.2009.02.006
[18]	TAHIR A, BÖLING J, HAGHBAYAN M H, et al. Swarms of unmanned aerial vehicles—A Survey[J]. Journal of Industrial Information Integration, 2019, 16: 100106. doi: 10.1016/j.jii.2019.100106
[19]	PAN C, WEN Y, JIE C, et al. Cooperative control for UCAVs path planning[C]//2010 8th World Congress on Intelligent Control and Automation. Piscataway: IEEE Press, 2010: 5259-5263.
[20]	SHORAKAEI H, VAHDANI M, IMANI B, et al. Optimal cooperative path planning of unmanned aerial vehicles by a parallel genetic algorithm[J]. Robotica, 2016, 34(4): 823-836. doi: 10.1017/S0263574714001878
[21]	蔡星娟, 胡钊鸣, 张志霞, 等. 基于高维多目标优化的多无人机协同航迹规划[J]. 中国科学:信息科学, 2021, 51(6): 985-996. CAI X J, HU Z M, ZHANG Z X, et al. Multi-UAV coordinated path planning based on many-objective optimization[J]. Scientia Sinica(Informationis), 2021, 51(6): 985-996(in Chinese).
[22]	LIU H, CHEN Q, PAN N, et al. Three-dimensional mountain complex terrain and heterogeneous multi-uav cooperative combat mission planning[J]. IEEE Access, 2020, 8: 197407-197419. doi: 10.1109/ACCESS.2020.3033408
[23]	单文昭, 崔乃刚, 黄蓓, 等. 基于PSO-HJ算法的多无人机协同航迹规划方法[J]. 中国惯性技术学报, 2020, 28(1): 122-128. SHAN W Z, CUI N G, HUANG B, et al. Multiple UAV cooperative path planning based on PSO-HJ method[J]. Journal of Chinese Inertial Technology, 2020, 28(1): 122-128(in Chinese).
[24]	李楠, 刘朋, 邓人博, 等. 基于改进遗传算法的无人机三维航路规划[J]. 计算机仿真, 2017, 34(12): 22-25. doi: 10.3969/j.issn.1006-9348.2017.12.006 LI N, LIU P, DENG R B, et al. Three dimensional path planning for unmanned aerial vehicles based on improved genetic algorithm[J]. Computer Simulation, 2017, 34(12): 22-25(in Chinese). doi: 10.3969/j.issn.1006-9348.2017.12.006
[25]	GAO M S, LIU Y X, WEI P F. Opposite and chaos searching genetic algorithm based for UAV path planning[C]//2020 IEEE 6th International Conference on Computer and Communications (ICCC). Piscataway: IEEE Press , 2020: 2364-2369.
[26]	WANG X H, MENG X Y. UAV online path planning based on improved genetic algorithm[C]//2019 Chinese Control Conference (CCC). Piscataway: IEEE Press, 2019: 4101-4106.
[27]	何庆, 吴意乐, 徐同伟. 改进遗传模拟退火算法在TSP优化中的应用[J]. 控制与决策, 2018, 33(2): 219-225. HE Q, WU Y L, XU T W. Application of improved genetic simulated annealing algorithm in TSP optimization[J]. Control and Decision, 2018, 33(2): 219-225(in Chinese).
[28]	王庆, 徐海明, 吕品, 等. 基于改进蚁群算法的多旋翼无人机航迹规划研究[J]. 合肥工业大学学报(自然科学版), 2021, 44(9): 1172-1178. WANG Q, XU H M, LV P, et al. Research on path planning of multi-rotor UAV based on improved ant colony algorithm[J]. Journal of Hefei University of Technology(Natural Science), 2021, 44(9): 1172-1178(in Chinese).
[29]	刘莉, 于成龙, 王祝, 等. 小型无人机快速三维航迹规划方法[J]. 系统工程与电子技术, 2013, 35(12): 2521-2526. LIU L, YU C L, WANG Z, et al. Fast 3D route planning method for small UAV[J]. Systems Engineering and Electronics, 2013, 35(12): 2521-2526(in Chinese).
[30]	冯峰. 基于三次B样条曲线的一些算法研究[D]. 武汉: 武汉大学, 2021: 11-19. FENG F. Some algorithm study based on cubic B-spline curve[D]. Wuhan: Wuhan University, 2021: 11-19(in Chinese).
[31]	HOLLAND J H. Adaptation in natural and artificial systems[M]. Ann Arbor: University of Michigan Press, 1975.
[32]	ZHANG Z X, YANG R N, LI H Y, et al. Antlion optimizer algorithm based on chaos search and its application[J]. Journal of Systems Engineering & Electronics, 2019, 30(2): 352-365.
[33]	滕志军, 吕金玲, 郭力文, 等. 一种基于Tent映射的混合灰狼优化的改进算法[J]. 哈尔滨工业大学学报, 2018, 50(11): 40-49. doi: 10.11918/j.issn.0367-6234.201806096 TENG Z J, LV J L, GUO L W, et al. An improved hybrid grey wolf optimization algorithm based on Tent mapping[J]. Journal of Harbin Institute of Technology, 2018, 50(11): 40-49(in Chinese). doi: 10.11918/j.issn.0367-6234.201806096
[34]	SRINIVAS M, PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Transactions on Systems Man & Cybernetics, 2002, 24(4): 656-667.