多无人机协同任务分配混合粒子群算法

张瑞鹏; 冯彦翔; 杨宜康

doi:10.7527/S1000-6893.2021.26011

航空学报 >

2022 , Vol. 43 >Issue 12: 326011 - 326011

DOI: https://doi.org/10.7527/S1000-6893.2021.26011

电子电气工程与控制

多无人机协同任务分配混合粒子群算法

张瑞鹏 ,
冯彦翔 ,
杨宜康

展开

西安交通大学自动化科学与工程学院, 西安 710049

收稿日期: 2021-06-23

修回日期: 2021-07-12

网络出版日期: 2021-09-06

基金资助

2020年度科技创新2030-"新一代人工智能"重大项目（2020AAA0108203）；国家自然科学基金（62003258）

收起

Hybrid particle swarm algorithm for multi-UAV cooperative task allocation

ZHANG Ruipeng ,
FENG Yanxiang ,
YANG Yikang

Expand

School of Automation Science and Engineering, Xi'an Jiaotong University, Xi'an 710049, China

Received date: 2021-06-23

Revised date: 2021-07-12

Online published: 2021-09-06

Supported by

2020 Science and Technology Innovation 2030-Key Project of "New Generation Artificial Intelligence" under Grant (2020AAA0108203); National Natural Science Foundation of China (62003258)

Fold

摘要

针对多无人机协同任务分配问题（MTAP），设计了一种综合考虑飞行航程、任务收益以及任务完成时间窗口的混合粒子群任务分配算法。首先，将粒子位置编码为一组任务分配向量，针对同时打击场景可能存在的死锁问题，设计了一种基于多打击任务有向图的死锁检测和修复算法，解码出对应一组可行的任务分配解或方案，实现粒子群算法解的离散化。另外，对于传统粒子群算法（PSO）容易陷入局部收敛的缺点，提出一种基于变邻域搜索算法的跳出局部收敛策略，并建立局部搜索启动概率准则，实现跳出局部收敛和计算开销的平衡。最后，将跳出局部收敛的策略嵌入到粒子群算法中，得到协同任务分配的混合粒子群算法（HPSO）。另外，针对新目标发现导致的初始计划失效问题，设计了一种基于匹配策略的局部任务重分配方法。仿真实验证明，所提出的混合粒子群算法能够有效解决异构多无人机同时打击场景中的任务分配问题。

关键词： 多无人机; 协同任务分配; 同时打击; 粒子群算法; 局部收敛; 变邻域搜索; 任务重分配

本文引用格式

张瑞鹏 , 冯彦翔 , 杨宜康 . 多无人机协同任务分配混合粒子群算法[J]. 航空学报, 2022 , 43(12) : 326011 -326011 . DOI: 10.7527/S1000-6893.2021.26011

Abstract

This paper proposes a hybrid particle swarm optimization algorithm for solving the Multi-UAV Task Allocation Problem (MTAP), which takes flight range, task revenue, and task completion time window into consideration. First, particle positions are encoded as a set of task assignment vectors, and a deadlock detection and repair algorithm based on digraphs of multi-strike tasks is designed for the possible deadlock problem of simultaneous strike scenarios, decoding the corresponding set of feasible task assignment solutions or schemes to realize the discretization of particle swarm algorithm solutions. Then, to overcome the drawback of premature convergence for traditional Particle Swarm Optimization (PSO), a policy of jumping local optimum is proposed based on variable neighborhood search, so that the balance between jumping local convergence and computational cost is achieved. Finally, an Hybrid Partide Swarm Optimization(HPSO) is obtained by embedding the proposed strategy into traditional PSO, which can be used to solve the underlying MTAP. A local task reassignment method based on the matching strategy is also designed for failure of the initial plan caused by new target discovery. Simulation experiments show that the proposed HPSO algorithm can effectively solve the task assignment problem in heterogeneous multi-UAV simultaneous strike scenarios.

Key words： multi-unmanned-aerial-vehicle; task assignment problem; simultaneous strike; particle swarm optimization algorithm; local convergence; variable neighborhood search; task rescheduling

参考文献

[1] 岳源, 屈高敏. 分布式多无人机协同侦察目标分配研究[J]. 兵器装备工程学报, 2018, 39(3):57-61, 82. YUE Y, QU G M. Research on distributed multi UAV cooperative reconnaissance task allocation[J]. Journal of Ordnance Equipment Engineering, 2018, 39(3):57-61, 82(in Chinese).
[2] 赵学远, 周绍磊, 王帅磊, 等. 多无人机系统编队控制综述[J]. 仪表技术, 2020(1):40-42. ZHAO X Y, ZHOU S L, WANG S L, et al. Review on the formation control of the multi-UAV system[J]. Instrumentation Technology, 2020(1):40-42(in Chinese).
[3] 齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规划研究综述[J]. 智能系统学报, 2020, 15(2):204-217. QI X G, LI B, FAN Y S, et al. A survey of mission planning on UAVs systems based on multiple constraints[J]. CAAI Transactions on Intelligent Systems, 2020, 15(2):204-217(in Chinese).
[4] CHEN Y B, YANG D, YU J Q. Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm[J]. IEEE Transactions on Aerospace and Electronic Systems, 2018, 54(6):2853-2872.
[5] 范厚明, 刘文琪, 徐振林, 等. 混合粒子群算法求解带软时间窗的VRPSPD问题[J]. 计算机工程与应用, 2018, 54(19):221-229. FAN H M, LIU W Q, XU Z L, et al. Hybrid particle swarm optimization for solving VRPSPD problems with soft time windows[J]. Computer Engineering and Applications, 2018, 54(19):221-229(in Chinese).
[6] 沈林成, 牛轶峰, 朱华勇. 多无人机自主协同控制理论与方法[M]. 北京:国防工业出版社, 2013. SHEN L C, NIU Y F, ZHU H Y. Theories and methods of autonomous cooperative control for multiple UAVs[M]. Beijing:National Defense Industry Press, 2013(in Chinese).
[7] ZOU D X, LIU H K, GAO L Q, et al. An improved differential evolution algorithm for the task assignment problem[J]. Engineering Applications of Artificial Intelligence, 2011, 24(4):616-624.
[8] SALMAN A, AHMAD I, AL-RUSHOOD H, et al. Solving the task assignment problem using Harmony Search algorithm[J]. Evolving Systems, 2013, 4(3):153-169.
[9] 苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配[J]. 航空学报, 2008, 29(S1):184-191. SU F, CHEN Y, SHEN L C. UAV cooperative multi-task assignment based on ant colony algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2008, 29(S1):184-191(in Chinese).
[10] POONGOTHAI M, RAJESWARI A. A hybrid ant colony tabu search algorithm for solving task assignment problem in heterogeneous processors[C]//Proceedings of the International Conference on Soft Computing Systems. New Delhi:Springer India, 2015:1-11.
[11] 王健, 郭建胜, 慕容政, 等. 带有专家信度的无人机任务分配最小风险问题[J]. 控制与决策, 2019, 34(9):2036-2040. WANG J, GUO J S, MURONG Z, et al. Minimum-risk problem of unmanned aerial vehicle task allocation with expert belief degree[J]. Control and Decision, 2019, 34(9):2036-2040(in Chinese).
[12] 王然然, 魏文领, 杨铭超, 等. 考虑协同航路规划的多无人机任务分配[J]. 航空学报, 2020, 41(S2):724234. WANG R R, WEI W L, YANG M C, et al. Task allocation of multiple UAVs considering cooperative route planning[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41(S2):724234(in Chinese).
[13] 宋育武, 贾林通, 李娟, 等. 异构型无人机群体并行任务分配算法[J]. 科学技术与工程, 2020, 20(4):1492-1497. SONG Y W, JIA L T, LI J, et al. Parallel task assignment algorithm for heterogeneous unmanned aerial vehicles[J]. Science Technology and Engineering, 2020, 20(4):1492-1497(in Chinese).
[14] EG COFFMAN E, ELPHICK M, SHOSHANI A. System deadlocks[J]. ACM Computing Surveys, 1971, 3(2):67-78.
[15] DENG Q B, YU J Q, MEI Y S. Deadlock-free consecutive task assignment of multiple heterogeneous unmanned aerial vehicles[J]. Journal of Aircraft, 2014, 51(2):596-605.
[16] CHEN Y B, YANG D, YU J Q. Multi-UAV task assignment with parameter and time-sensitive uncertainties using modified two-part wolf pack search algorithm[J]. IEEE Transactions on Aerospace and Electronic Systems, 2018, 54(6):2853-2872.
[17] MORATORI P, PETROVIC S, VÁZQUEZ A. Match-up strategies for job shop rescheduling[C]//New Frontiers in Applied Artificial Intelligence. Berlin:Springer, 2008:119-128.
[18] ZAKARIA Z, PETROVIC S. Genetic algorithms for match-up rescheduling of the flexible manufacturing systems[J]. Computers & Industrial Engineering, 2012, 62(2):670-686.
[19] WANG Z, ZHANG J H, YANG S X. An improved particle swarm optimization algorithm for dynamic job shop scheduling problems with random job arrivals[J]. Swarm and Evolutionary Computation, 2019, 51:100594.
[20] 韩庆田. 基于改进PSO的多UAV协同任务分配研究[J]. 兵器装备工程学报, 2019, 40(11):74-78. HAN Q T. Research on cooperate task allocation of multiple UAVs based on PSO algorithm[J]. Journal of Ordnance Equipment Engineering, 2019, 40(11):74-78(in Chinese).
[21] 赵雪森, 王社伟, 邵校. 基于改进量子粒子群优化算法的多UCAV协同任务分配研究[J]. 四川兵工学报, 2015, 36(10):120-124. ZHAO X S, WANG S W, SHAO X. Cooperative task allocation for multiple UCAV based on improved quantum-behaved particle swarm optimization algorithm[J]. Journal of Sichuan Ordnance, 2015, 36(10):120-124(in Chinese).
[22] 梁国强, 康宇航, 邢志川, 等. 基于离散粒子群优化的无人机协同多任务分配[J]. 计算机仿真, 2018, 35(2):22-28. LIANG G Q, KANG Y H, XING Z C, et al. UAV cooperative multi-task assignment based on discrete particle swarm optimization algorithm[J]. Computer Simulation, 2018, 35(2):22-28(in Chinese).
[23] AKBARI R, ZIARATI K. A rank based particle swarm optimization algorithm with dynamic adaptation[J]. Journal of Computational and Applied Mathematics, 2011, 235(8):2694-2714.
[24] ZHU Z X, TANG B W, YUAN J P. Multirobot task allocation based on an improved particle swarm optimization approach[J]. International Journal of Advanced Robotic Systems, 2017, 14(3):172988141771031.
[25] 胡月, 丁萌, 姜欣言, 等. 一种面向有人/无人直升机协同打击的地面目标任务分配方法[J]. 航空科学技术, 2019, 30(10):64-69. HU Y, DING M, JIANG X Y, et al. Ground target assignment of manned/unmanned helicopters for coordinated attack[J]. Aeronautical Science & Technology, 2019, 30(10):64-69(in Chinese).
[26] 李炜, 张伟. 基于粒子群算法的多无人机任务分配方法[J]. 控制与决策, 2010, 25(9):1359-1363, 1368. LI W, ZHANG W. Method of tasks allocation of multi-UAVs based on particles swarm optimization[J]. Control and Decision, 2010, 25(9):1359-1363, 1368(in Chinese).
[27] HAN L B, XING K Y, CHEN X, et al. A Petri net-based particle swarm optimization approach for scheduling deadlock-prone flexible manufacturing systems[J]. Journal of Intelligent Manufacturing, 2018, 29(5):1083-1096.
[28] MIYAMOTO T, TSUJIMOTO N, KUMAGAI S. A cooperative algorithm for autonomous distributed vehicle systems with finite buffer capacity[J]. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 2005, E88-A(11):3036-3044.
[29] 范厚明, 刘鹏程, 吴嘉鑫, 等. 集货需求随机的同时配集货VRP及混合变邻域搜索算法[J]. 系统工程理论与实践, 2019, 39(10):2646-2659. FAN H M, LIU P C, WU J X, et al. Hybrid genetic algorithm with variable neighborhood descent for the vehicle routing problem with simultaneous stochastic pickup and deterministic delivery[J]. Systems Engineering-Theory & Practice, 2019, 39(10):2646-2659(in Chinese).
[30] 仲筱艳, 黄大庆. 一种典型任务的多无人机协同任务分配算法研究[J]. 自动化技术与应用, 2016, 35(8):7-12, 22. ZHONG X Y, HUANG D Q. Research of cooperation task allocation algorithm for a kind of typical mission[J]. Techniques of Automation and Applications, 2016, 35(8):7-12, 22(in Chinese).
[31] TURKER T, SAHINGOZ O K, YILMAZ G. 2D path planning for UAVs in radar threatening environment using simulated annealing algorithm[C]//2015 International Conference on Unmanned Aircraft Systems (ICUAS). Piscataway:IEEE Press,2015:56-61.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献