Distributed Target Assignment Method for UAV Swarms Using Identity Hungarian Algorithm

doi:10.12382/bgxb.2022.0994

Abstract

Abstract:

Distributed strike capabilities against multiple enemy targets are crucial for Unmanned Aerial Vehicle (UAV) swarms in combat scenarios. One key challenge is how individual UAVs choose their targets for effective strikes. Most existing target allocation algorithms are designed for centralized target allocation problems with global information, making them unsuitable for battlefield environments with local perception and interaction. To address this, we propose the Identity Hungarian Algorithm, which incorporates drone and target identities into the traditional Hungarian algorithm. This approach considers factors such as proximity, target value, target distance, target azimuth, and UAV speed to achieve distributed target allocation for UAV swarms. Case study results demonstrate that the proposed identity Hungarian Algorithm mitigates target omission and redundancy attacks, enhances the overall combat effectiveness of the UAV swarm, and lays the foundation for effective combat strategies in sequence.

Key words: UAV swarm, distributed target assignment, Hungarian algorithm, attack superiority

CLC Number:

E911

LIU Xingyu, GUO Ronghua, REN Chengcai, YAN Chao, CHANG Yuan, ZHOU Han, XIANG Xiaojia. Distributed Target Assignment Method for UAV Swarms Using Identity Hungarian Algorithm[J]. Acta Armamentarii, 2023, 44(9): 2824-2835.

Figures/Tables 22

Fig.1 Concept of drone swarm combat

Fig.2 Schematic diagram of swarm drone strike situation

Fig.3 Distance advantage function

Fig.4 Speed advantage function

Table 1 Steps of Hungarian algorithm

序号	内容
1	使效率矩阵变换,在各行各列中均出现0元素
2	进行试指派,寻求最优解
3	作最少直线覆盖所有0元素,确定效率矩阵中能找到的最多独立元素
4	使效率矩阵变换,增加0元素
5	获得N个独立0元素,即最优解

Fig.5 Unified efficiency matrix

Fig.6 Unified efficiency matrix based on local information

Fig.7 Unified efficiency matrix in identity Hungarian algorithm

Fig.8 Process flow of multi-target assignment method for UAV swarm using identity-based Hungarian algorithm

Fig.9 Comparison of runtimes of HA, PSO, and GA[23]

Fig.10 Comparison of optimal values of HA, PSO, and GA[23]

Table 2 UAV and enemy target information

参数	对象
参数	Γ₁	Γ₂	Γ₃	T₁	T₂	T₃
横坐标/km	0.098	1.547	0.971	6.916	7.960	4.036
纵坐标/km	1.279	2.958	1.957	4.792	3.656	5.850
角度/rad	0.132	0.465	1.245
速度/(km·h^-1)	46.210	49.574	42.147
种类				1	2	3

Fig.11 UAV unified efficiency matrix with globally known information

Table 3 UAV and enemy target information

参数	对象
参数	Γ₁	Γ₂	Γ₃	T₁	T₂	T₃
横坐标/km	0	5.606	3.117	-0.722	-3.907	4.134
纵坐标/km	4.838	4.716	9.816	-3.027	2.699	6.363
角度/rad	2.999	0.682	0.484
速度/(km·h^-1)	30.019	42.497	33.860
种类				1	3	2

Fig.12 Schematic diagram of UAV and Enemy Target Information

Fig.13 Unified efficiency matrix of UAV 1 by Hungary algorithm

Fig.14 Unified efficiency matrix of UAV 2 by Hungary algorithm

Fig.15 Unified efficiency matrix of UAV 3 by Hungary algorithm

Fig.16 Unified efficiency matrix of UAV 1 by identity-based Hungary algorithm

Fig.17 Unified efficiency matrix of UAV 2 by identity-based Hungary algorithm

Fig.18 Unified efficiency matrix of UAV 3 by identity-based Hungary algorithm

Fig.19 Results of target assignment

References 26

[1]	王祥科, 刘志宏, 丛一睿. 小型固定翼无人机集群综述和未来发展[J]. 航空学报, 2020, 41(4):023732.
	WANG X K, LIU Z H, CONG Y R. Miniature fixed-wing UAV swarms: review and outlook[J]. Acta Aeronautical et Astronautical Sinical, 2020, 41(4):023732. (in Chinese)
[2]	孙永芹, 马响玲, 叶文, 等. 超视距多机协同多目标攻击系统研究[J]. 系统仿真学报, 2008, 20(8):2161-2164.
	SUN Y Q, MA X L, YE W, et al. Research onbeyond visual range multi-fighter cooperation and multi-target attack system[J]. Journal of System Simulation, 2008, 20(8):2161-2164. (in Chinese)
[3]	兰俊龙, 赵思宏, 寇英信, 等. 多机协同多目标攻击空战战术决策[J]. 电光与控制, 2010, 17(12) :17-19.
	LAN J L, ZHAO S H, KOU Y X, et al. Tacticaldecision-making in multi-aircraft cooperative combat for multi-target attacking[J]. Electronics Optics & Control, 2010, 17(12) :17-19. (in Chinese)
[4]	肖冰松, 方洋旺, 夏海宝, 等. 多机协同对空目标探测与攻击任务的最优分配[J]. 火力与指挥控制, 2011, 36(6):19-23.
	XIAO B S, FANG Y W, XIA H B, et al. Optimalallocation of aerial target detection and attack in cooperative multi-fighter air combat[J]. Fire Control & Command Control, 2011, 36(6):19-23. (in Chinese)
[5]	胡月, 丁萌, 姜欣言, 等. 一种面向有人/无人直升机协同打击的地面目标任务分配方法[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)
[6]	韩统, 崔明朗, 张伟, 等. 多无人机协同空战机动决策[J]. 兵工装备工程学报, 2020, 41(4):117-123.
	HAN T, CUI M L, ZHANG W, et al. Multi-UCAVcooperative air combat maneuvering decisio[J]. Journal of Ordnance Equipment Engineering, 2020, 41(4):117-123. (in Chinese)
[7]	KONG L L, WANG J Z, ZHAO P. Solving thedynamic weapon target assignment problem by an improved multi-objective particle swarm optimization algorithm[J]. Applied Sciences, 2021, 11:9254. doi: 10.3390/app11199254 URL
[8]	KIM J E, LEE C H, YI M Y. Newweapon target assignment algorithms for multiple targets using a rotational strategy and clustering approach[J]. IEEE Access, 2022, 10:43738-43750. doi: 10.1109/ACCESS.2022.3168718 URL
[9]	李战武, 常一哲, 孙源源, 等. 中远距协同空战多目标攻击决策[J]. 火力与指挥控制, 2016, 41(2):36-40.
	LI Z W, CHANG Y Z, SUN Y Y, et al. Adecision-making for multiple target attack based on characteristic of future long-range cooperative air combat[J]. Fire Control & Command Control, 2016, 41(2):36-40. (in Chinese)
[10]	岳源, 屈高敏. 分布式多无人机协同侦察目标分配研究[J]. 兵工装备工程学报, 2018, 39(3):57-61,82.
	YUE Y, QU G M. Research ondistributed multi-UAV cooperative reconnaissance task allocation[J]. Journal of Ordnance Equipment Engineering, 2018, 39(3):57-61,82. (in Chinese)
[11]	KLINE A G, AHNER D K, LUNDAY B J. Real-time heuristic algorithms for the static weapon target assignment problem[J]. Journal of Heuristics, 2019, 25:377-397. doi: 10.1007/s10732-018-9401-1
[12]	吴文海, 郭晓峰, 周思羽, 等. 改进差分进化算法求解武器目标分配问题[J]. 系统工程与电子技术, 2021, 43(4):1012-1021.
	WU W H, GUO X F, ZHOU S Y, et al. Improved differential evolution algorithm for solving weapon-target assignment problem[J]. Systems Engineering and Electronics, 2021, 43(4):1012-1021. (in Chinese)
[13]	黄刚, 李军华. 基于AC-DSDE进化算法多UAVs协同目标分配[J]. 自动化学报, 2021, 47(1):173-184.
	HUANG G, LI J H. Multi-UAV cooperative target allocation based on AC-DSDE evolutionary algorithm[J]. Acta Automatica Sinica, 2021, 47(1):173-184. (in Chinese)
[14]	朱建文, 赵长见, 李小平, 等. 基于强化学习的集群多目标分配与智能决策方法[J]. 兵工学报, 2021, 42(9):2040-2048.
	ZHU J W, ZHAO C J, LI X P, et al. Multi-target assignment and intelligent decision based on reinforcement learning[J]. Acta Armamentarii, 2021, 42(9):2040-2048. (in Chinese) doi: 10.3969/j.issn.1000-1093.2021.09.025
[15]	NAN M Y, ZHU Y F, KANG L, et al. A Modified RL-IGWO algorithm for dynamic weapon-target assignment in frigate defensing UAV swarms[J]. Electronics, 2022, 11:1796. doi: 10.3390/electronics11111796 URL
[16]	BERTSEKAS D P. New algorithms for assignment and transportation problems[D]. Cambridge,MA, US: MIT, 1979.
[17]	KUHN H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics Quarterly, 1955, 2(1):83-97. doi: 10.1002/nav.v2:1/2 URL
[18]	BOURGEOIS F, LASSALLE J. An extension of the Munkres algorithm for the assignment problem to rectangular matrices[J]. Communications of the ACM, 1971, 14(12):802-804. doi: 10.1145/362919.362945 URL
[19]	ZHU H B, LIU D N, ZHANG S Q, et al. Solving the many to many assignment problem by improving the Kuhn-Munkres algorithm with backtracking[J]. Theoretical Computer Science, 2016, 618:30-41. doi: 10.1016/j.tcs.2016.01.002 URL
[20]	CHOPRA S, NOTARSTEFANO G, RICE M, et al. A distributed version of the Hungarian method for multirobot assignment[J]. IEEE Transactions on Robotics, 2017, 33(4):932-947. doi: 10.1109/TRO.2017.2693377 URL
[21]	柳毅, 佟明安. HA在多目标分配中的应用[J]. 火力与指挥控制, 2002, 27(4):34-37.
	LIU Y, TONG M A. Anapplication of Hungarian algorithm to the multi-target assignment[J]. Fire Control & Command Control, 2002, 27(4):34-37. (in Chinese)
[22]	DU C P, DAI Z X, ZHENG Y, et al. A target allocation method inspired by Hungarian algorithm[C] //Proceedings of 2018 IEEE International Conference on Information and Automation. Wuyi Mountain, Fujian, China: IEEE, 2018.
[23]	张进, 郭浩, 陈统. 基于可适应HA的武器-目标分配问题[J]. 兵工学报, 2021, 42(6):1339-1344. doi: 10.3969/j.issn.1000-1093.2021.06.025
	ZHANG J, GUO H, CHEN T. Weapon-targetassignment based on adaptable Hungarian algorithm[J]. Acta Armamentarii, 2021, 42(6):1339-1344. (in Chinese) doi: 10.3969/j.issn.1000-1093.2021.06.025
[24]	JIANG Y, WANG D B, BAI T T, et al. Multi-UAV objective assignment using Hungarian fusion genetic algorithm[J]. IEEE Access, 2022, 10:43013-43021. doi: 10.1109/ACCESS.2022.3168359 URL
[25]	林晨. 面向无人机集群任务分配的分布式算法研究[D]. 成都: 电子科技大学, 2019.
	LIN C. Distributed algorithm research for multi-UAV task assignment problem[D]. Chengdu: University of Electronic Science and Technology of China, 2019. (in Chinese)
[26]	陈洁钰, 姚佩阳, 唐剑, 等. 多无人机分布式协同动态目标分配方法[J]. 空军工程大学学报:自然科学版, 2014, 15(6):11-16.
	CHEN J Y, YAO P Y, TANG J, et al. Multi-UAV decentralized cooperative dynamic target assignment method[J]. Journal of Air Force Engineering University: Natural Science Edition, 2014, 15(6):11-16. (in Chinese)