Heuristic Target Assignment Method for Swarm Operations

doi:10.3969/j.issn.1009-086x.2024.06.007

Abstract

Abstract:

With the development of low-cost and intelligent technologies， swarm operations are becoming a hot research topic. As the size of the swarm increases， efficient target assignment algorithms become an important research direction. In order to improve the computational efficiency of target assignment， this paper takes the surplus value of target clusters as the optimization goal， uses the greedy algorithm to select local optimal solutions step by step， and ultimately obtains an approximate global optimal solution for target assignment. Simulation of typical target assignment problems verifies the effectiveness of the proposed algorithm.

Key words: swarm, unmanned systems, target assignment, heuristic, greedy algorithm

摘要：

由于低成本和智能化技术的发展，蜂群作战正在成为现在的研究热点。随着蜂群规模的增加，高效的目标分配算法成为其中的一个重要研究方向。为了提高目标分配的计算效率，利用目标集群的剩余价值作为优化目标，使用贪婪算法分步选取局部最优解，最终获取目标分配的近似全局最优解。通过对典型目标分配问题的仿真，验证了提出算法的有效性。

关键词: 蜂群, 无人系统, 目标分配, 启发式, 贪婪算法

CLC Number:

TP181

Xiqing WEI, Sha DU. Heuristic Target Assignment Method for Swarm Operations[J]. Modern Defense Technology, 2024, 52(6): 47-51.

魏喜庆, 杜厦. 蜂群作战的启发式目标分配方法[J]. 现代防御技术, 2024, 52(6): 47-51.

Figures/Tables 4

Table 1 Target and weapon information

武器类型（数量）	V₁=70	V₂=60	V₃=25
1（ $w 1 = 2$ ）	0.8	0.9	0.5
2（ $w 2 = 1$ ）	0.6	0.2	0.4
3（ $w 3 = 2$ ）	0.4	0.4	0.8

Table 1 Target and weapon information

武器类型（数量）	V₁=70	V₂=60	V₃=25
1（ $w 1 = 2$ ）	0.8	0.9	0.5
2（ $w 2 = 1$ ）	0.6	0.2	0.4
3（ $w 3 = 2$ ）	0.4	0.4	0.8

Table 2 Missile gains of the first 3 iterations

武器类型i（数量）		目标j
武器类型i（数量）		1	2	3
$∆ V a l$ （第1轮）	1	56	54	12.5
	2	42	12	10
	3	28	24	20
$∆ V a l$ （第2轮）	1	11.2	54	12.5
	2	8.4	12	10
	3	5.6	24	20
$∆ V a l$ （第3轮）	1	0	0	0
	2	8.4	1.2	10
	3	5.6	2.4	20

Table 2 Missile gains of the first 3 iterations

武器类型i（数量）		目标j
武器类型i（数量）		1	2	3
$∆ V a l$ （第1轮）	1	56	54	12.5
	2	42	12	10
	3	28	24	20
$∆ V a l$ （第2轮）	1	11.2	54	12.5
	2	8.4	12	10
	3	5.6	24	20
$∆ V a l$ （第3轮）	1	0	0	0
	2	8.4	1.2	10
	3	5.6	2.4	20

Table 3 Results of target assignment

目标	1	2	3
武器	1， 3	2	4， 5

Table 4 Precision and time of swarm target assignment

武器	目标	精度/%		时间/s
武器	目标	VLSN	HRST	VLSN	HRST
80	80	0.15	0.17	0.16	0.12
200	200	0.36	0.45	0.83	0.45

References 19

1	SHOUMAN M， BANDO M， HOKAMOTO S. Output Regulation Control for Satellite Formation Flying Using Differential Drag［J］. Journal of Guidance， Control， and Dynamics， 2019， 42（10）： 2220-2232.
2	WANG Ximan， BALDI S， FENG Xuewei， et al. A Fixed-Wing UAV Formation Algorithm Based on Vector Field Guidance［J］. IEEE Transactions on Automation Science and Engineering， 2023， 20（1）： 179-192.
3	ZHANG Yao， WANG Xiao， TANG Shengjing. A Globally Fixed-Time Solution of Distributed Formation Control for Multiple Hypersonic Gliding Vehicles［J］. Aerospace Science and Technology， 2020， 98： 105643.
4	HADI B， KHOSRAVI A， SARHADI P. A Review of the Path Planning and Formation Control for Multiple Autonomous Underwater Vehicles［J］. Journal of Intelligent & Robotic Systems， 2021， 101（4）： 67.
5	ISSA B A， RASHID A T. A Survey of Multi-Mobile Robot Formation Control［J］. International Journal of Computer Applications， 2019， 181（48）： 12-16.
6	XU Ximeng， XU Jihui， TIAN Wenjie， et al. Review on Research and Development of Unmanned Aerial Vehicle Swarm Cooperative Operation［C］∥Proceedings of the 2022 5th International Conference on Robot Systems and Applications. New York： Association for Computing Machinery， 2022： 54-58.
7	李梦杰，常雪凝，石建迈，等. 武器目标分配问题研究进展：模型、算法与应用［J］. 系统工程与电子技术， 2023， 45（4）： 1049-1071.
	LI Mengjie， CHANG Xuening， SHI Jianmai， et al. Developments of Weapon Target Assignment： Models， Algorithms， and Applications［J］. Systems Engineering and Electronics， 2023， 45（4）： 1049-1071.
8	MANNE A S. A Target-Assignment Problem［J］. Operations Research， 1958， 6（3）： 346-351.
9	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（3）： 377-397.
10	ANDERSEN A C， PAVLIKOV K， TOFFOLO T A M. Weapon-Target Assignment Problem： Exact and Approximate Solution Algorithms［J］. Annals of Operations Research， 2022， 312（2）： 581-606.
11	AHUJA R K， ORLIN J B， SHARMA D. A Composite Very Large-Scale Neighborhood Structure for the Capacitated Minimum Spanning Tree Problem［J］. Operations Research Letters， 2003， 31（3）： 185-194.
12	AHUJA R K， KUMAR A， JHA K C， et al. Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem［J］. Operations Research， 2007， 55（6）： 1136-1146.
13	WACHOLDER E. A Neural Network-Based Optimization Algorithm for the Static Weapon-Target Assignment Problem［J］. ORSA Journal on Computing， 1989， 1（4）： 232-246.
14	丁振林，刘冠龙，谢艺，等. 基于强化学习与神经网络的动态目标分配算法［J］. 电子设计工程， 2020， 28（13）： 54-60.
	DING Zhenlin， LIU Guanlong， XIE Yi， et al. Dynamic Targets Assignment with Reinforcement Learning and Neural Network［J］. Electronic Design Engineering， 2020， 28（13）： 54-60.
15	SAHIN M A， LEBLEBICIOGLU K. A Genetic Algorithm for Weapon Target Assignment Problem［C］∥Proceedings of the Proceedings of the 2009 Summer Computer Simulation Conference. Vista： Society for Modeling & Simulation International， 2009： 61-65.
16	LEE Z J， LEE C Y， SU Shunfeng. An Immunity-Based Ant Colony Optimization Algorithm for Solving Weapon-Target Assignment Problem［J］. Applied Soft Computing， 2002， 2（1）： 39-47.
17	ZENG Xiangping， ZHU Yunlong， Lin NAN， et al. Solving Weapon-Target Assignment Problem Using Discrete Particle Swarm Optimization［C］∥Proceedings of the 2006 6th World Congress on Intelligent Control and Automation. Piscataway： IEEE， 2006： 3562-3565.
18	邹子缘，陈琪锋. 基于决策树搜索的空间飞行器集群对抗目标分配方法［J］. 航空学报， 2022， 43（增1）： 78-88.
	ZOU Ziyuan， CHEN Qifeng. Decision Tree-Based Target Assignment for Confrontation of Multiple Space Vehicles［J］. Acta Aeronautica et Astronautica Sinica， 2022， 43（S1）： 78-88.
19	KLINE A， AHNER D， HILL R. The Weapon-Target Assignment Problem［J］. Computers & Operations Research， 2019， 105： 226-236.

[1]	Wenbiao HE, Yongjiang HU, Wenguang LI. Review of Optimization Algorithms for UAV Routes [J]. Modern Defense Technology, 2024, 52(4): 24-32.
[2]	Yang TAO, Yi ZHOU, Huangtao JIANG. Application of Improved Ant Colony Algorithm to Terrain Following Route Planning Problem [J]. Modern Defense Technology, 2024, 52(1): 34-40.
[3]	Yuhao LIU, Bing ZHANG, Zijin FANG. Approach Orbit Design Method for Space Multi-target Glide Observation [J]. Modern Defense Technology, 2024, 52(1): 57-64.
[4]	Zhenggong LIAO, yuan REN, Jingzhang BI. A Frequency-Phase Hybrid Coded Waveform Design for MIMO Radar [J]. Modern Defense Technology, 2023, 51(6): 112-122.
[5]	Shiqiao DU, Guilan LI, Jun KOU, He HAO, Tong WU, Guoqing QIN, Hongwei GAO. Fast Search of Quantum Measurement System Parameters via Particle Swarm Optimization [J]. Modern Defense Technology, 2023, 51(6): 155-161.
[6]	Changhong QU, Yu SONG, Kun WANG, Qingyong CUI, Jiangyang CHEN. Deployment Method of Ground-Based Tactical Laser System for UAV Swarm Defense Based on PSO Algorithm [J]. Modern Defense Technology, 2023, 51(5): 15-24.
[7]	Guodong YUAN, Ming HE, Wei HAN, Minggang YU, Mingyang CHENG. Research on Resilience Reconstruction of Community Network of Unmanned Aerial Vehicle Swarm [J]. Modern Defense Technology, 2023, 51(5): 50-58.
[8]	Ruijie WANG, Dechao WANG, Lu FENG, Zhengdang ZHAO, Zheliang CHEN. Research Progress and Countermeasures Against UAV Swarm Operations Abroad [J]. Modern Defense Technology, 2023, 51(4): 1-9.
[9]	Zonglei BAI, Xiuhua LIU, Tianxiang BAI, Kewu SUN. Research on Multi-task Controllable Emergence Mechanism for Air and Space Defense System [J]. Modern Defense Technology, 2023, 51(3): 39-48.
[10]	Biyan LI, Shun HU. Formation Control of UAV Swarm with Bearing-Only Measurements [J]. Modern Defense Technology, 2023, 51(2): 55-61.
[11]	An XU, Wan-ze ZHENG, Zhi-fei XI, Lu-fei DANG. Improved Evolutionary Decision Tree for BVR Air Combat Decision Making [J]. Modern Defense Technology, 2022, 50(6): 68-82.
[12]	Fang-yu ZHOU, Jie ZHOU, Chao-bo CHEN, Song GAO. Cooperative Detection and Tracking of UAV Swarms Based on Clonal Immune Decision-Making [J]. Modern Defense Technology, 2022, 50(5): 93-105.
[13]	Jun-yi CHEN, Jian YANG. Research on Rules for Reconnaissance Area Planning of Communications Countermeasure Drone Swarms [J]. Modern Defense Technology, 2022, 50(1): 54-59.
[14]	BIAN Wei-wei, LÜ Xin, LIU Chan, JIA Yan-xiang, QIU Xu-yang. Simulation Analysis of Mission Planning for Low Slow Small Target Compound Interception [J]. Modern Defense Technology, 2021, 49(5): 104-110.
[15]	SONG Wei-xing, WU Jing-jing, DONG Zhi-peng, ZHANG Jun, ZHOU Kai. Equipment Maintenance Scheduling Optimization Model Based on Cost Analysis [J]. Modern Defense Technology, 2021, 49(5): 88-94.