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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

1.1WTA問題描述

設(shè)A，B方進(jìn)行攻防對抗，A為紅方，有N個(gè)單位，B為藍(lán)方，有M個(gè)單位，則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，行動(dòng)規(guī)劃共有K步。行動(dòng)步驟為k=0，1，…，K，各步可用作戰(zhàn)單位數(shù)為N（k），M（k），設(shè)在決策中每一步都有評價(jià)函數(shù)，紅方為JA（x（k），y（k）），藍(lán)方為JB（x（k），y（k）），其中：

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

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

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

1.2WTA問題的Nash均衡解

設(shè)在評價(jià)函數(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時(shí)，雙方策略為納什均衡策略對。

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

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

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

則，納什策略對滿足：

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

1.3一種Epsilon-Nash均衡策略

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

雙矩陣博弈：

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

如式（8）所描述的納什策略可以抽象為尋找雙矩陣博弈問題的納什均衡點(diǎn)，非合作非零和雙矩陣博弈Γ=〈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-納什均衡存在定理）：

一個(gè)n×m非負(fù)正規(guī)化非合作雙矩陣對策Γ=〈A，B〉中，設(shè)為所有行（列）玩家所有納什均衡決策中支付最小者，且設(shè)λ=max，則必存在線性時(shí)間可求得的（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）屬于動(dòng)態(tài)變化的量，所以多步預(yù)測是極復(fù)雜的問題。為簡化計(jì)，可以用鐘擺交替搜索法。首先假設(shè)藍(lán)方兩步的步驟是{y（k），y（k+1）}0，相應(yīng)地算出對應(yīng)的策略{x（k），x（k+1）}0，然后再根據(jù)此策略計(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策略評價(jià)

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

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

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

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

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

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

2 實(shí)驗(yàn)驗(yàn)證

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

表1 仿真實(shí)驗(yàn)結(jié)果

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

3 結(jié)論

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

［1］劉傳波，邱志明，吳玲，等.動(dòng)態(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］周全，劉娟.基于動(dòng)態(tài)武器目標(biāo)分配的建模［J］.四川兵工學(xué)報(bào)，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é)基金資助項(xiàng)目（20131789004）

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