Improved Particle Swarm Optimization Algorithm for Cooperative Task Assignment of Multiple vehicles

doi:10.12382/bgxb.2022.0968

Abstract

Abstract:

An improved particle swarm optimization (PSO) algorithm for multi-aircraft cooperative task assignment is proposed. The corresponding mathematical model is developed by considering the constraints of the aircraft’s capability, the threat cost, the range cost, and the benefits obtained by completing the tasks. The position attribute of particles is encoded as a set of task assignment vectors, from which we can decode the task assignment solution such that the PSO solution is discretized. In order to solve the problem that the PSO algorithm can easily fall into local convergence, a strategy of jumping out of the local convergence is proposed. Based on the simulated annealing algorithm, this strategy first generates new particles, and then decides whether to retain the new particles with a certain probability. Finally, this jumping-out strategy is applied to the conventional PSO algorithm so as to establish an improved one that can be used for multi-aircraft cooperative task assignment. The digital simulation results verify the effectiveness of the proposed algorithm.

Key words: multi-aircraft cooperation, task assignment, particle swarm optimization algorithm, local convergence, simulated annealing

CLC Number:

TJ301

WANG Lei, XU Chao, LI Miao, ZHAO Huiwu. Improved Particle Swarm Optimization Algorithm for Cooperative Task Assignment of Multiple vehicles[J]. Acta Armamentarii, 2023, 44(8): 2224-2232.

Figures/Tables 8

References 20

[1]	牛轶峰, 肖湘江, 柯冠岩. 无人机集群作战概念及关键技术分析[J]. 国防科技, 2013, 34(5):37-43.
	NIU Y F, XIAO X J, KE G Y. Operation concept and key techniques of unmanned aerial vehicle swarms[J]. National defense science and technology, 2013, 34(5):37-43 (in Chinese)
[2]	ZHU M J, QIN Z, XING J K. Task assignment scheme of multi-uav based on single-unit combinatorial auction[C]// Proceedings of International Conference on Electrical and Control Engineering. Wuhan, China:IEEE. 2010: 2232-2235.
[3]	齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规划研究综述[J]. 智能系统学报, 2020, 15(2):204-217.
	QI X G, LI B, FAN Y S, et al. A survey of mission planning on UAV system based on multi-constraints[J]. CAAI transactions on intelligent systems, 2020, 15(2): 204-217. (in Chinese)
[4]	EDISON E, SHIMA T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2011, 38(1):340-356. doi: 10.1016/j.cor.2010.06.001 URL
[5]	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. doi: 10.2514/1.C032309 URL
[6]	韩健. 基于多Agent的无人机协作控制[D]. 哈尔滨: 哈尔滨工业大学, 2012.
	HAN J. Cooperative control of UAV based on multi-agent system[D]. Harbin: Harbin Institute of Technology, 2012. (in Chinese)
[7]	WU W N, CUI N G, SHAN W Z, et al. Distributed task allocation for multiple heterogeneous UAVs based on consensus algorithm and online cooperative strategy[J]. Aircraft engineering, 2018, 90(9):1464-1473.
[8]	GAUTHAM P D, THOMAS M M, SONYA A C, et al. A distributed task allocation algorithm for a multi-robot system in healthcare facilities[J]. Journal of Intelligent and Robotic Systems, 2015, 80(1):33-58. doi: 10.1007/s10846-014-0154-2 URL
[9]	FORSMO E J, GRØTLI E I, FOSSEN T I, et al. Optimal search mission with unmanned aerial vehicles using mixed integer linear programming[C]// Proceedings of 2013 International conference on unmanned aircraft systems. Atlanta, GA, US:IEEE, 2013:253-259.
[10]	苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配[J]. 航空学报, 2008, 29(5): 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(5): 184-191. (in Chinese)
[11]	KURDI H, HOW J, BAUTISTA G. Bio-inspired algorithm for task allocation in multi-UAV search and rescue missions[C]// Proceedings of Guidance, Navigation, & Control Conference. San Diego, CA, US: AIAA, 2016:2016-1377.
[12]	CHOI H, KIM Y, KIM H. Genetic algorithm based decentralized task assignment for multiple unmanned aerial vehicles in dynamic environments[J]. International Journal of Aeronautical and Space science, 2011, 12(12):163-174.
[13]	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. doi: 10.1016/j.engappai.2010.12.002 URL
[14]	AYED S, IMTIAZ A, HANAA A, et al. Solving the task assignment problem using Harmony Search algorithm[J]. Evolving Systems, 2013, 4: 153-169. doi: 10.1007/s12530-012-9058-1 URL
[15]	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):1-22.
[16]	李炜, 张伟. 基于粒子群算法的多无人机任务分配方法[J]. 控制与决策, 2010, 25(9):1359-1363.
	LI Y, ZHANG W. Method of tasks allocation of multi-UAVs based on particles swarm optimization[J]. Control and decision, 2010, 25(9):1359-1363. (in Chinese)
[17]	DARRAH M A, NILAND W M, STOLARIK B M, et al. UAV cooperative task assignments for a SEAD mission using genetic algorithms[C]// Proceedings of AIAA Guidance, Navigation, and Control Conference and Exhibit. Keystone, CO, US: AIAA, 2006:2006-6456.
[18]	KLYNE A, MERRICK K. Intrinsically motivated particle swarm optimization applied to task allocation for workplace hazard detection[J]. Adaptive Behavior, 2016, 24(4): 219-236. doi: 10.1177/1059712316651686 URL
[19]	李鹏, 李兵舰, 亓亮, 等. 一种改进的粒子群优化算法及其在无人机航路规划中的应用[J]. 舰船电子对抗, 2019, 42(5):59-64.
	LI P, LI B J, QI L, et al. An improved particle swarm optimization algorithm and its application to UAV route planning[J]. Shipboard Electronic Countermeasure, 2019, 42(5):59-64. (in Chinese)
[20]	熊华捷, 蔚保国, 何成龙. 基于改进粒子群算法的UAV航迹规划方法[J]. 计算机测量与控制, 2020, 28(2):144-147.
	XIONG H J, WEI B G, HE C L. UAV path planning method based on improved PSO[J]. Compute Measurement and Control, 2020, 28(2):144-147. (in Chinese)

A_k	2	2	2	2	3	3	2	2	1	1	1	1	1	1
Y_k	0.02	0.8	0.85	0.71	1.30	1.31	0.28	0.79	1.66	2.86	2.93	2.34	1.33	2.77
Z_k	-1.21	0.62	0.73	1.22	0.26	0.21	0.60	0.97	1.25	1.93	0.34	0.01	0.21	1.21

A_k	2	2	2	2	3	3	2	2	1	1	1	1	1	1
Y_k	0.02	0.8	0.85	0.71	1.30	1.31	0.28	0.79	1.66	2.86	2.93	2.34	1.33	2.77
Z_k	-1.21	0.62	0.73	1.22	0.26	0.21	0.60	0.97	1.25	1.93	0.34	0.01	0.21	1.21

目标	位置/10^-1km	价值	威胁概率
T₁	(67,23)	20	0.1
T₂	(65,70)	30	0.2
T₃	(25,55)	25	0.3
T₄	(8,32)	40	0.2
T₅	(35,30)	50	0.1
T₆	(40,44)	30	0.2
T₇	(42,90)	25	0.15
T₈	(19,40)	40	0.2
T₉	(60,35)	25	0.3
T₁₀	(66,55)	30	0.2
T₁₁	(80,98)	50	0.12
T₁₂	(94,89)	50	0.25
T₁₃	(32,65)	40	0.2
T₁₄	(87,30)	30	0.1
T₁₅	(87,30)	30	0.

目标	位置/10^-1km	价值	威胁概率
T₁	(67,23)	20	0.1
T₂	(65,70)	30	0.2
T₃	(25,55)	25	0.3
T₄	(8,32)	40	0.2
T₅	(35,30)	50	0.1
T₆	(40,44)	30	0.2
T₇	(42,90)	25	0.15
T₈	(19,40)	40	0.2
T₉	(60,35)	25	0.3
T₁₀	(66,55)	30	0.2
T₁₁	(80,98)	50	0.12
T₁₂	(94,89)	50	0.25
T₁₃	(32,65)	40	0.2
T₁₄	(87,30)	30	0.1
T₁₅	(87,30)	30	0.

编号	位置/10^-1km	价值	杀伤概率	任务上限
U₁	(45,3)	130	0.9	5
U₂	(34,5)	100	0.8	5
U₃	(23,3)	80	0.7	5