基于偏好聯盟博弈的導彈集群分布式任務分配模型

張 贇，邱忠宇，蔡云澤

（1.上海交通大學自動化系，上海 200240；2.上海機電工程研究所，上海 201109）

0 引言

在導彈實現集群智能作戰的關鍵技術中，協同決策系統是重中之重，其主要功能是負責導彈集群的任務分配。任務分配的目標可以概括為：在當前態勢環境下，對我方資源進行調配以實現我方效益的最大化。

大量研究成果針對不同場景提出了各種任務分配模型和算法，這些方法按照架構主要分為集中式和分布式。隨著作戰集群規模的不斷擴大，集中式算法漸漸不再適應任務分配的需求。相對于集中式算法，分布式算法賦予了各智能體一定的自主性和決策能力，因此具有更適應大規模集群、魯棒性更好、響應迅速等優勢。

目前分布式任務分配算法主要有基于市場機制的方法［1］、分布式馬爾可夫決策過程方法［2］和博弈論方法。基于市場機制的方法主要有合同網方法和拍賣算法，合同網［3］包含發布者和競標者，并將分配過程分為招標、投標、中標、確認4 個階段；拍賣算法［4］以競價的方法將任務分配給出價最高者，使得全體競價者的滿意值最高，經典的拍賣分配算法有一致性包算法（consensus-based bundle algorithm，CBBA）［5］?；诜植际今R爾可夫法是基于分布式馬爾可夫過程模型的分配算法［6］，通常使用強化學習進行訓練得到最優分配解，這種方法適用于動態復雜的場景下的分配，但訓練難度較大、收斂較慢。

運用博弈論解決分布式任務分配問題時，鑒于博弈參與者只關注自身利益最大化，而無需關注全局利益，通過一定的頂層設計可使得全局利益與局部利益一致，這意味著智能體自身不需要復雜的決策系統，不需要關注過多全局信息。

聯盟形成博弈（coalition formation game，CFG）模型是一種常用的博弈模型，屬于合作博弈模型的范疇。在博弈過程中參與者會自行組成若干個聯盟，從全局來看即形成了若干分組。在此基礎上，偏好聯盟博弈（hedonic coalition game，HCG）模型中的參與者會選擇自己最喜好的聯盟加入。HCG 模型被越來越多地應用于多種場景下的分布式優化問題中，包括無線通信網絡［7］、認知網絡［8］、無人機［9］等場景中的資源調配、安全傳輸［10］、任務分配［11］等問題。

本文基于偏好聯盟博弈模型，設計了空空導彈集群攻擊場景下的分布式任務分配模型，并針對該模型選擇空間自適應學習（spatial adaptive play，SAP）算法進行求解，通過仿真實驗驗證了設計模型和算法的有效性，并取得了較好的優化結果和收斂效率。本文貢獻主要有兩點：1）基于HCG 模型建立了含約束的分布式任務分配模型；2）針對SAP 算法收斂效率較低、易于陷入局部最優的局限對其進行了改進。

1 基本分配模型

1.1 彈目相對運動模型

在建立多對多任務分配模型之前，需要先建立一對一的空戰模型［12］。本文所考慮的模型是在二維平面內，不考慮導彈和目標具體形狀的影響，即將導彈和目標當作質點處理，導彈與目標速度均為常值，且導彈速度遠大于目標。

圖1展示的是本文所使用的導彈與目標相對運動模型。 其中：M 表示導彈；T 表示目標；分別表示導彈和目標的位置、速度、加速度和航向角；R為彈目距離；λ表示彈目視線角。

圖1 導彈與目標相對運動模型Fig.1 Relative motion model of missile and target

建立導彈與目標的運動方程如下：

令vR、vλ分別表示彈目相對速度平行于和垂直于視線角方向的分量，vR表示彈目相對接近速度，則彈目相對運動方程為

1.2 攻擊成本

攻擊成本考慮兩個因素，剩余攻擊時間和預計消耗能量。其中剩余攻擊時間采用文獻［13］中的方法，將目標狀態投影到彈目視線方向，將目標轉化為相對靜止狀態的思想，實現對機動目標的剩余攻擊時間估計。

針對機動目標，采用虛擬目標的思路，將vT和aT對彈目相對運動的影響均投影到彈目視線角方向上，并修正由目標機動引起的航向角和視線角變化，將目標轉化為相對靜止狀態。修正后的剩余攻擊時間估計為

估計預計消耗能量的方法是在預計剩余攻擊時間的基礎上，借鑒文獻［14］的方法，基于最優控制原理設計，使得導彈機動最小化的最優制導律為

由此可計算導彈i攻擊目標j的預計消耗能量指標為

式中：w1和w2為權重。

1.3 任務分配模型

假設我方有nM枚導彈，其集合表示為M：={M1，M2，…，MnM}；戰場上有nT個目標需要攻擊，其集合表示為T：={T0，T1，…，TnT}，其中T0表示空目標。本文只考慮導彈數量不少于目標數量，即nM≥nT的情況。

設Ai?T表示第i枚導彈的可選目標集。特別地，引入T0∈Ai(i=1，…，nM)，表示所有導彈總是可以選擇不攻擊任何目標。導彈i從自己的目標集Ai中選出目標ai，則向量組a=(a1，a2，…，anM)組成了一個分配解。設，其中Sj表示分配解a下選擇目標j的導彈集合，sj表示Sj中的導彈個數，即sj=|。

將全局目標函數定義為攻擊所有目標可得收益之和，可建立任務分配模型如下：

2 面向任務分配的偏好聯盟博弈模型

2.1 偏好聯盟博弈模型

在HCG 模型［15］中，任務分配問題被看作是聯盟劃分問題，定義聯盟劃分為一個集合Π={S0，S1，…，SnT}，Sj(j=1，…，nT)的定義與1.3 節相同，特別地，引入新的集合S0，代表沒有選擇任何任務的導彈集合。由于每枚導彈只能選擇一個任務，因此，這里M為1.3 節中定義的導彈集合。為了后續論述方便，用Π(i)表示導彈Mi選擇的目標編號，用SΠ()i表示導彈Mi所屬的聯盟集合，即。

對于每個導彈Mi，將二元組x=(Tj，p)稱為一組聯盟對，意味著“導彈Mi將與p個隊友一起執行任務Tj”。在所有聯盟對上定義一個關于效用的偏序關系?i，對任意x1，x2∈X，x1?i x2意味著導彈Mi對聯盟對x1偏好。

HCG模型G=(M，T，?i)是由導彈集合、任務集合和導彈的偏好關系組成的博弈模型。在HCG 模型框架下解決任務分配問題，實質上是將選擇相同目標的導彈視為一個聯盟，導彈可根據自己的偏好選擇加入某個聯盟。當模型獲得納什均衡狀態時即可得到分配結果，HCG 模型的納什均衡狀態下的聯盟劃分Π*滿足對于任何導彈Mi有

2.2 導彈效用函數

在設計模型時，設計效用函數Ui(Tj，p)表示導彈的聯盟偏好關系，p表示聯盟成員數量。該效用函數與目標和聯盟成員數有關，且導彈偏好的聯盟具有更大的效用。

為了保證HCG 模型的納什均衡狀態的存在性，由文獻［16］的結論可知，當導彈效用函數滿足關于聯盟成員數遞減，即

HCG 模型的納什均衡狀態一定存在。根據此性質，設計導彈效用函數為

式中：r(Tj，|Sj|)為導彈和聯盟成員一起攻擊目標Tj可獲得的回報，并假設聯盟所有成員平分任務回報。在空戰場景中，攻擊同一個目標的導彈數量越多，擊中目標的概率越大。但當數量超過一定界限時，再增加導彈數量對于攻擊目標所起的作用很小，即隨著聯盟成員的數量增加，導彈所得到的邊際回報在遞減。因此可定義任務回報函數r(Tj，|Sj|)為

在本文的HCG 模型的場景中，需要限定得到的聯盟劃分滿足約束條件式（9）。由于本節定義的導彈效用函數與聯盟成員數有關，而約束條件也是對于執行同一任務的導彈個數的限定，因此可以直接對導彈效用函數進行進一步改進，使得導彈在加入一個聯盟時，會考慮到加入該聯盟后該聯盟成員數是否仍滿足約束條件。如果加入該聯盟后約束條件不再滿足，則導彈不會選擇加入該聯盟。具體來說，設計最終的導彈效用函數為

當導彈即將選擇加入的聯盟已經達到約束邊界時，若導彈加入，則得到的效用將會是0，因此導彈最終不會選擇再加入該聯盟，從而保證了求解的可行性。

2.3 模型性能分析

2.3.1 收斂性分析

若將HCG 模型G下的導彈效用函數設計成如式（15）所示的形式，可以得到G收斂到一個納什均衡劃分的迭代次數上界。從只包含1枚導彈的模型開始，逐一在模型中增加導彈并且找到新模型的納什均衡劃分。當1枚新的導彈加入1個已得到納什均衡劃分的k個導彈模型時，至多會造成原有的所有導彈都改變策略，即總計（k+1）次策略改變，新的模型就可以獲得新的納什均衡劃分。因此，對于含有nM個導彈的模型，要獲得其納什均衡劃分，至多需要的迭代次數為

2.3.2 均衡性能分析

選擇無秩序代價（price of anarchy，PoA）作為衡量納什均衡性能的指標。設純納什均衡分配解為a*，全局最優分配解為aopt，則PoA 的定義為全局最優效用和納什均衡效用之比的上界，即

由PoA 的定義可知，PoA 越大，代表最差情況下納什均衡效用越小，即意味著HCG 模型的性能越差。關于本文建立的HCG 模型，我們可以用以下命題得到該模型PoA 的上界，從而保證了HCG 模型性能的下界。

命題1（HCG 模型PoA 上界）根據式（15）設計的導彈效用函數建立的HCG 模型G，且令εj=ε>1 和，則該HCG模型的PoA滿足

式中：

在可行解范圍內，根據任務回報函數r(Tj，|Sj|)單調遞增的性質，結合全局效用函數為任務回報函數之和的定義，對全局效用函數有

將全局最優劃分Πopt和納什均衡劃分Π*分別取代式（20）中的ΠA和ΠB，則不等式左側為Ug(Πopt)。對于不等式右側，代入式（13），忽略常值代價函數，將式（20）右側化為

因此可得命題結論。

由命題1 可知，若要控制HCG 模型的性能下界PoA<1+η0（0<η0<1），則需要設置衰減參數ε滿足

3 博弈學習算法

SAP 算法［16］原本是空間博弈中的一種自適應學習方法，本文將針對任務分配問題的特點，將其改造為適用于任務分配問題的SAP算法。

SAP算法的特點是在第k次迭代時等可能地隨機選擇1 枚導彈Mi進行目標的選擇，其他導彈保持目標選擇a-i(k-1)不變。被選中的導彈Mi根據自己的可選集Ai使用以下方法計算其目標選擇概率分布為

式中：σ(·)為softmax函數。

在原始的SAP 算法迭代后期，由于只有少部分導彈尚未達到均衡，此時若仍然等可能地選擇1枚導彈，會導致收斂過程加長。因此，對原始SAP 算法作出以下改進。

在第k次迭代時刻，每枚導彈會統計前（k-1）次迭代過程中自己被選中且沒有改變目標的次數Ni(k)。設計選擇導彈的概率分布為

這樣設計的意義在于：較大的Ni(k)使得選中已處于均衡狀態的導彈的概率減少；如果導彈改變了目標，則Ni(k)清零，使導彈重新進入均衡迭代過程。

另外，HCG 模型下導彈效用函數均為非負值，可能導致計算pi(k)時各分量之間差距不大而使得導彈反而加入不符合約束的聯盟，從而導致約束條件不再滿足。為了保證收斂解的可行性與快速性，對SAP 算法作出修正，將計算pi(k)的方法改為導彈效用值為正的聯盟參與計算，如果所有分量均為0，則隨機選擇聯盟加入。因此pi(k)的計算公式為

本章提出的改進SAP算法流程如圖2所示。

圖2 改進SAP算法流程Fig.2 Flow of improve SAP algorithm

4 仿真實驗與分析

本章設計仿真實驗測試本文HCG 模型與算法的性能。為了對比效果，使用幾種集中式啟發算法對式（8）所示模型進行對比，使用到的集中式啟發算法包括遺傳算法（genetic algorithm，GA）、粒子群算法（paticle swarm optimization，PSO）、退火遺傳算法（simulated annealing genetic algorithm，SAGA）、蟻群退火遺傳算法（ant colony optimization-simulated annealing genetic algorithm，ACOSAGA）。

將GA 和SAGA 算法的參數設置為：種群數量為20，迭代次數為200步，交叉算子為PMX 算子，交叉概率為0.4，變異算子為EM 算子，變異概率為0.4。ACOSAGA 算法使用蟻群算法對SAGA 算法中使用的交叉和變異算子進行尋優。

此外，使用文獻［17］中的分布式一致交互算法（distributed mutual exclusion algorithm，DMEA）作為分布式算法中的對比算法參與實驗。

為了消除隨機因素影響，本文將6 種算法針對同一場景的任務分配問題求解100 次，每次迭代隨機產生初始解，以此比較各算法下優化性能的穩定性。此外，為了比較不同場景下的算法性能，本文將同一場景下所有算法重復計算得到的所有優化值中的最優值作為參照值，將各算法所得目標值與參照值作比，作為各算法的優化程度表現。下面將使用的“AvsB”表示A枚導彈對戰B個目標的場景。

任務分配中的場景通?？梢苑譃閮煞N，分別為平衡分配場景和非平衡分配場景。平衡分配場景指的是n枚導彈攻擊n個目標，即導彈數量等于目標數量；非平衡分配問題指的是導彈數量不等于目標數量，在本文中只研究導彈數大于目標數的情況。

平衡分配問題可以反映出問題規模對算法的影響。在使用集中式啟發算法解決非平衡問題時，引入虛擬目標將非平衡問題轉換成平衡問題?；贖CG模型的SAP 算法（HCGSAP）沒有引入虛擬目標，也沒有對可選目標集加以約束，因此在處理非平衡問題和平衡問題時的性能有所差別。本章將針對任務分配中的這兩種問題場景進行仿真實驗，對比HCGSAP算法與集中式啟發算法的性能。

本文使用的仿真平臺是Ubuntu16.04 系統下的Matlab R2018a。

4.1 平衡分配場景

首先分析平衡分配場景，設計導彈和目標數量等同地從10 增加到50，圖3 展示了6 種算法在5 種場景下的優化結果的箱型圖分布及其平均值曲線，具體平均值數據見表1。

圖3 平衡分配場景下算法優化效果對比Fig.3 Comparison of algorithm optimization performance in balance scenarios

表1 平衡場景下不同算法優化效果平均值對比Tab.1 Comparison of different algorithm optimization performance in balance scenarios

從同場景的不同算法角度對比可見，集中式啟發算法的優化效果普遍比分布式算法好，且SAGA 算法的優化效果最好。本文提出的HCGSAP 算法優化效果達到97.5%以上，但相比于集中式啟發算法和另一種分布式算法DMEA還存在差距。

從不同場景變化角度來看，隨著任務分配規模的擴大，集中式啟發算法除了SAGA 外，優化效果都有略微下降。而HCGSAP 算法和基于HCG 模型的DMEA 算法（HCGDMEA）性能則有所提升，表現為得到的解更加收斂和穩定，且結果與部分集中式算法相當，如PSO 算法。在50 vs 50 的場景中，HCGSAP可達到98%以上的優化效果。由此可見，HCG 模型下的分布式算法在處理較大規模問題上具有較好的優化能力。

關于收斂效率方面，由于集中式算法和分布式算法的框架不同，表2 中只比較了HCGSAP 和HCGDMEA 的平均收斂步數。由表2 可以看出，HCGSAP 的總收斂步數比HCGDMEA 多，但實際上由于SAP 算法的迭代特點，將收斂步數平均到每枚導彈后，即表2 第3 行所示的HCGSAP 收斂步數是很小的?？紤]到算法中計算效用函數以及交互通信達到一致性需要消耗較多資源，實際上HCGSAP 可以節約更多的時間和資源。

表2 平衡場景下分布式算法平均收斂步數對比Tab.2 Comparison of average convergence steps in balance scenarios

4.2 非平衡分配場景

選擇固定導彈數量為55，目標數量由10 增加到50，對于目標分配的不平衡，設定約束條件的確定方法為盡量平均分配，不平均部分隨機分配。圖4 展示的是非平衡場景下不同算法的優化效果對比，具體平均值數據見表3。

圖4 非平衡分配場景下不同算法優化效果對比Fig.4 Comparison of different algorithm optimization performance in unbalance scenarios

從同場景下不同算法的對比來看，可看出在非平衡問題下，集中式算法效果有所下降，而分布式算法則有所提升，尤其是HCGSAP 算法，在部分場景下優化效果已經超過了HCGDMEA 算法，且達到了與PSO算法相當的水平。

從不同場景變化看，隨著目標數量的增加，任務分配的非平衡程度減小，HCGSAP算法的性能逐漸降低，但優化效果也達到了98%以上；而在目標數量為10 時，問題非平衡程度最大，且此場景下HCGSAP 算法性能可與PSO 算法和ACOSAGA 算法相當。由此可見，HCGSAP算法在非平衡分配問題上的優化效果比集中式算法更優。

關于收斂效率方面，表3 列出了非平衡分配場景下分布式算法的平均收斂步數對比。從不同場景的對比情況分析，HCGDMEA算法所需的迭代步數會隨著目標數量增加而增加。在非平衡程度較高時，HCGSAP 算法下平均到每枚導彈所需的迭代次數最多，在非平衡程度較低即目標數量較多時，HCGSAP算法下平均到每枚導彈的迭代次數反而減少，這是由于HCGSAP 算法的總迭代步數幾乎不隨目標數量的改變而改變。

表3 非平衡場景下不同算法優化效果對比Tab.3 Comparison of different algorithm optimization performance in unbalance scenarios

從上述兩個場景的仿真對比可以看出，與集中式啟發算法以及分布式的DMEA算法對比，本文設計的HCG 模型及SAP 算法具有較好的優化能力和收斂效率，尤其是在非平衡程度較高的分配問題和較大規模問題上具有更好的性能，在某些場景下可以達到與集中式算法相當的性能。

表4 非平衡場景下分布式算法平均收斂步數對比Tab.4 Comparison of average convergence steps in unbalance scenarios

5 結束語

針對實際空戰場景下空空導彈集群攻擊中任務分配技術所面臨的高動態性、強博弈性需求，本文使用HCG 作為基本理論工具，設計了基于HCG 的任務分配模型，并針對該模型改進了SAP 算法。仿真實驗表明，本文設計的模型與算法在較大規模分配問題和非平衡分配問題下具有良好的性能和收斂效率。

但本文提出的算法仍存在不少問題，比如在部分場景下仍不能達到集中式算法的水平。另一方面，分布式算法的優化結果分散性較大，因此提高分布式算法求解結果的優化性和穩定性是下一步的研究工作。