基于Epsilon-Nash策略的動態(tài)武器-目標(biāo)分配方法*

王邑，孫金標(biāo)，華玉光，王繼輝

（空軍指揮學(xué)院，北京100097）

基于Epsilon-Nash策略的動態(tài)武器-目標(biāo)分配方法*

王邑，孫金標(biāo)，華玉光，王繼輝

（空軍指揮學(xué)院，北京100097）

在大型任務(wù)規(guī)劃軟件的作戰(zhàn)單元任務(wù)分配中，搜索零和博弈問題的納什均衡點是求解任務(wù)分配的一種有效的方法。然而，納什均衡點在決策中并不一定總是存在且唯一，這造成了納什均衡策略在實際使用時具有較大的局限。通過采用Epsilon-Nash策略克服這種局限，并將其應(yīng)用于自主空戰(zhàn)任務(wù)規(guī)劃系統(tǒng)中，通過仿真實驗，證實Epsilon-Nash策略具有近似于納什策略的效果。

戰(zhàn)術(shù)決策，武器-目標(biāo)分配，Epsilon-Nash，博弈論

0 引言

動態(tài)武器-目標(biāo)分配問題（Dynamic Weapon-Target Assignment，WTA）是戰(zhàn)場指揮決策中的關(guān)鍵問題［1］。對該問題的求解，是很多武器任務(wù)規(guī)劃軟件的核心功能。

以博弈論為基礎(chǔ)的作戰(zhàn)指揮控制理論在戰(zhàn)場指揮決策中得到了廣泛的應(yīng)用。在敵我雙方具有一定情報信息理解的前提下，通過構(gòu)造對策矩陣，尋找博弈均衡點，來搜尋作戰(zhàn)收益最高的分配方案，是解決武器-目標(biāo)分配問題的可行的方法。

博弈論中最常討論研究的博弈均衡為納什均衡（Nash Equilibirum），采用納什均衡解決任務(wù)規(guī)劃問題的時候，必須保證決策矩陣都有全局唯一的納什均衡點。這種決策矩陣博弈對策中存在且唯一的納什均衡點稱之為純納什均衡點，而據(jù)文獻(xiàn)［2］，大多數(shù)非零和博弈對策矩陣不存在純納什均衡點，因此，在實踐中，必須考慮納什均衡點非唯一或不存在的情形。在理論探討中，通常采用混合策略（Mixed Strategy）［3］，簡化決策矩陣［4］等方法來進(jìn)行無純納什均衡點矩陣的決策。

影響納什均衡策略在動態(tài)武器［6］-目標(biāo)分配問題中的使用問題，除了純納什均衡點可能不存在這個理論問題之外，還有搜索納什均衡點本身的效率問題。經(jīng)過科學(xué)論證，搜索納什均衡點、判斷純納什均衡點數(shù)量的計算復(fù)雜度都是PPAD-Complete難度，而若對策矩陣中出現(xiàn)元素缺失或不確定的情況，隨之產(chǎn)生的納什均衡點非唯一或不存在使情況更加復(fù)雜，除此以外，搜索混合納什均衡點、簡化決策矩陣等工作涉及也都是PPAD-Complete難度的計算，因此，在實踐中，基本上沒有討論戰(zhàn)役規(guī)模決策矩陣的相關(guān)論述，而大多是圍繞小規(guī)模2對2空戰(zhàn)等簡單對策中討論納什均衡的求解。

綜上所述，若有方法能夠克服納什均衡點數(shù)量的問題，且能夠快速有效地計算得到接近納什均衡的結(jié)果，那將是非常實用的。

本文將Epsilon-Nash策略引入解決純納什均衡不存在時的局部最優(yōu)化問題，使用經(jīng)過線性時間就可計算出的Epsilon-Nash均衡點來代替納什均衡點，得到純納什均衡的近似解，大大地提高了問題的求解效率，并拓寬了博弈論方法在WTA問題中的運(yùn)用范圍。通過蒙特卡洛仿真，與全信息最優(yōu)策略，和無信息最優(yōu)策略進(jìn)行效用對比來分析方法的使用效果。通過實驗表明，Epsilon-Nash策略能夠接近于純納什均衡所產(chǎn)生的效能。

1 基于Epsilon-Nash的武器-目標(biāo)分配

1.1WTA問題描述

設(shè)A，B方進(jìn)行攻防對抗，A為紅方，有N個單位，B為藍(lán)方，有M個單位，則A={1，2，…，n}，B= {1，2，…，m}，設(shè)Pij表示A組第i單位攻擊B組第j目標(biāo)的擊毀概率，對應(yīng)的存活概率是qij=1-Pij，則目標(biāo)j遭受多目標(biāo)攻擊后的存活概率為：

其中，xij為A組第i單位攻擊B組第j目標(biāo)的武器數(shù)。則xij的約束條件為：

設(shè)紅方為A，藍(lán)方為B，行動規(guī)劃共有K步。行動步驟為k=0，1，…，K，各步可用作戰(zhàn)單位數(shù)為N（k），M（k），設(shè)在決策中每一步都有評價函數(shù)，紅方為JA（x（k），y（k）），藍(lán)方為JB（x（k），y（k）），其中：

分別是NA（k），MB（k）維向量，表示紅藍(lán)雙方每個作戰(zhàn)單元第k步的目標(biāo)分配策略。

設(shè)第k步時，紅方第i作戰(zhàn)單元打擊藍(lán)方第j作戰(zhàn)單元的毀傷概率為，對應(yīng)的藍(lán)方第j作戰(zhàn)單元打擊紅方第i作戰(zhàn)單元的毀傷概率為，設(shè)分別是第k步起始時紅方第i作戰(zhàn)單元和藍(lán)方第j作戰(zhàn)單元的生存概率，則生存概率的計算式為：

每個作戰(zhàn)單元的價值不同，設(shè)Wx（i）表示紅方第i個作戰(zhàn)單元對紅方的價值，Wy（i）表示該作戰(zhàn)單元對藍(lán)方的價值。設(shè)Wy（j）表示藍(lán)方第j個作戰(zhàn)單元對藍(lán)方的價值，Wx（j）表示該單元對紅方的價值。相應(yīng)地，紅藍(lán)雙方的策略評價函數(shù)可以寫為：

1.2WTA問題的Nash均衡解

設(shè)在評價函數(shù)JA下，對B方策略y，A方的最優(yōu)策略x*，定義為：

對于B方給定的策略y，A方由最優(yōu)策略x*變?yōu)槠渌呗詘，造成的損失（又稱悔值regret）為：

對稱地，對A方策略x，B方由最優(yōu)策略y*變?yōu)槠渌呗詙，造成的損失為：

Dx（x，y），Dy（x，y）嚴(yán)格非負(fù)。

當(dāng)Dx（x，y）=Dy（x，y）=0時，雙方策略為納什均衡策略對。

定義（WTA問題的納什均衡策略）：

稱uA，uB納什策略對，當(dāng)且僅當(dāng)：

若定義雙方的累積損失為：

則，納什策略對滿足：

將式（7）～式（9）給出的納什策略對條件帶入式（3），得到許多步規(guī)劃以下目標(biāo)函數(shù)：

1.3一種Epsilon-Nash均衡策略

由于動態(tài)武器-目標(biāo)分配問題的每一步都是NP難優(yōu)化問題，故式（10）沒有解析解，雖然可以對模型進(jìn)行適當(dāng)簡化，使其符合雙矩陣博弈的基本形式，但搜索其Nash均衡解的復(fù)雜度仍然是PPAD-Complete難度，且如前所述，純納什策略的存在性和唯一性無法保證，因此，需要引入Epsilon-Nash均衡策略作為納什均衡策略的替代。

雙矩陣博弈：

博弈空間G=（V，E）中，博弈方i∈V有mi個純決策方案，j∈V有mj個純決策方案，則：雙矩陣博弈規(guī)模mi×mj，〈A（i×j），A（j×i）〉，對所有（i，j）∈E，i方的支付函數(shù)（即決策收益）為所有博弈分支付的總和：

如式（8）所描述的納什策略可以抽象為尋找雙矩陣博弈問題的納什均衡點，非合作非零和雙矩陣博弈Γ=〈A，B〉，策略對（x*，y*）為納什均衡，當(dāng)且僅當(dāng)，

①對行博弈方（row player）任意混合策略x，xTAy*≤x*TAy*且，

②對列博弈方（column player）任意混合策略y，x*TBy*≤x*TBy*，

定義（Epsilon-Nash策略）：

②對列博弈方（column player）任意混合策略y，，

引理［5］（（2+λ）/4-納什均衡存在定理）：

一個n×m非負(fù)正規(guī)化非合作雙矩陣對策Γ=〈A，B〉中，設(shè)為所有行（列）玩家所有納什均衡決策中支付最小者，且設(shè)λ=max，則必存在線性時間可求得的（2+λ）/4-納什均衡策略。

（2+λ）/4-納什均衡求解方法：

設(shè)如下線性規(guī)劃問題：

線性規(guī)劃1：

線性規(guī)劃2：

設(shè)t*，y*，s*，x*分別是線性規(guī)劃1和2最優(yōu)解，則存在至少一行r∈［1，n］，滿足，一列c∈［1，m］使。即最優(yōu)解的行號和列號分別是r，c。

1.4鐘擺搜索Epsilon-Nash策略

由于對抗雙方控制變量x（k），y（k）屬于動態(tài)變化的量，所以多步預(yù)測是極復(fù)雜的問題。為簡化計，可以用鐘擺交替搜索法。首先假設(shè)藍(lán)方兩步的步驟是{y（k），y（k+1）}0，相應(yīng)地算出對應(yīng)的策略{x（k），x（k+1）}0，然后再根據(jù)此策略計算藍(lán)方的響應(yīng)策略{y（k），y（k+1）}1以此類推。結(jié)束終止條件為：

其中r≥1，當(dāng)搜索結(jié)束，選取在其中滿足線性規(guī)劃式（12）、式（13）的量，即可構(gòu)造Epsilon-Nash決策輸出。

1.5Epsilon-Nash策略評價

為驗證Epsilon-Nash策略目標(biāo)分配方法的實際效果，定義兩種其他策略作為參考策略。即，全信息最優(yōu)策略和無信息最優(yōu)策略。

定義（全信息最優(yōu)策略）：

紅方全信息最優(yōu)策略{x*（k），x*（k+1）}∈XA*（k）為在給定藍(lán)方作戰(zhàn)單位y（k）條件下，在后推步長d=1時，滿足如下不等式：

全信息最優(yōu)策略是在完全知曉對方策略的前提下得到的，且僅知道當(dāng)前時刻對方的策略，其策略的目標(biāo)函數(shù)可以在下一個運(yùn)算周期內(nèi)進(jìn)行推測。

定義（無信息最優(yōu)策略）：

無信息最優(yōu)策略x（ok），在k步驟時，，任一方的決策滿足己方獲益最大，即，藍(lán)方以此類推。無信息最優(yōu)策略即完全忽略對方策略而產(chǎn)生的一種策略。

2 實驗驗證

為驗證Epsilon-Nash策略在動態(tài)武器-目標(biāo)分配問題中的效用，進(jìn)行了紅藍(lán)雙方各10個目標(biāo)的蒙特卡洛仿真。假設(shè)紅藍(lán)雙方的作戰(zhàn)單元價值相同，每次仿真生成新的隨機(jī)決策矩陣，首先假定了兩個16×16矩陣，分別是紅方對藍(lán)方以及藍(lán)方對紅方的殺傷概率，取值服從［0，0.5］區(qū)間上的正態(tài)分布。策略評價函數(shù)與式（3）相同，作戰(zhàn)單元價值服從［0，1］區(qū)間上的正態(tài)分布，且對稱構(gòu)造，即。然后連續(xù)執(zhí)行3輪攻擊，即雙方進(jìn)行決策—攻擊3次。統(tǒng)計3輪攻擊后雙方的存活作戰(zhàn)單元價值總和，數(shù)值大者勝利，然后重置仿真參數(shù)，進(jìn)入下一局。每種配置執(zhí)行10 000局仿真。實驗1中，紅藍(lán)方均采用Epsilon-Nash策略進(jìn)行對抗；實驗2中，紅方采用Epsilon-Nash策略，藍(lán)方采用全信息最優(yōu)策略；實驗3中，紅方采用Epsilon策略，藍(lán)方采用無信息最優(yōu)策略。實驗的評價指標(biāo)為勝利率，即勝利局?jǐn)?shù)占總局?jǐn)?shù)的百分比，仿真的結(jié)果如表1所示：

表1 仿真實驗結(jié)果

從表1中可以看出，實驗1的結(jié)果與實驗2的結(jié)果更為近似，采用Epsilon-Nash策略的總體效果與敵方采用Epsilon-Nash的效果相同，優(yōu)于無信息最優(yōu)分配策略，低于全信息最優(yōu)策略。實踐中，當(dāng)納什均衡存在時，一方選擇納什均衡而另一方選擇全信息最優(yōu)策略，其結(jié)果應(yīng)該與雙方均選取納什均衡策略結(jié)果一致，故，Epsilon-Nash策略在對抗全信息最優(yōu)策略時，其效果為相當(dāng)或略低于全信息最優(yōu)策略。而Epsilon-Nash策略對抗無信息最優(yōu)策略，則顯現(xiàn)出較大的優(yōu)勢。這表明，Epsilon-Nash策略產(chǎn)生的結(jié)果非常近似于納什策略，且比納什策略的求解范圍更大。

3 結(jié)論

本文采用了一種Epsilon-Nash策略來克服納什均衡點不存在或不唯一時的動態(tài)武器-目標(biāo)規(guī)劃問題，采用蒙特卡洛法和隨機(jī)矩陣，通過實驗驗證了Epsilon-Nash策略相對全信息和無信息最優(yōu)策略的效能。通過試驗表明了Epsilon-Nash策略近似于納什策略，可作為無全局納什點動態(tài)武器-目標(biāo)分配問題的解法策略。

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

［2］BRANDT F，F(xiàn)ISCHER F，HOLZER M.Symmetries and the complexity of pure Nash equilibrium［J］.Journal of Computer and System Sciences，2009，75（3）：163-177.

［3］RENY P J.On the existence of pure and mixed strategy Nash equilibriaindiscontinuousgames［J］.Econometrica，1999，67（5）：1029-1056.

［4］KNUTH D E，PAPADIMITRIOU C H，TSITSIKLIS J N.A note on strategy elimination in bimatrix games［J］.Operations Research Letters，1988，7（3）：103-107.

［5］KONTOGIANNIS S C，PANAGOPOULOU P N，SPIRAKIS P G.Polynomial algorithms for approximating nash equilibria of bimatrix games［M］.Berlin：Springer Berlin Heidelberg，2006：286-296.

［6］周全，劉娟.基于動態(tài)武器目標(biāo)分配的建模［J］.四川兵工學(xué)報，2010，31（9）：14-15.

Research of Dynamic Weapon-Target Assignment Problem Based on Epsilon-Nash Equlibirum

WANG Yi，SUN Jin-biao，HUA Yu-guang，WANG Ji-hui
（Air Force Command College，Beijing 100097，China）

In large scale mission planning software，the mission assignment of asset can be effctive when searching nash equilibria in non-cooperative non zero sum game problem.However，the pure nash equlibrium is not always exist and single，in which case limit the use of nash strategy in Weapon-Target assignment.A Epsilon-Nash Equlibirum method to overcome the limitation is proposed.Apply it in a air combat mission planning system，through simulation test，the epsilon-nash strategy can be as effective as pure nash strategy.

tactical decision，weapon-target assignment，epsilon-nash，game theory

TP391.9

A

1002-0640（2016）11-0012-04

2015-10-12

2015-11-17

航空科學(xué)基金資助項目（20131789004）

王邑（1984-），男，四川成都人，博士，工程師。研究方向：計算智能、空軍合同戰(zhàn)術(shù)模擬。