Review of Optimization Algorithms for UAV Routes

doi:10.3969/j.issn.1009-086x.2024.04.003

Abstract

Abstract:

With the increasing mission complexity and environmental uncertainty of UAV， the requirements for route planning also increase， and the complexity of the route planning problem gradually increases from single UAV route planning to multi-UAV planning， and from single mission to multi-mission. To find a solution to the UAV route planning problem， a comprehensive analysis from aspects of concept， connotation， task modeling and algorithm analysis is presented. To solve the problems of existing route planning algorithms， such as， poor optimal path effect， slow convergence speed and tendency of falling into local optimization， applications and problems of UAV route planning with A* algorithm， particle swarm algorithm， genetic algorithm as well as ant colony algorithm are analyzed， and directions of algorithm optimizations and improvements are proposed.

Key words: path planning, constraints, A* algorithm, particle swarm optimization（PSO）, genetic algorithm（GA）, ant colony optimization（ACO）

摘要：

随着无人机任务复杂性以及环境不确定性的不断提高，对航路规划的要求也随之提高，航路规划问题复杂度逐渐增加，由单无人机航路规划向多无人机规划发展，由单任务向多任务发展。针对无人机航路规划问题，从概念内涵、任务建模、算法解析等方面进行了综合分析。针对现有航路规划算法存在的最优路径效果较差、收敛速度慢以及易陷入局部最优等问题，重点分析了A*算法、粒子群算法、遗传算法、蚁群算法在无人机航路规划中的应用及存在的问题，提出了优化改进的方向。

关键词: 航路规划, 约束条件, A*算法, 粒子群算法, 遗传算法, 蚁群算法

CLC Number:

V279

Wenbiao HE, Yongjiang HU, Wenguang LI. Review of Optimization Algorithms for UAV Routes[J]. Modern Defense Technology, 2024, 52(4): 24-32.

何文彪, 胡永江, 李文广. 面向无人机航路的优化算法研究综述[J]. 现代防御技术, 2024, 52(4): 24-32.

Figures/Tables 5

Fig. 1 UAV route planning algorithm

Fig. 2 Flowchart of A* algorithm

Fig. 3 Flowchart of particle swarm algorithm

Fig. 4 Flowchart of genetic algorithm

Fig. 5 Flowchart of ACO algorithm

References 25

1	张志文，张鹏，毛虎平，等. 融合改进A*算法和动态窗口法的全局动态路径规划［J］. 电光与控制， 2021， 28（9）： 39-43.
	ZHANG Zhiwen， ZHANG Peng， MAO Huping， et al. Global Dynamic Path Planning Combining Improved A* Algorithm with Dynamic Window Approach［J］. Electronics Optics & Control， 2021， 28（9）： 39-43.
2	ZHANG Jing， WU Jun， SHEN Xiao， et al. Autonomous Land Vehicle Path Planning Algorithm Based on Improved Heuristic Function of A-Star［J］. International Journal of Advanced Robotic Systems， 2021， 18（5）： 17298814211042730.
3	姜月秋，李紫嫣，关启学，等. 基于改进A*算法的无人机路径规划研究［J］. 兵器装备工程学报， 2020， 41（9）： 160-164.
	JIANG Yueqiu， LI Ziyan， GUAN Qixue， et al. Research on UAV Path Planning Based on Improved A*Algorithms［J］. Journal of Ordnance Equipment Engineering， 2020， 41（9）： 160-164.
4	陈晓宏，储飞黄，方胜良，等. 基于剖分网格改进A*算法的航迹规划研究［J］. 电光与控制， 2022， 29（7）： 17-21.
	CHEN Xiaohong， CHU Feihuang， FANG Shengliang， et al. Trajectory Planning Based on A* Algorithm Improved by Subdivision Grid［J］. Electronics Optics & Control， 2022， 29（7）： 17-21.
5	TIAN Zhetong， DING Yan， SONG Jianmei， et al. 3D Path Planning of UAV Based on Improved A* Algorithm［C］∥ITM Web of Conferences. Les Ulis： EDP Sciences， 2017： 01015.
6	吴天羿，许继恒，刘建永，等. 基于改进A*算法的越野路径规划研究［J］. 计算机应用研究， 2013， 30（6）： 1724-1726.
	WU Tianyi， XU Jiheng， LIU Jianyong， et al. Research of Cross-Country Path Planning Based on Improved A^*Algorithm［J］. Application Research of Computers， 2013， 30（6）： 1724-1726.
7	LIN Mingxiu， YUAN Kai， SHI Chengzhi， et al. Path Planning of Mobile Robot Based on Improved A^*Algorithm［C］∥2017 29th Chinese Control And Decision Conference （CCDC）. Piscataway： IEEE， 2017： 3570-3576.
8	梁国强，康宇航，邢志川，等. 基于离散粒子群优化的无人机协同多任务分配［J］. 计算机仿真， 2018， 35（2）： 22-28.
	LIANG Guoqiang， KANG Yuhang， XING Zhichuan， et al. UAV Cooperative Multi-Task Assignment Based on Discrete Particle Swarm Optimization Algorithm［J］. Computer Simulation， 2018， 35（2）： 22-28.
9	方群，徐青. 基于改进粒子群算法的无人机三维航迹规划［J］. 西北工业大学学报， 2017， 35（1）： 66-73.
	FANG Qun， XU Qing. 3D Route Planning for UAV Based on Improved PSO Algorithm［J］. Journal of Northwestern Polytechnical University， 2017， 35（1）： 66-73.
10	唐汇禹，彭世蕤，孙经蛟，等. 基于混沌DESAPSO算法的无人机三维航迹规划［J］. 兵器装备工程学报， 2017， 38（2）： 92-96.
	TANG Huiyu， PENG Shirui， SUN Jingjiao， et al. 3-D Route Planning of UAV Based on Chaotic DESAPSO Algorithm［J］. Journal of Ordnance Equipment Engineering， 2017， 38（2）： 92-96.
11	吴振，吴红兰. 基于改进遗传算法的无人机航路规划［J］. 电子测量技术， 2021， 44（24）： 52-58.
	WU Zhen， WU Honglan. UAV Route Planning Based on the Improved Genetic Algorithm［J］. Electronic Measurement Technology， 2021， 44（24）： 52-58.
12	程泽新，李东生，高杨. 一种改进遗传算法的无人机航迹规划［J］. 计算机仿真， 2019， 36（12）： 31-35.
	CHENG Zexin， LI Dongsheng， GAO Yang. GASA Drone Path Planning to Improve Mutation Strategy［J］. Computer Simulation， 2019， 36（12）： 31-35.
13	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.
14	蔡星娟，胡钊鸣，张志霞，等. 基于高维多目标优化的多无人机协同航迹规划［J］. 中国科学（信息科学）， 2021， 51（6）： 985-996.
	CAI Xingjuan， HU Zhaoming， ZHANG Zhixia， et al. Multi-UAV Coordinated Path Planning Based on Many-Objective Optimization［J］. Scientia Sinica（Informationis）， 2021， 51（6）： 985-996.
15	GAO Mingsheng， LIU Yuxiang， WEI Pengfei. Opposite and Chaos Searching Genetic Algorithm Based for UAV Path Planning［C］∥2020 IEEE 6th International Conference on Computer and Communications （ICCC）. Piscataway： IEEE， 2020： 2364-2369.
16	WANG Xiaohai， MENG Xiuyun. UAV Online Path Planning Based on Improved Genetic Algorithm［C］∥2019 Chinese Control Conference （CCC）. Piscataway： IEEE， 2019： 4101-4106.
17	李文广，胡永江，庞强伟，等. 基于改进遗传算法的多无人机协同侦察航迹规划［J］. 中国惯性技术学报， 2020， 28（2）： 248-255.
	LI Wenguang， HU Yongjiang， PANG Qiangwei， et al. Track Planning of Multi-UAV Cooperative Reconnaissance Based on Improved Genetic Algorithm［J］. Journal of Chinese Inertial Technology， 2020， 28（2）： 248-255.
18	孔维立，王峰，周平华，等. 改进蚁群算法的无人机三维路径规划［J］. 电光与控制， 2023， 30（3）： 63-69.
	KONG Weili， WANG Feng， ZHOU Pinghua， et al. Three-Dimensional Path Planning of UAVs Based on Improved Ant Colony Algorithm［J］. Electronics Optics & Control， 2023， 30（3）： 63-69.
19	李涛，赵宏生. 基于进化蚁群算法的移动机器人路径优化［J］. 控制与决策， 2023， 38（3）： 612-620.
	LI Tao， ZHAO Hongsheng. Path Optimization for Mobile Robot Based on Evolutionary Ant Colony Algorithm［J］. Control and Decision， 2023， 38（3）： 612-620.
20	李志锟，赵倩楠. 融合人工势场蚁群算法的移动机器人路径规划［J］. 电光与控制， 2022， 29（11）： 118-124.
	LI Zhikun， ZHAO Qiannan. Path Planning of Mobile Robot Based on Artificial Potential Field and Ant Colony Algorithm［J］. Electronics Optics & Control， 2022， 29（11）： 118-124.
21	赵娜，陈越峰. 联合势场与蚁群算法的机器人路径规划［J］. 火力与指挥控制， 2021， 46（7）： 39-44.
	ZHAO Na， CHEN Yuefeng. Robot Path Planning Algorithm Based on Combination of Improved Potential Field and Ant Colony Algorithm［J］. Fire Control & Command Control， 2021， 46（7）： 39-44.
22	TAN Wei， HU Yongjiang， ZHAO Yuefei， et al. Heterogeneous Multi UAV Mission Planning Based on Ant Colony Algorithm Powered BP Neural Network［J］. Computational Intelligence and Neuroscience， 2021， 2021： 4369201.
23	樊永生，连云霞，杨臻. 改进烟花算法在虚拟士兵路径规划中的应用［J］. 计算机工程， 2018， 44（12）： 228-232.
	FAN Yongsheng， LIAN Yunxia， YANG Zhen. Application of Improved Fireworks Algorithm in Path Planning of Virtual Soldier［J］. Computer Engineering， 2018， 44（12）： 228-232.
24	李霜琳，何家皓，敖海跃，等. 基于鸽群优化算法的火星飞行器智能可视图法［J］. 飞行力学， 2020， 38（5）： 90-94.
	LI Shuanglin， HE Jiahao， AO Haiyue， et al. Intelligent Visibility Graph Algorithm of Mars Aircraft Based on Pigeon-Inspired Optimization［J］. Flight Dynamics， 2020， 38（5）： 90-94.
25	王杨斌，章伟，王为科，等. 改进Informed-RRT*的动态环境路径规划算法［J］. 电光与控制， 2022， 29（5）： 28-32.
	WANG Yangbin， ZHANG Wei， WANG Weike， et al. An Improved Informed-RRT* Algorithm for Path Planning in Dynamic Environment［J］. Electronics Optics & Control， 2022， 29（5）： 28-32.

[1]	Tianliang LI, Qiusheng LI, Zhen LIU, Yuman LIU. Research on Optimization for Energy Efficiency of Electromagnetic Gun Based on Genetic Algorithm [J]. Modern Defense Technology, 2024, 52(4): 146-153.
[2]	Linan WANG, Guanghui WEN, Xiaojian YI. Finite-time Attitude Consensus Control of Multiple Unmanned Aerial Vehicles Under State Constraints [J]. Modern Defense Technology, 2024, 52(2): 124-131.
[3]	Zhehao WANG, Tian LI, Haidong YAN, Yudong HU, Changsheng GAO. Improved Drag Acceleration Profile Design for Hypersonic Vehicles [J]. Modern Defense Technology, 2024, 52(2): 115-123.
[4]	Yuhao LIU, Bing ZHANG, Zijin FANG. Approach Orbit Design Method for Space Multi-target Glide Observation [J]. Modern Defense Technology, 2024, 52(1): 57-64.
[5]	Yang TAO, Yi ZHOU, Huangtao JIANG. Application of Improved Ant Colony Algorithm to Terrain Following Route Planning Problem [J]. Modern Defense Technology, 2024, 52(1): 34-40.
[6]	Shiqiao DU, Guilan LI, Jun KOU, He HAO, Tong WU, Guoqing QIN, Hongwei GAO. Fast Search of Quantum Measurement System Parameters via Particle Swarm Optimization [J]. Modern Defense Technology, 2023, 51(6): 155-161.
[7]	Feng-chu SUN, Xu-sheng GAN. Lateral Maneuver Path Planning of Two UAV Formation Air Combat [J]. Modern Defense Technology, 2022, 50(3): 109-118.
[8]	Yan SHI, Hang SUN, Yun-ge CHEN, Jue WANG. Calculation Analysis of the Distance Between Planned Waypoints of the Ship⁃to⁃Land Cruise Missile [J]. Modern Defense Technology, 2022, 50(1): 48-53.
[9]	MA Yan-yan, JIN Hong-bin, LI Hao, ZHANG Hui. Application of Improved PSO Algorithm in Radar-Net Deployment [J]. Modern Defense Technology, 2020, 48(3): 104-112.
[10]	SONG Bo-wen, WANG Mao-cai, DAI Guang-ming, BAO Qian, PENG Lei, SONG Zhi-ming, CHEN Xiao-yu. Missile Flight Planning System Based on Spatial Coverage Analysis [J]. Modern Defense Technology, 2020, 48(2): 15-21.
[11]	LI Chun, SONG Xiao-cheng, LI Fang-fang. Design and Simulation of Multi-UAVs Coordinated Formation Control Software Platform [J]. Modern Defense Technology, 2018, 46(6): 143-150.
[12]	YE Wen, ZHAO Jian-zhong, LÜ Xiao-feng, LIU Hua-wen. Multi-UAV Cooperation Path Planning Based on Decomposition Strategy and Niche Clonal Selection Algorithm [J]. Modern Defense Technology, 2018, 46(4): 21-26.