中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2022 , Vol. 44 >Issue 2: 38 - 42

DOI: https://doi.org/10.3969/j.issn.1673-3819.2022.02.008

Theory & Research

Multi-stage Dynamic Target Assignment Method for Air Defense

  • WU Hong-kun
Expand
  • Jiangsu Automation Research Institute, Lianyungang 222061, China

Received date: 2021-10-13

  Request revised date: 2021-11-16

  Online published: 2022-04-28

Copyright

Copyright reserved © 2022
Fold

Abstract

Weapon-target assignment (WTA) is one of the central part of command and control decision-making in air defense. Aiming at the inefficiency and poor dynamic performance of the traditional multi-stage assignment model, the model is improved by overlaying the weapon firing cycle and increasing the assignment times, so that it can be better applied to the air defense. Aiming at the slow convergence speed and poor stability of commonly used WTA algorithms, the solution process uses the KM algorithm to meet the real-time requirements of the improved dynamic model. The relevant parameters involved in solving dynamic WTA problems are described in detail. The simulation experiment results verify the effectiveness of the model and algorithm.

Key words： dynamic weapon-target assignment; multi-stage assignment model; weapon firing cycle; KM algorithm

Cite this article

WU Hong-kun . Multi-stage Dynamic Target Assignment Method for Air Defense[J]. Command Control and Simulation, 2022 , 44(2) : 38 -42 . DOI: 10.3969/j.issn.1673-3819.2022.02.008

现代局部热战中,空袭和防空对抗相当程度上影响着战争的进程和胜负[1]。防空系统在面临大规模梯次配置的空袭编队时,必须充分利用各火力单元的弹药资源,尽可能拦截更多更重要的目标,以实现作战效能最大化,在此过程中,武器-目标分配是指挥控制决策的关键环节。武器-目标分配(Weapon Target Assignment, WTA)又称火力分配,是指在一定的条件约束下,根据作战目的、武器性能、目标参数等因素,合理配置武器资源,优化火力打击体系。
从模型研究的角度,根据是否考虑时间因素,通常分为静态武器-目标分配模型(Static Weapon Target Assignment, SWTA)和动态武器-目标分配模型(Dynamic Weapon Target Assignment, DWTA)[2]。静态WTA模型强调在单个阶段内一次性求解分配方案,不考虑时间因素,仅将毁伤概率和目标威胁等因素作为优化对象,这样一来虽然可以提高求解效率,但模型过于简单,实用性受限。动态WTA模型则将分配过程分成多个阶段执行,在静态模型的基础上增加考虑时间约束和打击次序对分配结果的影响,从而使模型更贴近实际,合理性更强,但约束条件增多给求解计算造成困难。
从算法研究的角度,WTA是典型的非线性组合优化问题[3],随着武器与目标数量的增加,解空间将呈指数式扩大,给求解带来困难。目前主要有两类求解方法,一类是基于枚举的精确算法,如穷举法、隐枚举法、割平面法、分支定界法[4]等。这类算法精确度高、稳定性好,但计算效率偏低,很难用于多约束复杂问题。另一类是基于启发式策略的智能优化算法,如遗传算法[5]、粒子群算法[6]、蚁群算法[7]、模拟退火算法等。这类算法可以在不进行全枚举的情况下搜索到理想的解[8],但稳定性较差,容易出现重复迭代导致收敛慢,或过早收敛却陷入局部最优的情况。
当前针对SWTA的研究较多,针对DWTA的研究较少,并且大多都采用启发式算法进行求解,很难满足实际战场中实时性和准确性的要求。本文在传统的多级WTA模型的基础上进行改进,并结合KM算法对问题进行求解,为防空作战中的动态WTA问题给出了一种可行的解决方法。

1 动态WTA问题建模

1.1 目标函数

动态分配问题可视作S个阶段的静态分配问题,每个阶段用序号k进行区分。在第k个阶段,假设有m个武器构成武器集合W={W1, W2,…, Wm},有n个目标构成目标集合T={T1, T2,…, Tn},有目标函数[9]:
E(k)= ∑ j = 1 nvj(k) 1 - ∏ i = 1 m 1 - p ij ( k ) x ij ( k )
或 E(k)= ∑ j = 1 nvj(k) ∑ i = 1 mpij(k)xij(k)
∑ j = 1 n x ij ( k ) ≤ 1 , 　 i = 1,2 , … , m ∑ i = 1 m x ij ( k ) ≤ 1 , 　 j = 1,2 , … , n
目标函数中E(k)表示第k个阶段分配方案的作战收益值;vj(k)∈(0,1)表示第k个阶段目标Tj的威胁系数;pij(k)表示第k个阶段武器Wi对目标Tj的整体拦截概率;xij(k)是布尔量,用于判定武器Wi是否分配给目标Tj,是则xij(k)=1,否则xij(k)=0;约束条件表示,武器与目标之间采用“一对一”的分配方式。

1.2 时间因素

动态武器-目标分配中需要考虑的时间因素主要包括武器射击周期和目标来袭时间。
武器射击周期t0是指武器从射击第一个目标到射击第二个目标的时间间隔,即t0=tfw+tzh。服务时间tfw是指武器射击第一个目标的时间,包括导弹发射间隔总耗时tΔ,拦截导弹从发射到与目标相遇的飞行时间tfx,即tfw=tΔ+tfx。转火准备时间tzh是指武器转火射击第二个目标所需要的准备时间。
目标来袭时间指的是目标飞临发射区远界的时间tfy和飞临发射区近界的时间tfj。

1.3 资源约束

武器平台载弹量有限,为了保证打击效果并且提高资源利用率,本文通过设定拦截概率阈值的方式来约束武器平台发射的导弹数量。
假设武器Wi的载弹量为Ai,第k个阶段武器Wi对目标Tj发射Bi(k)枚导弹,单发导弹对目标的毁伤概率为dij(k),则Wi对Tj的总体拦截概率:
pij(k)=1-[1-dij(k) ] B i ( k )
定义拦截概率阈值Pj(k),武器对目标的拦截概率不得低于阈值,即pij(k)≥Pj(k),从而得到关于Bi(k)的约束条件:
B i ( k ) ≥ ln [ 1 - P i ( k ) ] ln [ 1 - d ij ( k ) ] , 　 i = 1,2 , … , m ∑ k = 1 S B i ( k ) ≤ A i , i = 1,2 , … , m
Pj的设定取决于Tj的威胁系数vj,对于威胁系数高的目标,拦截概率阈值设定的更高,对于vj<0.1的目标则不进行拦截。如表1。
表1 威胁系数与拦截概率阈值对应表
威胁系数 拦截概率阈值
0.9≤vj<1 0.95
0.7≤vj<0.9 0.85
0.5≤vj<0.7 0.75
0.3≤vj<0.5 0.65
0.1≤vj<0.3 0.55
vj<0.1 不进行拦截
在此约束条加下,若武器Wi的剩余弹药无法满足对来袭目标Tj实现高于拦截概率阈值Dj的拦截打击,则不考虑将Wi分配给Tj。若Wi的弹药全部用完,则将其从火力单元序列中移出。

1.4 改进多级分配模型

多级分配模型是动态WTA研究中的常用模型。传统的多级分配模型通常采用“射击-观察-射击”的模式[10],每个阶段的分配决策以上一阶段的交战结果(来袭目标生存或被击毁)作为新的初始条件[11],防御方对未被击毁的目标进行新一轮的分配,时间窗口图如图1所示。图中白色框表示武器的射击周期t0,灰色框表示防空系统等待阶段1的交战结果判定以及进行阶段2发射准备的时间。传统的多级分配模型中,武器对不同目标的射击周期不存在重叠。
图1 传统多级分配模型时间窗口图
当来袭目标数量多且时间紧迫时,防空系统为了等待判定交战结果往往会耗费许多时间,这在实际作战中对防御方非常不利。因此,本文对多级分配模型进行改进。区别于传统模型中仅有生存和击毁两种状态,改进的多级分配模型将来袭目标分为:未分配、已分配未交战、已交战被摧毁和突破拦截等四种状态。防空系统不再等待上一阶段的交战结果判定,而是以固定的时间间隔连续进行分配轮次的求解,此时的时间窗口图如图2所示。
图2 改进多级分配模型时间窗口图
由于目标数量过多,防空系统必须命令武器平台提前准备转火射击,以应对新目标。此时武器的射击周期存在重叠,武器发射的导弹与上一个目标还未交战便进行对下一个目标的转火准备。此时武器若想实现转火拦截,需要满足约束条件:
tfy≤tzh+tΔ≤tfj
若tzh+tΔ>tfj,则拦截失败;若tzh+tΔ<tfy,则武器转火准备过于提前,待机过久而浪费时间。

2 动态WTA问题求解

2.1 KM算法基本原理

KM(Kuhn-Munkras)算法是一种在多项式时间内查找有权二部图最优匹配的算法[12],其在匈牙利算法的基础上引入了可行顶标以及相等子图等概念[13],以实现二部图最优匹配的求解。
将WTA问题用有权二部图进行刻画,如图1所示。G=(W, T, L, ω),武器集合W和目标集合T是顶点集合,显然二者互不相交,且集合内部元素之间不存在分配关系;L是边集合,与Tj间的连线lij表示Wi与Tj可能存在的分配关系;ω是边权值集合,ωij表示lij的权值,是判断是否将Wi分配给Tj的主要依据。如此一来只要合理设置边权值ωij就可以将WTA问题转化为有权二部图求解最优匹配的问题。
图3 WTA的有权二部图模型
定义:G=(W, T, L, ω)是有权完备二部图,设顶点Wi的顶标为wi,顶点Tj的顶标为tj,若子图Ge中的所有边都满足wi+tj=ωij,则称Ge为G的相等子图,若Ge存在原图G的完备匹配,则该完备匹配便是原图的最优匹配。
KM算法主要步骤为:
step1:初始化各个顶点的可行顶标值;
step2:找出相等子图并使用匈牙利算法搜索最大匹配;
step3:判断最大匹配是否为原图的完备匹配,若是则该匹配便是所求的最优匹配,若不是则修改可行顶标值。
step4:重复step2~3直至找到最优匹配。

2.2 剩余弹药资源判定系数

约束条件规定武器Wi的剩余弹药对来袭目标Tj的总体拦截概率pij要高于阈值Pj。如果要在分配计算之前遍历所有武器,判断其剩余弹药量是否满足要求,显然会增加求解耗时。因此本文定义判定剩余弹药资源的系数eij:
eij=[1-(1-pij ) a i-Dj]+1
式中方括号表示取整函数,ai表示武器Wi的剩余导弹枚数。当武器剩余弹药量对目标的总体拦截概率大于Dj时,eij=1;小于Dj时,eij=0。

2.3 目标威胁系数vj的变化

随着时间和分配轮次的推移,系统会接收到数个阶段以前的交战结果,在此过程中目标的威胁会发生变化。
当目标未被分配时,威胁系数不变;
当目标已被分配未交战时,认为目标的威胁系数降低,本文中用公式(6)来计算:
vj(k+1)=vj(k)×[1-dij(k)]
当目标已被分配已交战且目标被摧毁,则将其威胁系数置0;
当目标已被分配已交战但目标突破拦截,则重置其威胁系数并再次加入分配轮次。

2.4 匹配度ωij

匹配度ωij也是有权二部图的边权值,边权值的加和是KM算法求解依据,为了契合目标函数与分配模型,定义:
ωij=eij×(vi×dij)
定义匹配度矩阵Ω=[ωij]m×n,用来统一表示武器Wi对应目标Tj的匹配度,如图4。
图4 匹配度矩阵Ω
将匹配度矩阵Ω代入KM算法进行求解即可求得目标分配结果。
每个阶段目标分配结果求出之后,若武器对目标的单发射击拦截概率满足大于等于拦截概率阈值则输出攻击次数ai(k)=1,若不满足,则根据式(3)计算ai(k)的值并输出。然后根据ai(k)和dij(k)求出pij(k),并代入目标函数中得到分配方案的作战收益值。

3 仿真实验与分析

为验证算法和模型的有效性,分别设置静态WTA和动态WTA仿真示例进行实验分析。实验环境为Windows10系统、i7-9750H处理器、16G运行内存。

3.1 静态分配实验

设置武器与目标的数量为10×10,由于是静态分配实验,所以只有一个分配阶段且仅考虑目标威胁系数vj和武器对目标的拦截概率pij,具体参数如表2所示。
表2 拦截概率与威胁系数
编号 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
vj 0.84 0.69 0.79 0.92 0.54 0.81 0.59 0.67 0.32 0.75
W1 0.87 0.27 0.33 0.63 0.70 0.80 0.64 0.43 0.49 0.66
W2 0.52 0.53 0.87 0.54 0.65 0.70 0.53 0.23 0.79 0.41
W3 0.72 0.82 0.23 0.38 0.35 0.69 0.48 0.41 0.53 0.64
W4 0.59 0.49 0.34 0.80 0.64 0.54 0.26 0.77 0.63 0.70
W5 0.76 0.89 0.61 0.76 0.53 0.90 0.08 0.78 0.81 0.71
W6 0.58 0.72 0.65 0.71 0.50 0.67 0.76 0.79 0.91 0.87
W7 0.80 0.14 0.92 0.43 0.47 0.56 0.45 0.67 0.48 0.06
W8 0.85 0.31 0.64 0.93 0.59 0.02 0.53 0.74 0.15 0.79
W9 0.09 0.69 0.84 0.77 0.30 0.86 0.64 0.58 0.83 0.66
W10 0.66 0.46 0.29 0.64 0.89 0.58 0.86 0.87 0.69 0.83
令ωij=vj×pij,代入KM算法进行求解,实验结果如表格3所示。分配求解过程耗时不到0.001 s,分配方案总收益值E=5.900 4,经过分支定界法验算可知所求结果是最优解。
表3 静态分配实验结果
目标 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
武器 W1 W3 W7 W8 W2 W5 W10 W4 W9 W6
同样在10×10规模的WTA问题中,将KM算法分支定界法(B&B)、遗传算法(GA)和粒子群算法(PSO)进行对比,每种算法都进行50次重复实验,对比结果如表4所示。
表4 算法性能对比
算法 最优解次数 平均耗时/s
GA 44 0.75
PSO 42 0.52
B&B 50 16.8
KM 50 <0.001
从实验结果可知,分支定界法和KM算法作为精确解法,可以稳定求得最优解,但KM算法搜索增广路径的速度远远快于分支定界法搜索根节点的速度。遗传算法和粒子群算法虽然在计算效率上优于枚举类算法,但求解效果不太稳定,容易陷入局部最优。
现代空袭目标飞行高度低、速度快、暴露时间较短,留给指控系统分配决策模块的时间往往以毫秒计算。与其他3种算法相比,KM算法的精度和速度都具有明显优势,能够更好地适应改进后多级动态WTA模型的实时性和准确性要求。

3.2 动态分配实验

假设我方防空阵地有5台地空导弹武器,敌方共有20个目标分批次来袭。武器与目标的相关参数见表5和表6。
表5 拦截概率与威胁系数
编号 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
vj 0.81 0.12 0.25 0.87 0.76 0.44 0.61 0.77 0.47 0.30
W1 0.88 0.47 0.49 0.54 0.11 0.04 0.77 0.55 0.02 0.36
W2 0.48 0.71 0.81 0.92 0.06 0.72 0.40 0.55 0.49 0.22
W3 0.47 0.72 0.84 0.27 0.57 0.74 0.68 0.31 0.61 0.34
W4 0.33 0.87 0.03 0.49 0.61 0.65 0.92 0.64 0.84 0.29
W5 0.80 0.70 0.69 0.54 0.90 0.67 0.56 0.02 0.66 0.58
编号 T11 T12 T13 T14 T15 T16 T17 T18 T19 T20
vj 0.43 0.36 0.85 0.69 0.84 0.66 0.68 0.48 0.32 0.33
W1 0.68 0.65 0.76 0.76 0.53 0.69 0.67 0.83 0.92 0.92
W2 0.58 0.85 0.66 0.88 0.55 0.42 0.42 0.80 0.67 0.66
W3 0.87 0.52 0.72 0.59 0.76 0.58 0.80 0.85 0.09 0.66
W4 0.63 0.54 0.39 0.80 0.76 0.71 0.43 0.93 0.77 0.64
W5 0.64 0.53 0.48 0.26 0.08 0.76 0.45 0.53 0.67 0.86
表6 目标来袭时间
编号 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
tfy(s) 5 5.5 5.7 6.1 6.8 7.3 7.7 8.1 8.8 8.9
tfj(s) 10.3 12.4 10.8 11.7 15.8 13.7 14.3 14.1 14.8 15.7
编号 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10
tfy(s) 9.9 10.5 10.8 11.6 11.9 12.3 12.7 13.3 13.8 14.1
tfj(s) 16.3 16.8 17.4 17.9 18.5 19 19.5 20.1 20.6 21.1
由于KM算法对于低维度WTA问题的求解耗时几乎可以忽略不计,所以我方防空系统目标分配轮次刷新间隔较短,假设为1 s。武器平台W1~W5的转火准备时间分别为:1 s、1 s、2 s、2 s、3 s。
具体的分配求解过程如下:
第0阶段:时刻0 s,此时防空发射区没有目标,不进行分配计算。
第1阶段:时刻5 s,T1飞入发射区,分配W1拦截。
第2阶段:时刻6 s,T2与T3飞入发射区,此时W1未完成转火准备,分配W4拦截T2,W3拦截T3。
第3阶段:时刻7 s,T4与T5飞入发射区,此时W1、W3、W4未完成转火准备,分配W2拦截T4,W5拦截T5。
第4阶段:时刻8 s,T6与T7飞入发射区,此时W5未完成转火准备,分配W3拦截T6,W4拦截T7。
……
直到第11阶段,完成对所有目标的分配,具体见表7。
表7 动态分配实验结果
阶段k 时刻/s 分配结果
i→j→[ai(k)]
0 0 ——
1 5 1→1→[1]
2 6 4→2→[1],3→3→[1]
3 7 2→4→[1],5→5→[1]
4 8 3→6→[1],4→7→[1]
5 9 1→8→[3],2→9→[2]
6 10 4→10→[4],2→11→[2]
7 11 3→12→[2],2→13→[2]
8 12 2→14→[1],4→15→[2]
9 13 5→16→[1],3→17→[1]
10 14 4→18→[1],1→19→[1]
11 15 2→20→[1]
根据实验结果可知,改进后的多级动态分配模型由于不用等待结果判定,可以在有限时间内执行更多的分配轮次,即使面对数倍于己的来袭目标,也可以高效地进行分配求解。

4 结束语

本文以防空作战WTA为背景,尝试对传统的多级分配模型进行改进,通过设定可叠加的武器射击周期,并以固定频率刷新分配求解轮次的方式,使得改进后的模型可以用于目标较多且时间紧迫的作战场景,为解决动态WTA问题给出了一种可行的方案。在算法求解过程中,采用KM算法以满足改进后多级分配模型对算法的实时性和准确性要求。但实际作战中需要考虑的因素还有很多,后续仍需要进一步对模型进行细化和改进。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
娄寿春. 地空导弹射击指挥控制模型[M]. 北京: 国防工业出版社, 2009.

[2]
李勇君, 黄卓, 郭波. 武器-目标分配问题综述[J]. 兵工自动化, 2009, 28(11):1-4+9.

[3]
孔德鹏, 常天庆, 郝娜, 等. 基于对抗的突击武器与支援武器协同火力打击决策方法[J]. 兵工学报, 2019, 40(3): 629-640.

[4]
TOKGÖZ A, BULKAN S. Weapon target assignment with combinatorial optimization techniques[J]. International Journal of Advanced Research in Artificial Intelligence, 2013, 2(7): 39-50.

[5]
董朝阳, 路遥, 王青. 改进的遗传算法求解火力分配优化问题[J]. 兵工学报, 2016, 37(1): 97-102.

[6]
王力超, 乔勇军, 李永胜. 基于CE-CAPSO武器目标分配优化算法[J]. 火力与指挥控制, 2020, 45(11): 82-87.

[7]
崔莉莉. 基于蚁群算法的武器-目标分配问题研究[D]. 上海:上海交通大学, 2011.

[8]
王邑, 孙金标, 肖明清, 等. 基于类型2区间模糊K近邻分类器的动态武器-目标分配方法研究[J]. 系统工程与电子技术, 2016, 38(6): 1314-1319.

[9]
黄大山, 徐克虎, 王天召. 求解WTA问题的智能算法评价准则[J]. 火力与指挥控制, 2013, 38(8): 43-46.

[10]
吴文海, 郭晓峰, 周思羽, 等. 改进差分进化算法求解武器目标分配问题[J]. 系统工程与电子技术, 2021, 43(4): 1012-1021.

[11]
邵诗佳. 基于智能算法的武器目标分配问题研究[D]. 哈尔滨:哈尔滨工程大学, 2019.

[12]
Bruff D. The assignment problem and the Hungarian method[J]. Notes for Math, 2005, 20(5): 29-47.

[13]
魏恩伟, 李伟华, 张之涵, 等. 基于改进匈牙利算法的非侵入式负荷匹配方法[J]. 电测与仪表, 2019, 56(22): 58-64.

Options
Outlines

/

〈 〉