多机任务分配与路径规划协同优化法研究

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

系统仿真学报 ›› 2024, Vol. 36 ›› Issue (5): 1141-1151.doi: 10.16182/j.issn1004731x.joss.23-0012

多机任务分配与路径规划协同优化法研究

肖鹏¹(), 谢锋², 倪海鸿¹, 张敏¹, 汤志荔¹^,³, 李霓¹^,³()

^1.西北工业大学航空学院, 陕西西安 710072
^2.中国航空工业集团公司成都飞机设计研究所, 四川成都 610091
^3.西安市飞行器智能认知与控制重点实验室, 陕西西安 710072

收稿日期:2023-01-04 修回日期:2023-02-14 出版日期:2024-05-15 发布日期:2024-05-21
通讯作者: 李霓 E-mail:2018294150@qq.com;lini@nwpu.edu.cn
第一作者简介:肖鹏(1997-)，男，硕士，研究方向为多无人机智能协同。E-mail：2018294150@qq.com
基金资助:
国家自然科学基金(62003272);特色学科基础研究(G2022WD)

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

Xiao Peng¹(), Xie Feng², Ni Haihong¹, Zhang Min¹, Tang Zhili¹^,³, Li Ni¹^,³()

^1.School of Aeronautics, Northwestern Polytechnical University, Xi’an 710072, China
^2.Chengdu Aircraft Design and Research Institute, Aviation Industry Corporation of China, Chengdu 610091, China
^3.Xi’an Key Laboratory of Intelligent Cognition and Control of Aircraft, Xi’an 710072, China

Received:2023-01-04 Revised:2023-02-14 Online:2024-05-15 Published:2024-05-21
Contact: Li Ni E-mail:2018294150@qq.com;lini@nwpu.edu.cn

摘要/Abstract

摘要：

针对多无人机执行多目标协同侦察的任务需求，提出了多机多目标任务分配与路径规划的协同优化方法。以单亲遗传算法(partheno genetic algorithms, PGA)为基础，基于Dubins曲线构建了与实际路径代价相结合的代价函数；为进一步减小计算量，提出了基于无人机探测距离的聚类算法，将生成的聚类点作为无人机新的航路点。仿真结果表明：在考虑禁飞区域以及侦察点繁多情况下，该算法能够有效完成无人机的侦察任务分配并同时形成初步航路，提高了任务分配的合理性和收敛速度，并降低了全局代价。

关键词: 多机协同, 单亲遗传算法, 任务聚类, 任务分配, 航路规划, 协同优化

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

中图分类号:

TP391.9

肖鹏,谢锋,倪海鸿等 . 多机任务分配与路径规划协同优化法研究[J]. 系统仿真学报, 2024, 36(5): 1141-1151.

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

图/表 21

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

表1

无人机信息

UAV

编号

坐标/

速度/

( $m / s$ )

探测半径/

k m

最小转弯

半径/ $k m$

(30, 0)

100

0.5

(40, 0)

100

0.5

(50, 0)

100

0.5

表1

表2

威胁信息 (km)

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

表2

图12

图13

图14

图15

图16

图17

图18

表3

参考文献 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]	程洁, 郑远, 李诚龙, 江波. 面向超低空物流场景的多机协同航迹规划算法[J]. 系统仿真学报, 2024, 36(1): 50-66.
[2]	刘家义, 王刚, 付强, 郭相科, 王思远. 基于分配策略优化算法的智能防空任务分配[J]. 系统仿真学报, 2023, 35(8): 1705-1716.
[3]	张腾飞, 胡蓉, 钱斌, 吕阳. 学习型变邻域搜索算法求解运输-装配协同优化问题[J]. 系统仿真学报, 2023, 35(6): 1260-1277.
[4]	牛双诚, 晋玉强, 寇昆湖. 基于区块链的多无人机协同任务分配方法研究[J]. 系统仿真学报, 2023, 35(5): 949-956.
[5]	马悦, 吴琳, 郭圣明. 作战任务分配建模及求解方法研究[J]. 系统仿真学报, 2023, 35(4): 887-898.
[6]	古鹏飞, 张霖, 陈真, 叶俊杰. 基于X语言的起飞场景民机协同设计与仿真一体化方法[J]. 系统仿真学报, 2022, 34(5): 929-943.
[7]	冯开团, 袁杰. 基于改进注水算法的离散车间任务分配问题研究[J]. 系统仿真学报, 2022, 34(4): 768-776.
[8]	张富震, 朱耀琴. 复杂环境中多无人机协同侦察的任务分配方法[J]. 系统仿真学报, 2022, 34(10): 2293-2302.
[9]	魏瑞轩, 吴子沉. 无人机集群实时任务分配方法研究[J]. 系统仿真学报, 2021, 33(7): 1574-1581.
[10]	史岩, 张立华, 董受全, 王珏. 基于ACO算法和Bezier曲线优化的巡航导弹航路规划[J]. 系统仿真学报, 2020, 32(1): 122-129.
[11]	谭亚新, 罗建华, 范锐, 董志明. 一种基于作战编成并行仿真方法及其实现[J]. 系统仿真学报, 2019, 31(11): 2350-2355.
[12]	张小平, 饶盛华, 张铸, 赵轩. 基于混沌果蝇算法的SRM多目标协同优化研究[J]. 系统仿真学报, 2018, 30(7): 2640-2647.
[13]	张静华, 韩璞. 多算法多种群协同优化差分进化算法[J]. 系统仿真学报, 2018, 30(5): 1690-1699.
[14]	汪汝根, 李为民, 刘永兰, 刘金松. 无人机集群组网任务分配方法研究[J]. 系统仿真学报, 2018, 30(12): 4794-4802.
[15]	陈文杰, 王艳. 离散制造过程生产协同能耗优化调度方法[J]. 系统仿真学报, 2018, 30(11): 4367-4375.

多机任务分配与路径规划协同优化法研究

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 21

参考文献 19

相关文章 15

编辑推荐

Metrics

本文评价