Hybrid particle swarm algorithm for multi-UAV cooperative task allocation

ZHANG Ruipeng; FENG Yanxiang; YANG Yikang

doi:10.7527/S1000-6893.2021.26011

ACTA AERONAUTICAET ASTRONAUTICA SINICA >

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

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

Electronics and Electrical Engineering and Control

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

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

Cite this article

ZHANG Ruipeng , FENG Yanxiang , YANG Yikang . Hybrid particle swarm algorithm for multi-UAV cooperative task allocation[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022 , 43(12) : 326011 -326011 . DOI: 10.7527/S1000-6893.2021.26011

References

[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

Outlines

模态框（Modal）标题

Abstract

Cite this article

References