基于身份匈牙利算法的无人机蜂群分布式目标分配方法

doi:10.12382/bgxb.2022.0994

摘要/Abstract

摘要：

对敌方多目标实施分布式打击是无人机蜂群的重要作战样式,无人机个体如何选择打击目标是其中的关键问题之一。现有目标分配算法大多针对信息全局可知的集中式目标分配问题,无法适应局部感知交互的战场环境。基于就近原则以及目标价值原则,参考目标距离、目标方位角、目标价值、无人机速度等要素,在匈牙利算法(HA)的基础上考虑了无人机身份和目标身份信息,提出了身份HA,实现了无人机蜂群的分布式目标分配。算例分析结果表明,身份HA可以避免无人机蜂群遗漏目标或冗余攻击,提升无人机蜂群的整体作战效能,为实现鱼贯依次打击的作战策略奠定算法基础。

关键词: 无人机蜂群, 分布式目标分配, 匈牙利算法, 打击优势

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

中图分类号:

E911

刘兴宇, 郭荣化, 任成才, 闫超, 常远, 周晗, 相晓嘉. 基于身份匈牙利算法的无人机蜂群分布式目标分配方法[J]. 兵工学报, 2023, 44(9): 2824-2835.

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.

图/表 22

图1 无人机蜂群作战概念图

Fig.1 Concept of drone swarm combat

图2 蜂群无人机打击态势示意图

Fig.2 Schematic diagram of swarm drone strike situation

图3 距离优势函数

Fig.3 Distance advantage function

图4 速度优势函数

Fig.4 Speed advantage function

表1 HA步骤

Table 1 Steps of Hungarian algorithm

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

图5 统一效率矩阵

Fig.5 Unified efficiency matrix

图6 掌握局部信息无人机的统一效率矩阵

Fig.6 Unified efficiency matrix based on local information

图7 身份HA中无人机的统一效率矩阵

Fig.7 Unified efficiency matrix in identity Hungarian algorithm

图8 基于身份HA的无人机蜂群多目标分配方法流程

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

图9 HA、PSO算法、GA运行时间对比[23]

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

图10 HA、PSO算法、GA最优值对比[23]

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

表2 无人机及敌方目标信息

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

图11 信息全局可知情况下的无人机统一效率矩阵

Fig.11 UAV unified efficiency matrix with globally known information

表3 无人机及敌方目标信息

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

图12 无人机及敌方目标示意图

Fig.12 Schematic diagram of UAV and Enemy Target Information

图13 依据HA无人机1号的统一效率矩阵

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

图14 依据HA无人机2号的统一效率矩阵

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

图15 依据HA无人机3号的统一效率矩阵

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

图16 依据身份HA无人机1号的统一效率矩阵

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

图17 依据身份HA无人机2号的统一效率矩阵

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

图18 依据身份HA无人机3号的统一效率矩阵

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

图19 无人机蜂群目标分配结果

Fig.19 Results of target assignment

参考文献 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)