Research on Collaborative Optimization Method of Multi-UAV Task Allocation and Path Planning

doi:10.16182/j.issn1004731x.joss.23-0012

Abstract

Abstract:

Aiming at the task requirements of multi-UAV to perform multi-target collaborative reconnaissance, a collaborative optimization method of multi-machine and multi-objective task allocation and path planning is proposed. Based on the partheno genetic algorithms (PGA), a cost function combined with the actual path cost is constructed through the Dubins curve. To further reduce the calculation cost, a clustering algorithm based on UAV detection distance is proposed, and the generated clustering point is used as a new waypoint of UAV. The simulation results show that considering the dangerous area and the large number of reconnaissance points, the algorithm can effectively complete the reconnaissance task allocation of the UAV and at the same time form a preliminary route. It improves the rationality and convergence speed of task assignment, and reduces the overall cost.

Key words: multi-UAV coordination, partheno genetic algorithms(PGA), task clustering, task allocation, path planning, collaborative optimization

CLC Number:

TP391.9

Xiao Peng, Xie Feng, Ni Haihong, Zhang Min, Tang Zhili, Li Ni. Research on Collaborative Optimization Method of Multi-UAV Task Allocation and Path Planning[J]. Journal of System Simulation, 2024, 36(5): 1141-1151.

Figures/Tables 21

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Fig. 11

Table 1

UAV information

UAV

编号

坐标/

速度/

( $m / s$ )

探测半径/

k m

最小转弯

半径/ $k m$

(30, 0)

100

0.5

(40, 0)

100

0.5

(50, 0)

100

0.5

Table 1

Table 2

Threat information

威胁编号	坐标	$R d$
1	(30, 65)	10
2	(65, 45)	10

Table 2

Fig. 12

Fig. 13

Fig. 14

Fig. 15

Fig. 16

Fig. 17

Fig. 18

Table 3

References 19

1	李文, 陈建. 有人机/无人机混合编队协同作战研究综述与展望[J]. 航天控制, 2017, 35(3): 90-96.
	Li Wen, Chen Jian. Review and Prospect of Cooperative Combat of Manned/Unmanned Aerial Vehicle Hybrid Formation[J]. Aerospace Control, 2017, 35(3): 90-96.
2	Gama Ricardo, Fernandes Hugo L. A Reinforcement Learning Approach to the Orienteering Problem with Time Windows[J]. Computers & Operations Research, 2021, 133: 105357.
3	Luo Zhihao, Poon Mark, Zhang Zhenzhen, et al. The Multi-visit Traveling Salesman Problem with Multi-drones[J]. Transportation Research Part C: Emerging Technologies, 2021, 128: 103172.
4	Temesgen Seyoum Alemayehu, Hoon Kim Jai. Efficient Nearest Neighbor Heuristic TSP Algorithms for Reducing Data Acquisition Latency of UAV Relay WSN[J]. Wireless Personal Communications, 2017, 95(3): 3271-3285.
5	金仙力, 李金刚. 基于遗传算法的多目标路径优化算法的研究[J]. 计算机技术与发展, 2018, 28(2): 54-58.
	Jin Xianli, Li Jingang. Research on Multi-target Path Optimization Algorithm Based on Genetic Algorithm[J]. Computer Technology and Development, 2018, 28(2): 54-58.
6	梁国伟, 王社伟, 赵雪森. 多无人机协同任务分配方法[J]. 火力与指挥控制, 2014, 39(11): 13-17.
	Liang Guowei, Wang Shewei, Zhao Xuesen. Method Research on Cooperative Task Allocation for Multiple UCAVs[J]. Fire Control & Command Control, 2014, 39(11): 13-17.
7	郝会成, 姜维, 李一军, 等. 基于Multi-Agent敏捷卫星动态任务规划问题[J]. 国防科技大学学报, 2013, 35(1): 53-59.
	Hao Huicheng, Jiang Wei, Li Yijun, et al. Research on Agile Satellite Dynamic Mission Planning Based on Multi-agent[J]. Journal of National University of Defense Technology, 2013, 35(1): 53-59.
8	Rasmussen S J, Shima Tal. Tree Search Algorithm for Assigning Cooperating UAVs to Multiple Tasks[J]. International Journal of Robust and Nonlinear Control, 2008, 18(2): 135-153.
9	Chen Lizhi, Liu Weili, Zhong Jinghui. An Efficient Multi-objective Ant Colony Optimization for Task Allocation of Heterogeneous Unmanned Aerial Vehicles[J]. Journal of Computational Science, 2022, 58: 101545.
10	刘超. 基于改进遗传算法的多无人机航路规划方法[J]. 火力与指挥控制, 2019, 44(1): 18-22.
	Liu Chao. Method of Path Planning for Multi-UAV Based on Improved Genetic Algorithm[J]. Fire Control & Command Control, 2019, 44(1): 18-22.
11	Liu Haoting, Ge Jianyue, Wang Yuan, et al. Multi-UAV Optimal Mission Assignment and Path Planning for Disaster Rescue Using Adaptive Genetic Algorithm and Improved Artificial Bee Colony Method[J]. Actuators, 2021, 11(1): 4.
12	王然然, 魏文领, 杨铭超, 等. 考虑协同航路规划的多无人机任务分配[J]. 航空学报, 2020, 41(增2): 21-32.
	Wang Ranran, Wei Wenling, Yang Mingchao, et al. Task Allocation of Multiple UAVs Considering Cooperative Route Planning[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S2): 21-32.
13	潘登, 高东, 郑建华. 均衡聚类市场拍卖机制的异构无人机集群任务规划方法[J]. 国防科技大学学报, 2022, 44(6): 151-162.
	Pan Deng, Gao Dong, Zheng Jianhua. Task Planning of Heterogeneous UAV Swarm Based on Balanced Clustering Market Auction Mechanism[J]. Journal of National University of Defense Technology, 2022, 44(6): 151-162.
14	朱创创, 梁晓龙, 何吕龙, 等. 群目标侦察航迹规划方法[J]. 火力与指挥控制, 2018, 43(1): 47-51.
	Zhu Chuangchuang, Liang Xiaolong, He Lülong, et al. Group Target Reconnaissance Flight Planning Method[J]. Fire Control & Command Control, 2018, 43(1): 47-51.
15	龙国庆, 祝小平, 董世友. 基于聚类算法的多无人机系统任务分配[J]. 火力与指挥控制, 2011, 36(12): 54-59.
	Long Guoqing, Zhu Xiaoping, Dong Shiyou. A Study on the Task Allocation Problem for Multi-UAV System Based on Clustering Algorithm[J]. Fire Control & Command Control, 2011, 36(12): 54-59.
16	Ma Yunhong, Zhang Heng, Zhang Yaozhong, et al. Coordinated Optimization Algorithm Combining GA with Cluster for Multi-UAVs to Multi-tasks Task Assignment and Path Planning[C]//2019 IEEE 15th International Conference on Control and Automation (ICCA). Piscataway, NJ, USA: IEEE, 2019: 1026-1031.
17	张富震, 朱耀琴. 复杂环境中多无人机协同侦察的任务分配方法[J]. 系统仿真学报, 2022, 34(10): 2293-2302.
	Zhang Fuzhen, Zhu Yaoqin. Task Allocation Method for Multi-UAV Cooperative Reconnaissance in Complex Environment[J]. Journal of System Simulation, 2022, 34(10): 2293-2302.
18	李文广, 胡永江, 孙世宇, 等. 基于最小转弯半径的无人机转弯航迹规划算法[J]. 计算机工程与设计, 2019, 40(10): 2849-2854.
	Li Wenguang, Hu Yongjiang, Sun Shiyu, et al. UAV Turning Path Planning Algorithm Based on Minimum Turning Radius[J]. Computer Engineering and Design, 2019, 40(10): 2849-2854.
19	Zhou Honglu, Song Mingli, Pedrycz Witold. A Comparative Study of Improved GA and PSO in Solving Multiple Traveling Salesmen Problem[J]. Applied Soft Computing, 2018, 64: 564-580.

规划算法	平均收敛步数	平均实际代价值	规划结果与实际结果的偏差/%	与原有算法相比任务代价值降低/%
未考虑协同优化	1 858	298.1	3.7	0
考虑协同优化	1 876	288.7	0	3.2
基于传统聚类法预处理的协同优化	1 240	275.7	0	7.5
基于改进聚类法预处理的协同优化	404	251.2	0	15.7

[1]	Lei Xu, Chen Jingyi, Chen Xiaoyang. Research on Path Planning of Warehouse Robot with Improved Harris Hawks Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1081-1092.
[2]	Liu Zesen, Bi Sheng, Guo Chuanhong, Wang Yankui, Dong Min. Deep Learning Based Local Path Planning Method for Moving Robots [J]. Journal of System Simulation, 2024, 36(5): 1199-1210.
[3]	Wang Xiaokang, Ji Jie, Liu Yang, He Qing. Path Planning of Unmanned Delivery Vehicle Based on Improved Q-learning Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1211-1221.
[4]	Jiang Zhaozhen, Wang Wenlong, Sun Wenqi. Path Planning Rapid Algorithm Based on Modified RRT* for Unmanned Surface Vessel [J]. Journal of System Simulation, 2024, 36(4): 888-900.
[5]	Zhang Rui, Zhou Li, Liu Zhengyang. Dynamic Path Planning for Mobile Robot Based on RRT* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(4): 957-968.
[6]	Li Gaoyang, Li Xiangfeng, Zhao Kang, Jin Yuchao, Yi Zhidong, Zuo Dunwen. Three-Dimensional Path Planning of UAV Based on All Particles Driving Wild Horse Optimizer Algorithm [J]. Journal of System Simulation, 2024, 36(3): 595-607.
[7]	Yu Xiang, Jiang Chen, Duan Sirui, Deng Qianrui. Path Planning for Improvement of A* Algorithm and Artificial Potential Field Method [J]. Journal of System Simulation, 2024, 36(3): 782-794.
[8]	Tang Yunchao, Qi Shaojun, Zhu Lixue, Zhuo Xianrong, Zhang Yunqi, Meng Fan. Obstacle Avoidance Motion in Mobile Robotics [J]. Journal of System Simulation, 2024, 36(1): 1-26.
[9]	Chen Dejun, Fang Zihao, Zeng Yunxiu, Xu Kai. Deceptive Path Planning in Fog of War [J]. Journal of System Simulation, 2023, 35(9): 1895-1908.
[10]	Li Wenjing, Luo Yanlin, Wang Yuhui, Zhu Li. Virtual Navigation Path Planning Based on Octree Potential Field for Endonasal Endoscope [J]. Journal of System Simulation, 2023, 35(9): 2054-2063.
[11]	Junqiang Lin, Hongjun Wang, Xiangjun Zou, Po Zhang, Chengen Li, Yipeng Zhou, Shujie Yao. Obstacle Avoidance Path Planning and Simulation of Mobile Picking Robot Based on DPPO [J]. Journal of System Simulation, 2023, 35(8): 1692-1704.
[12]	Laiyi Yang, Jing Bi, Haitao Yuan. Intelligent Path Planning for Mobile Robots Based on SAC Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1726-1736.
[13]	Menglong Cao, Wenbin Zhao, Zhiqiang Chen. Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorithm [J]. Journal of System Simulation, 2023, 35(8): 1768-1775.
[14]	Hailan Yang, Yongqiang Qi, Baolei Wu, Dan Rong, Miaoying Hong, Jun Wang. Path Planning of Mobile Robots Based on Memristor Reinforcement Learning in Dynamic Environment [J]. Journal of System Simulation, 2023, 35(7): 1619-1633.
[15]	Tengfei Zhang, Rong Hu, Bin Qian, Lü Yang. Learning Variable Neighborhood Search Algorithm for Transportation-assembly Collaborative Optimization Problem [J]. Journal of System Simulation, 2023, 35(6): 1260-1277.