面向防空作戰(zhàn)的多級動態(tài)目標分配方法

吳洪坤

(江蘇自動化研究所,江蘇 連云港 222061)

現(xiàn)代局部熱戰(zhàn)中,空襲和防空對抗相當程度上影響著戰(zhàn)爭的進程和勝負。防空系統(tǒng)在面臨大規(guī)模梯次配置的空襲編隊時,必須充分利用各火力單元的彈藥資源,盡可能攔截更多更重要的目標,以實現(xiàn)作戰(zhàn)效能最大化,在此過程中,武器-目標分配是指揮控制決策的關鍵環(huán)節(jié)。武器-目標分配(Weapon Target Assignment, WTA)又稱火力分配,是指在一定的條件約束下,根據(jù)作戰(zhàn)目的、武器性能、目標參數(shù)等因素,合理配置武器資源,優(yōu)化火力打擊體系。

從模型研究的角度,根據(jù)是否考慮時間因素,通常分為靜態(tài)武器-目標分配模型(Static Weapon Target Assignment, SWTA)和動態(tài)武器-目標分配模型(Dynamic Weapon Target Assignment, DWTA)。靜態(tài)WTA模型強調(diào)在單個階段內(nèi)一次性求解分配方案,不考慮時間因素,僅將毀傷概率和目標威脅等因素作為優(yōu)化對象,這樣一來雖然可以提高求解效率,但模型過于簡單,實用性受限。動態(tài)WTA模型則將分配過程分成多個階段執(zhí)行,在靜態(tài)模型的基礎上增加考慮時間約束和打擊次序對分配結果的影響,從而使模型更貼近實際,合理性更強,但約束條件增多給求解計算造成困難。

從算法研究的角度,WTA是典型的非線性組合優(yōu)化問題,隨著武器與目標數(shù)量的增加,解空間將呈指數(shù)式擴大,給求解帶來困難。目前主要有兩類求解方法,一類是基于枚舉的精確算法,如窮舉法、隱枚舉法、割平面法、分支定界法等。這類算法精確度高、穩(wěn)定性好,但計算效率偏低,很難用于多約束復雜問題。另一類是基于啟發(fā)式策略的智能優(yōu)化算法,如遺傳算法、粒子群算法、蟻群算法、模擬退火算法等。這類算法可以在不進行全枚舉的情況下搜索到理想的解,但穩(wěn)定性較差,容易出現(xiàn)重復迭代導致收斂慢,或過早收斂卻陷入局部最優(yōu)的情況。

當前針對SWTA的研究較多,針對DWTA的研究較少,并且大多都采用啟發(fā)式算法進行求解,很難滿足實際戰(zhàn)場中實時性和準確性的要求。本文在傳統(tǒng)的多級WTA模型的基礎上進行改進,并結合KM算法對問題進行求解,為防空作戰(zhàn)中的動態(tài)WTA問題給出了一種可行的解決方法。

1 動態(tài)WTA問題建模

1.1 目標函數(shù)

動態(tài)分配問題可視作個階段的靜態(tài)分配問題,每個階段用序號進行區(qū)分。在第個階段,假設有個武器構成武器集合={,,…,},有個目標構成目標集合={,,…,},有目標函數(shù):

(1)

目標函數(shù)中()表示第個階段分配方案的作戰(zhàn)收益值;()∈(0,1)表示第個階段目標的威脅系數(shù);()表示第個階段武器對目標的整體攔截概率;()是布爾量,用于判定武器是否分配給目標,是則()=1,否則()=0;約束條件表示,武器與目標之間采用“一對一”的分配方式。

1.2 時間因素

動態(tài)武器-目標分配中需要考慮的時間因素主要包括武器射擊周期和目標來襲時間。

武器射擊周期是指武器從射擊第一個目標到射擊第二個目標的時間間隔,即=+。服務時間是指武器射擊第一個目標的時間,包括導彈發(fā)射間隔總耗時,攔截導彈從發(fā)射到與目標相遇的飛行時間,即=+。轉火準備時間是指武器轉火射擊第二個目標所需要的準備時間。

目標來襲時間指的是目標飛臨發(fā)射區(qū)遠界的時間和飛臨發(fā)射區(qū)近界的時間。

1.3 資源約束

武器平臺載彈量有限,為了保證打擊效果并且提高資源利用率,本文通過設定攔截概率閾值的方式來約束武器平臺發(fā)射的導彈數(shù)量。

假設武器的載彈量為,第個階段武器對目標發(fā)射()枚導彈,單發(fā)導彈對目標的毀傷概率為(),則對的總體攔截概率:

()=1-[1-()]()

(2)

定義攔截概率閾值(),武器對目標的攔截概率不得低于閾值,即()≥(),從而得到關于()的約束條件:

(3)

的設定取決于的威脅系數(shù),對于威脅系數(shù)高的目標,攔截概率閾值設定的更高,對于<01的目標則不進行攔截。如表1。

表1 威脅系數(shù)與攔截概率閾值對應表

在此約束條加下,若武器的剩余彈藥無法滿足對來襲目標實現(xiàn)高于攔截概率閾值的攔截打擊,則不考慮將分配給。若的彈藥全部用完,則將其從火力單元序列中移出。

1.4 改進多級分配模型

多級分配模型是動態(tài)WTA研究中的常用模型。傳統(tǒng)的多級分配模型通常采用“射擊-觀察-射擊”的模式,每個階段的分配決策以上一階段的交戰(zhàn)結果(來襲目標生存或被擊毀)作為新的初始條件,防御方對未被擊毀的目標進行新一輪的分配,時間窗口圖如圖1所示。圖中白色框表示武器的射擊周期,灰色框表示防空系統(tǒng)等待階段1的交戰(zhàn)結果判定以及進行階段2發(fā)射準備的時間。傳統(tǒng)的多級分配模型中,武器對不同目標的射擊周期不存在重疊。

圖1 傳統(tǒng)多級分配模型時間窗口圖

當來襲目標數(shù)量多且時間緊迫時,防空系統(tǒng)為了等待判定交戰(zhàn)結果往往會耗費許多時間,這在實際作戰(zhàn)中對防御方非常不利。因此,本文對多級分配模型進行改進。區(qū)別于傳統(tǒng)模型中僅有生存和擊毀兩種狀態(tài),改進的多級分配模型將來襲目標分為:未分配、已分配未交戰(zhàn)、已交戰(zhàn)被摧毀和突破攔截等四種狀態(tài)。防空系統(tǒng)不再等待上一階段的交戰(zhàn)結果判定,而是以固定的時間間隔連續(xù)進行分配輪次的求解,此時的時間窗口圖如圖2所示。

圖2 改進多級分配模型時間窗口圖

由于目標數(shù)量過多,防空系統(tǒng)必須命令武器平臺提前準備轉火射擊,以應對新目標。此時武器的射擊周期存在重疊,武器發(fā)射的導彈與上一個目標還未交戰(zhàn)便進行對下一個目標的轉火準備。此時武器若想實現(xiàn)轉火攔截,需要滿足約束條件:

≤+≤

(4)

若+>,則攔截失敗;若+<,則武器轉火準備過于提前,待機過久而浪費時間。

2 動態(tài)WTA問題求解

2.1 KM算法基本原理

KM(Kuhn-Munkras)算法是一種在多項式時間內(nèi)查找有權二部圖最優(yōu)匹配的算法,其在匈牙利算法的基礎上引入了可行頂標以及相等子圖等概念,以實現(xiàn)二部圖最優(yōu)匹配的求解。

將WTA問題用有權二部圖進行刻畫,如圖1所示。=(,,,),武器集合和目標集合是頂點集合,顯然二者互不相交,且集合內(nèi)部元素之間不存在分配關系;是邊集合,與間的連線表示與可能存在的分配關系;是邊權值集合,表示的權值,是判斷是否將分配給的主要依據(jù)。如此一來只要合理設置邊權值就可以將WTA問題轉化為有權二部圖求解最優(yōu)匹配的問題。

圖3 WTA的有權二部圖模型

定義:=(,,,)是有權完備二部圖,設頂點的頂標為,頂點的頂標為,若子圖中的所有邊都滿足+=,則稱為的相等子圖,若存在原圖的完備匹配,則該完備匹配便是原圖的最優(yōu)匹配。

KM算法主要步驟為:

step1:初始化各個頂點的可行頂標值;

step2:找出相等子圖并使用匈牙利算法搜索最大匹配;

step3:判斷最大匹配是否為原圖的完備匹配,若是則該匹配便是所求的最優(yōu)匹配,若不是則修改可行頂標值。

step4:重復step2～3直至找到最優(yōu)匹配。

2.2 剩余彈藥資源判定系數(shù)

約束條件規(guī)定武器的剩余彈藥對來襲目標的總體攔截概率要高于閾值。如果要在分配計算之前遍歷所有武器,判斷其剩余彈藥量是否滿足要求,顯然會增加求解耗時。因此本文定義判定剩余彈藥資源的系數(shù):

=[1-(1-)-]+1

(5)

式中方括號表示取整函數(shù),表示武器的剩余導彈枚數(shù)。當武器剩余彈藥量對目標的總體攔截概率大于時,=1;小于時,=0。

2.3 目標威脅系數(shù)vj的變化

隨著時間和分配輪次的推移,系統(tǒng)會接收到數(shù)個階段以前的交戰(zhàn)結果,在此過程中目標的威脅會發(fā)生變化。

當目標未被分配時,威脅系數(shù)不變;

當目標已被分配未交戰(zhàn)時,認為目標的威脅系數(shù)降低,本文中用公式(6)來計算:

(+1)=()×[1-()]

(6)

當目標已被分配已交戰(zhàn)且目標被摧毀,則將其威脅系數(shù)置0;

當目標已被分配已交戰(zhàn)但目標突破攔截,則重置其威脅系數(shù)并再次加入分配輪次。

2.4 匹配度ωij

匹配度也是有權二部圖的邊權值,邊權值的加和是KM算法求解依據(jù),為了契合目標函數(shù)與分配模型,定義:

=×(×)

(7)

定義匹配度矩陣=[]×,用來統(tǒng)一表示武器對應目標的匹配度,如圖4。

圖4 匹配度矩陣Ω

將匹配度矩陣代入KM算法進行求解即可求得目標分配結果。

每個階段目標分配結果求出之后,若武器對目標的單發(fā)射擊攔截概率滿足大于等于攔截概率閾值則輸出攻擊次數(shù)()=1,若不滿足,則根據(jù)式(3)計算()的值并輸出。然后根據(jù)()和()求出(),并代入目標函數(shù)中得到分配方案的作戰(zhàn)收益值。

3 仿真實驗與分析

為驗證算法和模型的有效性,分別設置靜態(tài)WTA和動態(tài)WTA仿真示例進行實驗分析。實驗環(huán)境為Windows10系統(tǒng)、i7-9750H處理器、16G運行內(nèi)存。

3.1 靜態(tài)分配實驗

設置武器與目標的數(shù)量為10×10,由于是靜態(tài)分配實驗,所以只有一個分配階段且僅考慮目標威脅系數(shù)和武器對目標的攔截概率,具體參數(shù)如表2所示。

表2 攔截概率與威脅系數(shù)

令=×,代入KM算法進行求解,實驗結果如表格3所示。分配求解過程耗時不到0001 s,分配方案總收益值=5900 4,經(jīng)過分支定界法驗算可知所求結果是最優(yōu)解。

表3 靜態(tài)分配實驗結果

同樣在10×10規(guī)模的WTA問題中,將KM算法分支定界法(B&B)、遺傳算法(GA)和粒子群算法(PSO)進行對比,每種算法都進行50次重復實驗,對比結果如表4所示。

表4 算法性能對比

從實驗結果可知,分支定界法和KM算法作為精確解法,可以穩(wěn)定求得最優(yōu)解,但KM算法搜索增廣路徑的速度遠遠快于分支定界法搜索根節(jié)點的速度。遺傳算法和粒子群算法雖然在計算效率上優(yōu)于枚舉類算法,但求解效果不太穩(wěn)定,容易陷入局部最優(yōu)。

現(xiàn)代空襲目標飛行高度低、速度快、暴露時間較短,留給指控系統(tǒng)分配決策模塊的時間往往以毫秒計算。與其他3種算法相比,KM算法的精度和速度都具有明顯優(yōu)勢,能夠更好地適應改進后多級動態(tài)WTA模型的實時性和準確性要求。

3.2 動態(tài)分配實驗

假設我方防空陣地有5臺地空導彈武器,敵方共有20個目標分批次來襲。武器與目標的相關參數(shù)見表5和表6。

表5 攔截概率與威脅系數(shù)

表6 目標來襲時間

由于KM算法對于低維度WTA問題的求解耗時幾乎可以忽略不計,所以我方防空系統(tǒng)目標分配輪次刷新間隔較短,假設為1 s。武器平臺～的轉火準備時間分別為:1 s、1 s、2 s、2 s、3 s。

具體的分配求解過程如下:

第0階段:時刻0 s,此時防空發(fā)射區(qū)沒有目標,不進行分配計算。

第1階段:時刻5 s,飛入發(fā)射區(qū),分配攔截。

第2階段:時刻6 s,與飛入發(fā)射區(qū),此時未完成轉火準備,分配攔截,攔截。

第3階段:時刻7 s,與飛入發(fā)射區(qū),此時、、未完成轉火準備,分配攔截,攔截。

第4階段:時刻8 s,與飛入發(fā)射區(qū),此時未完成轉火準備,分配攔截,攔截。

……

直到第11階段,完成對所有目標的分配，具體見表7。

表7 動態(tài)分配實驗結果

根據(jù)實驗結果可知,改進后的多級動態(tài)分配模型由于不用等待結果判定,可以在有限時間內(nèi)執(zhí)行更多的分配輪次,即使面對數(shù)倍于己的來襲目標,也可以高效地進行分配求解。

4 結束語

本文以防空作戰(zhàn)WTA為背景,嘗試對傳統(tǒng)的多級分配模型進行改進,通過設定可疊加的武器射擊周期,并以固定頻率刷新分配求解輪次的方式,使得改進后的模型可以用于目標較多且時間緊迫的作戰(zhàn)場景,為解決動態(tài)WTA問題給出了一種可行的方案。在算法求解過程中,采用KM算法以滿足改進后多級分配模型對算法的實時性和準確性要求。但實際作戰(zhàn)中需要考慮的因素還有很多,后續(xù)仍需要進一步對模型進行細化和改進。