基于SDP的動態武器目標分配決策算法研究

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

關鍵詞：水面艦艇； 防空作戰； 動態武器目標分配； 隨機動態規劃

中圖分類號：TJ760

文獻標識碼： A

文章編號：1673-5048（2023）05-0050-07

DOI： 10.12132/ISSN.1673-5048.2023.0093

0 引" 言

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

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

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

算法，通過轉移概率刻畫攔截過程的動態變化。但是，算法對目標來襲間隔、武器射擊時刻等有較為嚴苛的假設，因此適用場景較為有限。

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

2.2 基于SDP的動態WTA決策算法設計

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

基于戰場狀態轉移概率矩陣，基于隨機動態規劃理論，采用逆向迭代算法［15-16］，從末次攔截開始求解面向s次攔截的分配方案最優策略，算法流程見圖5。

該算法的時間復雜度為O（2（m+n）·mn·s），每次攔截分配方案的可選擇性和攔截結果的不確定性是導致時間復雜度提升的最主要原因； 空間復雜度為O（4m+n·mn），主要用于存儲狀態轉移矩陣。

3 動態WTA決策算法分析

3.1 基本算例

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

“盡早攔截、盡遠攔截”的作戰原則要求，應當在第1次攔截機會時就使用所有艦空導彈，在該原則下最優分配方案即是靜態WTA決策代表的最優決策，即圖中分配方案U2。但是根據動態WTA決策計算顯示，當敵方采用不同殺傷能力的反艦導彈搭配協同進攻的作戰樣式時，我方應該預留部分艦空導彈，針對可能在第1次攔截時突防的高殺傷目標進行二次攔截，從而達到更好的攔截效果。此時，動態WTA決策算法就能夠量化地解決資源應該在哪次攔截時使用，應該用多少艦空導彈打擊哪個目標等目標分配決策問題。

3.2 動態與靜態WTA決策算法對比

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

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

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

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

綜上所述，使用動態WTA算法的攔截效能顯著優于靜態WTA算法。根據數值仿真反映的規律，在防空反導作戰過程中，當艦空導彈數量多于目標數量時，使用動態WTA算法能夠獲得更好的攔截效能； 當艦空導彈數量少于目標數量時，使用動態WTA算法能夠更好地降低目標剩余威脅。同時，如果能夠盡可能增加攔截次數，則動態WTA算法能夠更好地提升水面艦艇的生存能力。

4 結" 論

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

參考文獻：

［1］ 李勇君，" 黃卓，" 郭波. 武器-目標分配問題綜述［J］. 兵工自動化， 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］ 劉傳波， 邱志明， 吳玲， 等. 動態武器目標分配問題的研究現狀與展望［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］. 火力與指揮控制， 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］ 徐加強， 畢義明， 汪民樂， 等. 基于時空約束的常規導彈火力分配建模與實現［J］. 系統工程與電子技術， 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］ 唐蘇妍， 梅珊， 朱一凡， 等. 基于擴展合同網協議的分布式武器目標分配方法［J］. 系統工程與電子技術， 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］ 孟慶操， 楊光. 航母編隊防空作戰效能評估指標體系構建［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］ 韓松臣， 秦俊奇， 韓品堯， 等. 馬爾可夫決策過程在目標分配中的應用［J］. 哈爾濱工業大學學報， 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］ 蔡懷平， 劉靖旭， 陳英武. 動態武器目標分配問題的馬爾可夫性［J］. 國防科技大學學報， 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］ 馬其東， 周俊， 樊繼功. 艦空導彈武器系統轉火射擊能力研究［J］. 現代防御技術， 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，Fan 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