A game theoretic model and a double oracle algorithm for the heterogeneous weapon target assignment problem

doi:10.23919/JSEE.2026.000065

Journal of Systems Engineering and Electronics ›› 2026, Vol. 37 ›› Issue (2): 548-566.doi: 10.23919/JSEE.2026.000065

• SYSTEMS ENGINEERING • Previous Articles

A game theoretic model and a double oracle algorithm for the heterogeneous weapon target assignment problem

Yingying MA¹^,²(), He LUO¹^,³^,*(), Guoqiang WANG¹^,⁴(), Waiming ZHU¹^,⁴(), Xiaoxuan HU¹^,²()

¹School of Management, Hefei University of Technology, Hefei 230009, China
²Key Laboratory of Process Optimization & Intelligent Decision-Making, Ministry of Education, Hefei 230009, China
³Engineering Research Center for Intelligent Decision-Making & Information System Technologies, Ministry of Education, Hefei 230009, China
⁴Engineering Research Center for Intelligent Management of Aerospace System, Hefei 230009, China

Received:2023-12-05 Accepted:2026-03-19 Online:2026-04-18 Published:2026-04-30
Contact: He LUO E-mail:mayy@hfuu.edu.cn;luohe@hfut.edu.cn;gqwang2017@hfut.edu.cn;zhuwaiming@hfut.edu.cn;xiaoxuanhu@hfut.edu.cn
About author:
MA Yingying was born in 1994. She received her Ph.D. degree from Hefei University of Technology in 2022. She is a lecturer in Hefei University of Technology. Her research interests are multi-UAV collaborative intelligent decision making and weapon target assignment. E-mail: mayy@hfuu.edu.cn

LUO He was born in 1982. He received his B.S. and Ph.D. degrees from Hefei University of Technology, in 2004 and 2009, respectively, where he is currently a professor. His research interests include intelligent decision making, multi-agent system, and the applications of un-manned aerial vehicle. E-mail: luohe@hfut.edu.cn

WANG Guoqiang was born in 1982. He received his B.S. and M.S. degrees from University of Science and Technology, in 2004 and 2007, respectively, and Ph.D. degree from Hefei University of Technology, in 2016, where he is currently an associate professor. His research interest includes management and intelligent decision making of unmanned aerial vehicle formation. E-mail: gqwang2017@hfut.edu.cn

ZHU Waiming was born in 1988. He received his M.S. and Ph.D. degrees from Hefei University of Technology, in 2015 and 2019, respectively. He is a lecturer in Hefei University of Technology. His current research interests include logistical unmanned aerial vehicle scheduling and satellite mission planning. E-mail: zhuwaiming@hfut.edu.cn

HU Xiaoxuan was born in 1978. He received his B.S. and Ph.D. degrees from Hefei University of Technology, in 1999 and 2006, respectively. He is a professor in Hefei University of Technology. His current research interests include satellite mission planning, unmanned system intelligence, and aerospace system management. E-mail: xiaoxuanhu@hfut.edu.cn
Supported by:
This paper was supported by the National Natural Science Foundation of China (72571094; 71871079; 72271076; 72001004), Anhui Provincial Natural Science Foundation (2308085QG233), Anhui Province Postdoctoral Research Activities Funds (2022B587), and Talent Research Fund of Hefei University (24RC75).

Abstract

Abstract:

Weapon target assignment (WTA) problem is a critical problem in multiplatform confrontation. This paper studies a static WTA problem with heterogeneous weapons in multi-platform air combat scenarios, called heterogeneous WTA (HWTA) problem. Heterogeneous indicates that the engagement platforms carry multiple kinds of weapons for different tactical purposes. The targets assigned and the weapons used by one side’s platforms will affect the survival probability and capability of the other side’s platforms. The goal of each side in HWTA is to find a solution to determine the kind of weapon used and the target assigned for each platform, so as to maximize their combat effectiveness. The problem is formulated as a two-player noncooperative game model with considering the conflicts between the engaged sides. The Nash equilibrium is an effective solution to the game in which no player has an incentive to deviate. However, the number of pure strategies in HWTA increases exponentially with the engagement platforms. To improve computing efficiency, a double oracle algorithm with constructive heuristic (DOCH) is developed, within which the constructive heuristic is embedded to solve the oracle subproblems efficiently. Numerical experiments are conducted to verify the effectiveness of the DOCH. The results show that the DOCH can find effective strategies for platforms to improve combat effectiveness. Moreover, the DOCH can find high-quality solutions in seconds, significantly outperforming the state-of-the-art algorithms in terms of computational efficiency, especially for large-scale problems.

Key words: weapon target assignment, noncooperative game, double oracle algorithm, constructive heuristic

Yingying MA, He LUO, Guoqiang WANG, Waiming ZHU, Xiaoxuan HU. A game theoretic model and a double oracle algorithm for the heterogeneous weapon target assignment problem[J]. Journal of Systems Engineering and Electronics, 2026, 37(2): 548-566.

Figures/Tables 12

Fig 1

Table 1

Table 2

Table 3

Fig 2

Fig 3

Table 4

Table 5

Table 6

Table 7

Fig 4

Fig 5

References 46

1	BAI Z Z, ZHOU H Y, SHI J M, et al A hybrid multi-objective evolutionary algorithm with high solving efficiency for UAV defense programming. Swarm and Evolutionary Computation, 2024, 87, 101572. doi: 10.1016/j.swevo.2024.101572
2	ACAR E, HATIPOGLU S, YILMAZ I A quantum algorithm for solving weapon target assignment problem. Engineering Applications of Artificial Intelligence, 2023, 125, 106668. doi: 10.1016/j.engappai.2023.106668
3	ARSLAN C, KARASAKAL O, KIRCA O Naval air defense planning problem: a novel formulation and heuristics. Naval Research Logistics, 2024, 71 (7): 895- 919. doi: 10.1002/nav.22186
4	LILES J M, ROBBINS M J, LUNDAY B J Improving defensive air battle management by solving a stochastic dynamic assignment problem via approximate dynamic programming. European Journal of Operational Research, 2023, 305 (3): 1435- 1449. doi: 10.1016/j.ejor.2022.06.031
5	JIANG R H, LUO H, MA Y Y, et al Multicriteria game approach to air-to-air combat tactical decisions for multiple UAVs. Journal of Systems Engineering and Electronics, 2023, 34 (6): 1447- 1464. doi: 10.23919/JSEE.2023.000115
6	WANG T, FU L Y, WEI Z X, et al Unmanned ground weapon target assignment based on deep Q-learning network with an improved multi-objective artificial bee colony algorithm. Engineering Applications of Artificial Intelligence, 2023, 117, 105612. doi: 10.1016/j.engappai.2022.105612
7	ANDERSEN A C, PAVLIKOV K, TOFFOLO T A Weapon-target assignment problem: exact and approximate solution algorithms. Annals of Operations Research, 2022, 312 (2): 581- 606. doi: 10.1007/s10479-022-04525-6
8	ZHAO L D, AN Z X, WANG B, et al A hybrid multi-objective bi-level interactive fuzzy programming method for solving ECM-DWTA problem. Complex & Intelligent Systems, 2022, 8 (6): 4811- 4829. doi: 10.1007/s40747-022-00730-9
9	KLINE A, AHNER D, HILL R The weapon-target assignment problem. Computers & Operations Research, 2019, 105, 226- 236. doi: 10.1016/j.cor.2018.10.015
10	ZHANG L L, GANG D U, JUN W U, et al Joint production planning, pricing and retailer selection with emission control based on Stackelberg game and nested genetic algorithm. Expert Systems with Applications, 2020, 161, 113733. doi: 10.1016/j.eswa.2020.113733
11	KOSE E, ERBAS M, ERSEN E An integrated approach based on game theory and geographical information systems to solve decision problems. Expert Systems with Applications, 2017, 308 (C): 105- 114. doi: 10.1016/j.amc.2017.03.020
12	WU Y F, KANG B Y, WU H Strategies of attack–defense game for wireless sensor networks considering the effect of confidence level in fuzzy environment. Engineering Applications of Artificial Intelligence, 2021, 102, 104238. doi: 10.1016/j.engappai.2021.104238
13	CHANG X N, SHI J M, LUO Z H, et al Adaptive large neighborhood search algorithm for multi-stage weapon target assignment problem. Computers & Industrial Engineering, 2023, 181, 109303. doi: 10.1016/j.cie.2023.109303
14	SUMMERS D S. , ROBBINS M J. , LUNDAY B J. An approximate dynamic programming approach for comparing firing policies in a networked air defense environment. Computers & Operations Research, 2020, 117: 104890.
15	MA Y Y, WANG G Q, HU X X, et al Two-stage hybrid heuristic search algorithm for novel weapon target assignment problems. Computers & Industrial Engineering, 2021, 162, 107717. doi: 10.1016/j.cie.2021.107717
16	XU H, ZHANG A, BI W H, et al Dynamic gaussian mutation beetle swarm optimization method for large-scale weapon target assignment problems. Applied Soft Computing, 2024, 162, 111798. doi: 10.1016/j.asoc.2024.111798
17	LAI C M, WU T H Simplified swarm optimization with initialization scheme for dynamic weapon-target assignment problem. Applied Soft Computing, 2019, 82, 105542. doi: 10.1016/j.asoc.2019.105542
18	ZHANG K, ZHOU D Y, YANG Z, et al Efficient decision approaches for asset-based dynamic weapon target assignment by a receding horizon and marginal return heuristic. Electronics, 2020, 9 (9): 1511. doi: 10.3390/electronics9091511
19	LI G J, HE G J, ZHENG M F, et al Uncertain multi-objective dynamic weapon-target allocation problem based on uncertainty theory. AIMS Mathematics, 2023, 8 (3): 5639- 5669. doi: 10.3934/math.2023284
20	KONG L R, WANG J Z, ZHAO P Solving the dynamic weapon target assignment problem by an improved multiobjective particle swarm optimization algorithm. Applied Sciences, 2021, 11 (19): 9254. doi: 10.3390/app11199254
21	SILAV A, KARASAKAL E, KARASAKAL O Bi-objective dynamic weapon-target assignment problem with stability measure. Annals of Operations Research, 2021, 311 (2): 1229- 1247. doi: 10.1007/s10479-020-03919-8
22	YI X J, YU H Y, XU T Solving multi-objective weapon-target assignment considering reliability by improved MOEA/D-AM2M. Neurocomputing, 2024, 563, 126906. doi: 10.1016/j.neucom.2023.126906
23	GULPINAR N, CANAKOGLU E, BRANKE J Heuristics for the stochastic dynamic task-resource allocation problem with retry opportunities. European Journal of Operational Research, 2018, 266 (1): 291- 303. doi: 10.1016/j.ejor.2017.09.006
24	ZHANG J Z, KONG M, ZHANG G, et al Weapon-target assignment using a whale optimization algorithm. International Journal of Computational Intelligence Systems, 2023, 16 (1): 1- 18.
25	AHUJA R K, KUMAR A, JHA K C, et al Exact and heuristic algorithms for the weapon-target assignment problem. Operations Research, 2007, 55 (6): 1136- 1146. doi: 10.1287/opre.1070.0440
26	LU Y P, CHEN D Z A new exact algorithm for the weapon-target assignment problem. Omega, 2021, 98, 102138. doi: 10.1016/j.omega.2019.102138
27	ZHI P F, LIANG Z Z, ZHU W L, et al Weapon target assignment strategy for shipboard power system considering high power pulse loads integration. Energy Reports, 2023, 9, 32- 40. doi: 10.1016/j.egyr.2023.04.257
28	YADAV K, ALSHUDUKHI J S, DHIMAN G, et al ITSA: an improved tunicate swarm algorithm for defensive resource assignment problem. Soft Computing, 2022, 26 (10): 4929- 4937. doi: 10.1007/s00500-022-06979-z
29	NIU W T, SHE W, ZHONG L H, et al Elite-centered artificial bee colony algorithm with extended solution boundary. Applied Soft Computing, 2023, 148, 110906. doi: 10.1016/j.asoc.2023.110906
30	WANG Y P, XIN B, CHEN J An adaptive memetic algorithm for the joint allocation of heterogeneous stochastic resources. IEEE Trans. on Cybernetics, 2022, 52 (11): 11526- 11538. doi: 10.1109/TCYB.2021.3087363
31	ZHAO Y, LIU J C, JIANG J, et al Shuffled frog leaping algorithm with non-dominated sorting for dynamic weapon-target assignment. Journal of Systems Engineering and Electronics, 2023, 34 (4): 1007- 1019. doi: 10.23919/JSEE.2023.000102
32	XU W Q, CHEN C, DING S X, et al A bi-objective dynamic collaborative task assignment under uncertainty using modified MOEA/D with heuristic initialization. Expert Systems with Applications, 2020, 140, 112844. doi: 10.1016/j.eswa.2019.112844
33	LI J, XIN B, PARDALOS P M, et al Solving bi-objective uncertain stochastic resource allocation problems by the CVAR-based risk measure and decomposition-based multi-objective evolutionary algorithms. Annals of Operations Research, 2019, 296 (1−2): 639- 666.
34	XIN B, WANG Y P, CHEN J An efficient marginal-return-based constructive heuristic to solve the sensor-weapon-target assignment problem. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2019, 49 (12): 2536- 2547. doi: 10.1109/TSMC.2017.2784187
35	KLINE A G, AHNER D K, LUNDAY B J A heuristic and metaheuristic approach to the static weapon target assignment problem. Journal of Global Optimization, 2020, 78 (4): 791- 812.
36	HAYWOOD A B, LUNDAY B J, ROBBINS M J Intruder detection and interdiction modeling: a bilevel programming approach for ballistic missile defense asset location. Omega, 2022, 110, 102640. doi: 10.1016/j.omega.2022.102640
37	SUN B, ZENG Y R, SU Z N Task allocation in multi-AUV dynamic game based on interval ranking under uncertain information. Ocean Engineering, 2023, 288, 116057. doi: 10.1016/j.oceaneng.2023.116057
38	HAN C Y, LUNDAY B J, ROBBINS M J A game theoretic model for the optimal location of integrated air defense system missile batteries. Informs Journal on Computing, 2016, 28 (3): 405- 416. doi: 10.1287/ijoc.2016.0690
39	XU J W, DENG Z H, SONG Q, et al Multi-UAV counter-game model based on uncertain information. Applied Mathematics and Computation, 2020, 366, 124684. doi: 10.1016/j.amc.2019.124684
40	LI S Y, CHEN M, WANG Y H, et al Air combat decision-making of multiple UCAVs based on constraint strategy games. Defence Technology, 2022, 18 (3): 368- 383. doi: 10.1016/j.dt.2021.01.005
41	ROSENMULLER J On a generalization of the Lemke-Howson algorithm to noncooperative N-person games. SIAM Journal on Applied Mathematics, 1971, 1 (21): 73- 79. doi: 10.1137/0121010
42	MCMAHAN H B, GORDON G J, BLUM A. Planning in the presence of cost functions controlled by an adversary. Proc. of the 20th International Conference on Machine Learning, 2003: 536–543.
43	JIE Y M, LIU C Z C, LI M C, et al Game theoretic resource allocation model for designing effective traffic safety solution against drunk driving. Applied Mathematics and Computation, 2020, 376, 125142. doi: 10.1016/j.amc.2020.125142
44	WU D W, LISSER A Using CNN for solving two-player zero-sum games. Expert Systems with Applications, 2022, 204, 117545. doi: 10.1016/j.eswa.2022.117545
45	WU Y H, QURESHI A G, YAMADA T Adaptive large neighborhood decomposition search algorithm for multi-allocation hub location routing problem. European Journal of Operational Research, 2022, 302 (3): 1113- 1127. doi: 10.1016/j.ejor.2022.02.002
46	LEI X, HU X X, WANG G Q, et al A multi-UAV deployment method for border patrolling based on Stackelberg game. Journal of Systems Engineering and Electronics, 2023, 34 (1): 99- 116. doi: 10.23919/JSEE.2023.000022

Symbol	Description
m	The number of APs
n	The number of DPs
$ p_{ij}^{a} $	The kill probability of the AP $ i $ to the DP $ j $
$ q_{ij}^{a} $	The interference probability of the AP $ i $ to the DP $ j $
$ v_{i}^{a} $	The value of the AP $ i $
$ p_{ji}^{d} $	The kill probability of the DP $ j $ to the AP $ i $
$ q_{ji}^{d} $	The interference probability of the DP $ j $ to the AP $ i $
$ v_{j}^{d} $	The value of the DP $ j $

Parameter	Range
$ p_{ij}^{a} $	0.30−0.90
$ q_{ij}^{a} $	0.30−0.70
$ v_{i}^{a} $	25−100
$ p_{ji}^{d} $	0.30−0.90
$ q_{ji}^{d} $	0.30−0.70
$ v_{j}^{d} $	25−100

Instance	m	n	LH	DOEM	DONS	DOCH
1-1	3	3	115.55	1.20	0.03	0.04
1-2	4		1396.08	21.75	0.07	0.06
1-3	5		−	15.88	0.11	0.01
1-4	6		−	976.72	0.17	0.05
2-1	4	5	−	1383.94	0.62	0.05
2-2	5		−	5862.15	0.23	0.09
2-3	6		−	−	0.83	0.20
2-4	7		−	−	0.93	0.13
3-1	7	10	−	−	7.57	0.24
3-2	10		−	−	16.21	0.37
3-3	12		−	−	6.22	0.28
3-4	15		−	−	9.51	0.52
4-1	10	20	−	−	34.37	0.41
4-2	20		−	−	80.81	1.56
4-3	30		−	−	194.06	2.72
4-4	40		−	−	602.91	1.84
5-1	30	40	−	−	944.54	5.32
5-2	40		−	−	2310.36	3.43
5-3	50		−	−	4451.77	7.03
5-4	60		−	−	9583.35	7.16
6-1	50	60	−	−	−	10.24
6-2	60		−	−	−	12.10
6-3	70		−	−	−	13.43
6-4	80		−	−	−	16.93

Instance	m	n	RS	OS	DNSS	LHS	DEMS	DCHS
1-1	3	3	1285.24	71.44	16.65	0.00	0.00	16.65
1-2	4		35.87	6.60	3.01	0.00	0.64	3.01
1-3	5		26.38	32.33	9.65	−	0.00	5.61
1-4	6		31.77	21.12	5.08	−	0.00	2.62
2-1	4	5	84.45	12.33	12.33	−	0.00	2.94
2-2	5		143.08	46.97	0.26	−	0.00	18.68
2-3	6		57.91	21.75	0.00	−	−	5.61
2-4	7		79.26	20.22	0.00	−	−	15.80
3-1	7	10	68.04	0.00	0.41	−	−	0.00
3-2	10		537.43	99.75	22.25	−	−	0.00
3-3	12		127.63	22.32	4.60	−	−	0.00
3-4	15		48.36	15.48	0.00	−	−	1.46
4-1	10	20	16.70	0.02	0.00	−	−	0.02
4-2	20		437.42	24.03	0.00	−	−	24.03
4-3	30		62.75	12.89	0.00	−	−	3.09
4-4	40		31.70	11.49	0.75	−	−	0.00
5-1	30	40	64.36	0.00	4.91	−	−	0.00
5-2	40		410.36	0.00	10.46	−	−	0.00
5-3	50		127.36	25.10	2.64	−	−	0.00
5-4	60		56.28	20.18	0.00	−	−	1.37
6-1	50	60	114.85	0.00	7.51	−	−	0.00
6-2	60		1399.46	135.53	62.71	−	−	0.00
6-3	70		176.31	29.95	−	−	−	0.00
6-4	80		96.98	18.36	−	−	−	0.00
Average			230.00	26.99	7.42	0	0.11	4.20

Instance	m	n	EM		NS		MMRCH
Instance	m	n	AOV	ACT	AOV	ACT	AOV	ACT
1-1	3	3	92.23	0.10	78.07	0.00	92.23	0.00
1-2	4		256.12	1.62	220.97	0.01	256.12	0.001
1-3	5		329.31	11.15	309.19	0.01	329.31	0.00
1-4	6		403.96	61.01	379.34	0.02	401.82	0.00
2-1	4	5	89.24	7.43	22.29	0.01	78.61	0.00
2-2	5		250.54	73.73	178.28	0.01	230.26	0.00
2-3	6		324.48	1006.00	245.88	0.02	311.00	0.00
2-4	7		317.61	12184.70	255.74	0.03	310.69	0.00
3-1	7	10	−	−	241.68	0.04	347.07	0.01
3-2	10		−	−	325.29	0.08	483.92	0.01
3-3	12		−	−	460.92	0.11	610.80	0.01
3-4	15		−	−	766.71	0.22	885.81	0.01
4-1	10	20	−	−	−289.37	0.11	−79.03	0.02
4-2	20		−	−	795.38	0.73	1103.08	0.05
4-3	30		−	−	1469.12	2.39	1689.04	0.07
4-4	40		−	−	2303.30	4.46	2454.32	0.12
5-1	30	40	−	−	745.28	3.49	1262.08	0.16
5-2	40		−	−	1303.31	6.62	1988.48	0.26
5-3	50		−	−	2381.48	14.68	2861.76	0.15
5-4	60		−	−	3386.14	22.84	3768.95	0.18
6-1	50	60	−	−	1470.69	17.68	2364.17	0.20
6-2	60		−	−	2147.65	30.21	2893.06	0.29
6-3	70		−	−	3093.60	47.61	3894.06	0.36
6-4	80		−	−	3957.46	68.50	4578.02	0.48

A game theoretic model and a double oracle algorithm for the heterogeneous weapon target assignment problem

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 12

References 46

Related Articles 2

Recommended Articles

Metrics

Comments

Instance	Given the strategy d1		Given the strategy d2
Instance	PDOV	PDR	PDOV	PDR
1-1	18.13	58.57	120.28	77.48
1-2	15.91	85.90	23.16	72.41
1-3	6.51	87.61	2.91	72.63
1-4	5.93	84.00	16.78	86.38
2-1	252.75	80.25	45.93	69.89
2-2	29.16	71.83	737.54	81.42
2-3	26.49	80.06	87.53	83.15
2-4	21.49	82.64	61.68	89.41
3-1	43.61	85.09	56.37	84.95
3-2	48.77	90.58	303.12	89.96
3-3	32.52	91.62	174.42	91.33
3-4	15.53	94.04	39.09	93.28
4-1	72.69	86.04	29.49	81.93
4-2	38.69	92.83	392.33	93.94
4-3	14.97	96.96	40.02	95.38
4-4	6.56	97.32	22.63	96.81
5-1	69.34	95.29	45.24	92.18
5-2	52.57	96.02	127.69	93.00
5-3	20.17	98.98	85.94	99.43
5-4	11.31	99.22	36.31	99.46
6-1	60.75	98.87	63.43	98.40
6-2	34.71	99.04	233.28	98.32
6-3	25.87	99.24	143.29	98.94
6-4	15.68	99.29	59.34	99.34
Average	39.17	89.64	122.82	89.14

[1]	Zhanwu LI, Yizhe CHANG, Yingxin KOU, Haiyan YANG, An XU, You LI. Approach to WTA in air combat using IAFSA-IHS algorithm [J]. Journal of Systems Engineering and Electronics, 2018, 29(3): 519-529.
[2]	Wang Yanxia, Qian Longjun, Guo Zhi & Ma Lifeng. Weapon target assignment problem satisfying expected damage probabilities based on ant colony algorithm [J]. Journal of Systems Engineering and Electronics, 2008, 19(5): 939-944.