基于SDP的動(dòng)態(tài)武器目標(biāo)分配決策算法研究

摘 要：武器目標(biāo)分配是水面艦艇防空反導(dǎo)作戰(zhàn)指揮決策的核心環(huán)節(jié)，決策結(jié)果的優(yōu)劣直接影響了防空反導(dǎo)作戰(zhàn)的最終防御效果與水面艦艇的生存能力。針對(duì)當(dāng)前武器目標(biāo)分配算法較少考慮攔截結(jié)果的不確定性和多梯次攔截的序貫分配需求，難以適應(yīng)戰(zhàn)場動(dòng)態(tài)變化的問題，設(shè)計(jì)一種基于隨機(jī)動(dòng)態(tài)規(guī)劃的動(dòng)態(tài)武器目標(biāo)分配決策算法。通過進(jìn)制變換編碼并計(jì)算目標(biāo)狀態(tài)和武器狀態(tài)的變化規(guī)律，基于戰(zhàn)場態(tài)勢轉(zhuǎn)移概率采用逆向迭代算法生成序貫攔截方案。最終精確求解面向多梯次攔截的動(dòng)態(tài)武器目標(biāo)分配最優(yōu)策略，回答“誰來打”“打多少”和“何時(shí)打”的水面艦艇防空反導(dǎo)作戰(zhàn)決策問題。通過算例驗(yàn)證和數(shù)值仿真表明，使用該算法能夠獲得比靜態(tài)武器目標(biāo)分配算法更好的攔截效能，在最好情況下能夠降低空中來襲目標(biāo)72%的威脅期望。

關(guān)鍵詞：水面艦艇； 防空作戰(zhàn)； 動(dòng)態(tài)武器目標(biāo)分配； 隨機(jī)動(dòng)態(tài)規(guī)劃

中圖分類號(hào)：TJ760

文獻(xiàn)標(biāo)識(shí)碼： A

文章編號(hào)：1673-5048（2023）05-0050-07

DOI： 10.12132/ISSN.1673-5048.2023.0093

0 引" 言

世界范圍內(nèi)近幾次高技術(shù)條件下的局部戰(zhàn)爭表明，水面艦艇防空反導(dǎo)作戰(zhàn)是高烈度的體系對(duì)抗，“攻擊體系”與“防御體系”的關(guān)系始終處于平衡-失衡-再平衡的螺旋型發(fā)展之中。1967年10月21日，第3次中東戰(zhàn)爭中以色列“埃拉特”驅(qū)逐艦被埃及“冥河”反艦導(dǎo)彈擊沉。2022年4月13日，俄羅斯黑海艦隊(duì)“莫斯科”巡洋艦被烏克蘭“海王星”亞音速反艦導(dǎo)彈重創(chuàng)，反艦導(dǎo)彈等成為打擊水面艦艇的主要兵器，并在體系對(duì)抗中占據(jù)優(yōu)勢，使得水面艦艇防空反導(dǎo)作戰(zhàn)難度陡然突增。

水面艦艇防空反導(dǎo)作戰(zhàn)決策是戰(zhàn)術(shù)技術(shù)結(jié)合密切、不確定因素多、實(shí)時(shí)性高、對(duì)抗性強(qiáng)的復(fù)雜決策過程，需要經(jīng)過早期目標(biāo)預(yù)警、持續(xù)目標(biāo)跟蹤、多源目標(biāo)識(shí)別、威脅判斷排序、武器目標(biāo)分配以及武器引導(dǎo)控制等過程才能最終對(duì)空中來襲目標(biāo)進(jìn)行有效攔截［1］。其中，武器目標(biāo)分配（Weapon Target Assignment，WTA）決策是水面艦艇防空反導(dǎo)作戰(zhàn)指揮與控制的核心環(huán)節(jié)，旨在求解最優(yōu)武器目標(biāo)分配方案，從而以最小的時(shí)間和資源代價(jià)，獲取最大的防空反導(dǎo)作戰(zhàn)效能。WTA決策的優(yōu)劣直接影響了水面艦艇防空作戰(zhàn)的最終防御效果與生存能力［2］。

按照是否考慮戰(zhàn)場動(dòng)態(tài)對(duì)抗的不確定性，可以將WTA決策分為兩類［3］。一是靜態(tài)WTA決策［4］，主要求解每類攔截武器對(duì)每個(gè)來襲目標(biāo)應(yīng)該分配多少火力，回答“誰來打”“打多少”的問題。目前，WTA研究領(lǐng)域以靜態(tài)WTA決策算法為主［5］，Yucel等［6］采用分支界定算法，實(shí)現(xiàn)了以消耗資源最少為優(yōu)化目標(biāo)的WTA精確求解； 徐加強(qiáng)等［7］將遺傳算法結(jié)合禁忌搜索的方法應(yīng)用于常規(guī)導(dǎo)彈分配問題中，實(shí)現(xiàn)了全局與局部搜索能力的融合，在較短時(shí)間內(nèi)獲得了最優(yōu)解； 唐蘇妍等［8］基于擴(kuò)展合約網(wǎng)絡(luò)的動(dòng)態(tài)目標(biāo)分配算法，提升傳統(tǒng)合約網(wǎng)絡(luò)性能，解決了網(wǎng)絡(luò)化防空體系中的目標(biāo)分配問題。然而，靜態(tài)WTA決策沒有考慮攔截失敗、多次攔截等不確定性和動(dòng)態(tài)性，難以適應(yīng)戰(zhàn)場的復(fù)雜變化。二是動(dòng)態(tài)WTA決策［9］，考慮戰(zhàn)場演進(jìn)引起殺傷概率、來襲目標(biāo)數(shù)量等決策要素的持續(xù)變化，不僅回答“誰來打”“打多少”，還需要進(jìn)一步解決“何時(shí)打”的決策時(shí)機(jī)問題［10］。由于建模和求解的困難，當(dāng)前針對(duì)動(dòng)態(tài)WTA決策的研究較少，文獻(xiàn)［11-12］提出了基于馬爾科夫決策過程的動(dòng)態(tài)目標(biāo)分配

算法，通過轉(zhuǎn)移概率刻畫攔截過程的動(dòng)態(tài)變化。但是，算法對(duì)目標(biāo)來襲間隔、武器射擊時(shí)刻等有較為嚴(yán)苛的假設(shè)，因此適用場景較為有限。

為充分考慮水面艦艇防空反導(dǎo)作戰(zhàn)過程中的不確定性與動(dòng)態(tài)變化，顯著提升對(duì)抗場景下的臨機(jī)決策質(zhì)量，本文首先將動(dòng)態(tài)WTA決策建模為序貫決策問題，然后基于隨機(jī)動(dòng)態(tài)規(guī)劃（Stochastic Dynamic Programming，SDP）［13］，設(shè)計(jì)針對(duì)動(dòng)態(tài)WTA的精確求解算法，最后通過算例對(duì)比動(dòng)態(tài)與靜態(tài)WTA算法的求解質(zhì)量。

2.2 基于SDP的動(dòng)態(tài)WTA決策算法設(shè)計(jì)

狀態(tài)轉(zhuǎn)移概率是描述多次攔截過程中戰(zhàn)場態(tài)勢演進(jìn)趨勢的核心參數(shù)。針對(duì)m個(gè)來襲目標(biāo)使用n個(gè)可用武器共進(jìn)行s次攔截的場景，為了能夠應(yīng)對(duì)不同攔截結(jié)果，實(shí)現(xiàn)動(dòng)態(tài)生成分配方案的最優(yōu)策略，首先要解決2（m+n）種不同戰(zhàn)場狀態(tài)之間狀態(tài)轉(zhuǎn)移概率的計(jì)算，算法流程見圖4。首先，根據(jù)BSA編碼機(jī)制依次確定從當(dāng)前戰(zhàn)場狀態(tài)x能夠轉(zhuǎn)移到的每一個(gè)可能的后續(xù)戰(zhàn)場狀態(tài)x′，并將轉(zhuǎn)移概率矩陣T中對(duì)應(yīng)從x至x′的轉(zhuǎn)移概率txux′標(biāo)記為合法轉(zhuǎn)移； 然后，通過位運(yùn)算檢查轉(zhuǎn)移前目標(biāo)狀態(tài)z到轉(zhuǎn)移后目標(biāo)狀態(tài)z′發(fā)生的變化，其中令⊕代表二進(jìn)制按位邏輯異或操作； 最后，根據(jù)目標(biāo)狀態(tài)變化情況和目標(biāo)存活概率矩陣Q，完成轉(zhuǎn)移概率計(jì)算。

基于戰(zhàn)場狀態(tài)轉(zhuǎn)移概率矩陣，基于隨機(jī)動(dòng)態(tài)規(guī)劃理論，采用逆向迭代算法［15-16］，從末次攔截開始求解面向s次攔截的分配方案最優(yōu)策略，算法流程見圖5。

該算法的時(shí)間復(fù)雜度為O（2（m+n）·mn·s），每次攔截分配方案的可選擇性和攔截結(jié)果的不確定性是導(dǎo)致時(shí)間復(fù)雜度提升的最主要原因； 空間復(fù)雜度為O（4m+n·mn），主要用于存儲(chǔ)狀態(tài)轉(zhuǎn)移矩陣。

3 動(dòng)態(tài)WTA決策算法分析

3.1 基本算例

以1.1節(jié)的場景為例，算法運(yùn)行過程如圖6所示。其中，加粗圓形表示的根節(jié)點(diǎn)代表函數(shù)Qk（xk， Uk），即在戰(zhàn)場狀態(tài)xk下采用分配方案Uk后最終能獲得的最小目標(biāo)剩余威脅期望； 圓角矩形表示的中間節(jié)點(diǎn)代表分配方案矩陣Uk； 正常圓形表示的葉節(jié)點(diǎn)代表函數(shù)J*k－1（xk－1），即在戰(zhàn)場態(tài)勢xk－1下采取最優(yōu)分配策略后最終能獲得的最小目標(biāo)剩余威脅期望。根節(jié)點(diǎn)與中間節(jié)點(diǎn)連線權(quán)重代表Qk（xk， Uk）的函數(shù)值，其中加粗連線代表在戰(zhàn)場狀態(tài)xk下，使得Qk（xk， Uk）取得最小目標(biāo)剩余威脅期望的分配方案，即U*k=argminUk∈U（xk）Q（xk， Uk）。中間節(jié)點(diǎn)與葉節(jié)點(diǎn)連線權(quán)重代表在分配方案Uk執(zhí)行后，戰(zhàn)場狀態(tài)從xk轉(zhuǎn)移至xk－1的概率，即函數(shù)P（xk－1|xk， Uk）。算法從第二次攔截的葉節(jié)點(diǎn)開始計(jì)算，逆向獲取根節(jié)點(diǎn)的目標(biāo)剩余威脅期望； 第二次攔截的根節(jié)點(diǎn)最小期望值，又成為了第一次攔截的葉節(jié)點(diǎn)，進(jìn)入新一輪逆向迭代計(jì)算。

“盡早攔截、盡遠(yuǎn)攔截”的作戰(zhàn)原則要求，應(yīng)當(dāng)在第1次攔截機(jī)會(huì)時(shí)就使用所有艦空導(dǎo)彈，在該原則下最優(yōu)分配方案即是靜態(tài)WTA決策代表的最優(yōu)決策，即圖中分配方案U2。但是根據(jù)動(dòng)態(tài)WTA決策計(jì)算顯示，當(dāng)敵方采用不同殺傷能力的反艦導(dǎo)彈搭配協(xié)同進(jìn)攻的作戰(zhàn)樣式時(shí)，我方應(yīng)該預(yù)留部分艦空導(dǎo)彈，針對(duì)可能在第1次攔截時(shí)突防的高殺傷目標(biāo)進(jìn)行二次攔截，從而達(dá)到更好的攔截效果。此時(shí)，動(dòng)態(tài)WTA決策算法就能夠量化地解決資源應(yīng)該在哪次攔截時(shí)使用，應(yīng)該用多少艦空導(dǎo)彈打擊哪個(gè)目標(biāo)等目標(biāo)分配決策問題。

3.2 動(dòng)態(tài)與靜態(tài)WTA決策算法對(duì)比

為了分析動(dòng)態(tài)WTA決策算法解的質(zhì)量，通過構(gòu)造隨機(jī)樣本測試比較動(dòng)態(tài)WTA決策算法和靜態(tài)WTA決策算法效果上的差別，其中殺傷概率隨機(jī)取值范圍為pij∈［0.6， 0.9］，目標(biāo)威脅隨機(jī)取值范圍為li∈［25， 100］。兩種算法對(duì)比結(jié)果如表1所示。表中m表示目標(biāo)數(shù)量，n表示武器數(shù)量； us表示靜態(tài)WTA算法求解結(jié)果，u（2）d表示動(dòng)態(tài)WTA算法針對(duì)兩次攔截機(jī)會(huì)的求解結(jié)果，u（3）d表示動(dòng)態(tài)WTA算法針對(duì)三次攔截機(jī)會(huì)的求解結(jié)果； 后四列給出了不同攻擊次數(shù)下，動(dòng)態(tài)WTA決策算法和靜態(tài)WTA決策算法效果的變化值以及變化率。

對(duì)表1數(shù)值仿真數(shù)據(jù)進(jìn)行分析，首先，在給定目標(biāo)數(shù)量和攔截次數(shù)的情況下，不論是靜態(tài)還是動(dòng)態(tài)分配算法，隨著武器數(shù)量的增多目標(biāo)剩余威脅期望均隨之下降;動(dòng)態(tài)WTA算法下降幅度顯著高于靜態(tài)算法。如在3個(gè)來襲目標(biāo)即m=3的條件下，當(dāng)武器數(shù)量由1增加至5時(shí)，靜態(tài)WTA算法us使目標(biāo)剩余威脅期望從87.37下降至15.55，而動(dòng)態(tài)WTA算法u（2）d和u（3）d使目標(biāo)剩余威脅期望下降至7.01和5.8。

其次，在給定武器數(shù)量和攔截次數(shù)的情況下，隨著目標(biāo)數(shù)量的增加，動(dòng)態(tài)WTA算法能夠更好的抑制目標(biāo)剩余威脅期望的增長。如在使用4個(gè)武器進(jìn)行2次攔截即n=4， s=2的情況下，當(dāng)目標(biāo)數(shù)量由1增加至5時(shí)，使用靜態(tài)WTA算法us時(shí)目標(biāo)剩余威脅期望由0.56增長至90.18，而使用動(dòng)態(tài)WTA算法u（2）d僅增長至72.5。

最后，在給定目標(biāo)數(shù)量和武器數(shù)量的情況下，隨著攔截次數(shù)的增加，使用動(dòng)態(tài)WTA算法能夠更有效地降低目標(biāo)剩余威脅期望。如在使用2個(gè)目標(biāo)和5個(gè)武器的情況即m=2， n=5，使用動(dòng)態(tài)WTA算法進(jìn)行2次攔截即u（2）d時(shí)，目標(biāo)剩余威脅期望比靜態(tài)WTA算法下降64%，當(dāng)進(jìn)行3次攔截即u（3）d時(shí)，進(jìn)一步下降至72%。

綜上所述，使用動(dòng)態(tài)WTA算法的攔截效能顯著優(yōu)于靜態(tài)WTA算法。根據(jù)數(shù)值仿真反映的規(guī)律，在防空反導(dǎo)作戰(zhàn)過程中，當(dāng)艦空導(dǎo)彈數(shù)量多于目標(biāo)數(shù)量時(shí)，使用動(dòng)態(tài)WTA算法能夠獲得更好的攔截效能； 當(dāng)艦空導(dǎo)彈數(shù)量少于目標(biāo)數(shù)量時(shí)，使用動(dòng)態(tài)WTA算法能夠更好地降低目標(biāo)剩余威脅。同時(shí)，如果能夠盡可能增加攔截次數(shù)，則動(dòng)態(tài)WTA算法能夠更好地提升水面艦艇的生存能力。

4 結(jié)" 論

本文針對(duì)動(dòng)態(tài)武器目標(biāo)分配問題，在考慮攔截結(jié)果的不確定性和攔截過程的動(dòng)態(tài)性的基礎(chǔ)上，設(shè)計(jì)了基于隨機(jī)動(dòng)態(tài)規(guī)劃的動(dòng)態(tài)武器目標(biāo)分配決策算法，并通過BSA編碼機(jī)制簡化了對(duì)分配方案多樣性和攔截結(jié)果隨機(jī)性的處理。通過算例驗(yàn)證以及與動(dòng)態(tài)武器目標(biāo)分配決策算法進(jìn)行比較，可以發(fā)現(xiàn)在多數(shù)場景下，特別是在武器較充足或者攔截機(jī)會(huì)較多的情況下動(dòng)態(tài)分配的對(duì)敵攔截效果顯著好于靜態(tài)分配。對(duì)比分析證明了動(dòng)態(tài)武器分配算法的潛在實(shí)用價(jià)值和優(yōu)勢，為水面艦艇防空作戰(zhàn)決策輔助系統(tǒng)提供了新的決策算法。當(dāng)然，目前該算法為了精確求解最優(yōu)方案，仍然面臨求解時(shí)間復(fù)雜度隨著武器數(shù)量、目標(biāo)數(shù)量以及攔截次數(shù)的增長而陷入“維度爆炸”的問題。有待在未來的研究工作中進(jìn)一步分析和解決。

參考文獻(xiàn)：

［1］ 李勇君，" 黃卓，" 郭波. 武器-目標(biāo)分配問題綜述［J］. 兵工自動(dòng)化， 2009， 28（11）： 1-4.

Li Yongjun， Huang Zhuo， Guo Bo. Review of Weapon-Target Assignment Problem［J］. Ordnance Industry Automation， 2009， 28（11）： 1-4.（in Chinese）

［2］ 劉傳波， 邱志明， 吳玲， 等. 動(dòng)態(tài)武器目標(biāo)分配問題的研究現(xiàn)狀與展望［J］. 電光與控制， 2010， 17（11）： 43-48.

Liu Chuanbo， Qiu Zhiming， Wu Ling， et al. Review on Current Status and Prospect of Researches on Dynamic Weapon Target Assignment［J］. Electronics Optics amp; Control， 2010， 17（11）： 43-48.（in Chinese）

［3］ 楊進(jìn)帥， 李進(jìn)， 王毅. 武器-目標(biāo)分配問題研究［J］. 火力與指揮控制， 2019， 44（5）： 6-11.

Yang Jinshuai， Li Jin， Wang Yi. Study of Weapon Target Assignment Problem［J］. Fire Control amp; Command Control， 2019， 44（5）： 6-11.（in Chinese）

［4］ 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.

［5］ Kline A， Ahner D， Hill R. The Weapon-Target Assignment Pro-blem［J］. Computers amp; Operations Research， 2019， 105： 226-236.

［6］ Yucel A， Rosenberger J M， Hwang H S， et al. The Generalized Weapon Target Assignment Problem［C］∥10th International Command and Control Research and Technology Symposium， 2005.

［7］ 徐加強(qiáng)， 畢義明， 汪民樂， 等. 基于時(shí)空約束的常規(guī)導(dǎo)彈火力分配建模與實(shí)現(xiàn)［J］. 系統(tǒng)工程與電子技術(shù)， 2011， 33（9）： 2025-2029.

Xu Jiaqiang， Bi Yiming， Wang Minle， et al. Modeling and Realization of Conventional Missile Fire Assignment Based on Time-Space Restriction［J］. Systems Engineering and Electronics， 2011， 33（9）： 2025-2029.（in Chinese）

［8］ 唐蘇妍， 梅珊， 朱一凡， 等. 基于擴(kuò)展合同網(wǎng)協(xié)議的分布式武器目標(biāo)分配方法［J］. 系統(tǒng)工程與電子技術(shù)， 2011， 33（3）： 568-574.

Tang Suyan， Mei Shan， Zhu Yifan， et al. Distributed Weapon Target Assignment Algorithm Based on Extended Contract Net Protocol［J］. Systems Engineering and Electronics， 2011， 33（3）： 568-574.（in Chinese）

［9］ Emrah G. Dynamic Weapon Target Assignment Problem［D］. Ankara： Middle East Technical University， 2008.

［10］ 孟慶操， 楊光. 航母編隊(duì)防空作戰(zhàn)效能評(píng)估指標(biāo)體系構(gòu)建［J］. 艦船電子工程， 2015， 35（10）： 1-4.

Meng Qingcao， Yang Guang. Design of Effectiveness Estimation Index System of Air Defense of the Aircraft Carrier Formation［J］. Ship Electronic Engineering， 2015， 35（10）： 1-4.（in Chinese）

［11］ 韓松臣， 秦俊奇， 韓品堯， 等. 馬爾可夫決策過程在目標(biāo)分配中的應(yīng)用［J］. 哈爾濱工業(yè)大學(xué)學(xué)報(bào)， 1996， 28（2）： 32-36.

Han Songchen， Qin Junqi， Han Pinyao， et al. An Application of the Markov Decision Process to Target Assignment［J］. Journal of Harbin Institute of Technology， 1996， 28（2）： 32-36.（in Chinese）

［12］ 蔡懷平， 劉靖旭， 陳英武. 動(dòng)態(tài)武器目標(biāo)分配問題的馬爾可夫性［J］. 國防科技大學(xué)學(xué)報(bào)， 2006， 28（3）： 124-127.

Cai Huaiping， Liu Jingxu， Chen Yingwu. On the Markov Characteristic of Dynamic Weapon Target Assignment Problem［J］. Journal of National University of Defense Technology， 2006， 28（3）： 124-127.（in Chinese）

［13］ Cristobal M P， Escudero L F， Monge J F. On Stochastic Dynamic Programming for Solving Large-Scale Planning Problems under Uncertainty［J］. Computers amp; Operations Research， 2009， 36（8）： 2418-2428.

［14］ 馬其東， 周俊， 樊繼功. 艦空導(dǎo)彈武器系統(tǒng)轉(zhuǎn)火射擊能力研究［J］. 現(xiàn)代防御技術(shù)， 2005， 33（1）： 49-51.

Ma Qidong， Zhou Jun， Fan Jigong. Research of Shifting Fire Po-wer Ability of Ship to Air Missile Weapon System［J］. Modern Defense Technology， 2005， 33（1）： 49-51.（in Chinese）

［15］ Marescot L， Chapron G， Chadès I， et al. Complex Decisions Made Simple： A Primer on Stochastic Dynamic Programming［J］. Methods in Ecology and Evolution， 2013， 4（9）： 872-884.

［16］ Ruszczyński A， Shapiro A. Stochastic Programming Models［M］∥Handbooks in Operations Research and Management Science. Amsterdam： Elsevier， 2003： 1-64.

SDP-Based Dynamic Weapon Target Assignment Algorithm

Li Yang1，2*，Liu Geng1，Hu Xiaohui2，F(xiàn)an Yao1，Kong Guanqiao1

（1. Systems Engineering Research Institute，China State Shipbuilding Corporation，Beijing 100036，China；

2. Institute of Software at the Chinese Academy of Sciences，Beijing 100190，China）

Abstract： Weapon target assignment is the core link of command and control of naval warship air-defense and anti-missile operations. The quality of the assignment directly affects the final defense effect and survivability of surface ship. Due to the lack of consideration of the uncertainty of interception results and the requirements of multi-round interception， current algorithms is difficult to adapt to the rapidly changed battlefield. A decision-making algorithm for dynamic weapon target allocation based on stochastic dynamic programming is designed. Through base conversion encoding and calculation of the change of target state and weapon state， the sequential optimal assignment scheme is generated by using the backward iterative algorithm based on battlefield situation transition probability. Meanwhile， the decision-making problems “who will fight”“how much” and “when to fight” are also answered by the dynamic weapon target assignment algorithm. The example verification and numerical simulation show that compared with the static algorithm， using this algorithm can reduce the threat expectation of the incoming target by up to 72%.

Key words：" naval warship； air-defense operation； dynamic weapon target assignment； stochastic dynamic programming