基于多聯(lián)盟非合作博弈納什均衡搜索的集群對(duì)抗方法

劉 飛 董希旺,2 化永朝,2 于江龍 任 章

集群系統(tǒng)及集群智能的研究得到了廣泛重視,其在集群編隊(duì)、搜索救援、區(qū)域偵查等場景[1-3],以及軍事領(lǐng)域具有極大應(yīng)用潛力.軍用無人集群系統(tǒng)具有分布式、自組織、自主決策的特點(diǎn),面對(duì)常規(guī)防御系統(tǒng)可形成非對(duì)稱優(yōu)勢.以無人集群攔截入侵集群是應(yīng)對(duì)其威脅、抵消其優(yōu)勢的可行方式,由此形成了集群對(duì)抗這一研究課題[4].

多聯(lián)盟非合作博弈理論可以用來建模與分析無人集群對(duì)抗中包含的復(fù)雜合作與競爭關(guān)系[5].大規(guī)模無人集群中可能會(huì)基于其載荷或性能特點(diǎn)形成各類異構(gòu)子群,承擔(dān)探測、干擾、攻擊等不同任務(wù).敵我無人集群均可基于上述特點(diǎn)或多樣任務(wù)形成多個(gè)聯(lián)盟.在多聯(lián)盟非合作博弈框架下,每個(gè)智能體作為實(shí)際的決策者驅(qū)動(dòng)其決策變量到達(dá)納什均衡點(diǎn),從而完成集群對(duì)抗任務(wù).

多聯(lián)盟非合作博弈建模了集群內(nèi)的合作關(guān)系和集群間的非合作關(guān)系,其納什均衡搜索算法的設(shè)計(jì)是實(shí)現(xiàn)集群對(duì)抗的關(guān)鍵.博弈參與者的策略由其動(dòng)力學(xué)及控制輸入驅(qū)動(dòng)[6].對(duì)于具有動(dòng)力學(xué)系統(tǒng)的多智能體系統(tǒng)的納什均衡搜索算法設(shè)計(jì),可利用時(shí)間尺度分離的方式依次進(jìn)行靜態(tài)納什均衡的搜索和定點(diǎn)跟蹤控制[7-8].另一種方法是直接設(shè)計(jì)分布式反饋控制器[9-10].針對(duì)部分信息未知的問題,通常基于一致性協(xié)議進(jìn)行分布式狀態(tài)估計(jì)[11-13].

無人集群的對(duì)抗中存在著大量的約束條件,主要來自資源或任務(wù)約束[14].含有約束的博弈問題的均衡被稱為廣義納什均衡（generalized Nash equilibrium,GNE）.文獻(xiàn)[15-17]提出了分布式的算子分割算法以定步長求解GNE,同時(shí)保證了算法收斂性.文獻(xiàn)[18]研究了多聯(lián)盟非合作博弈中GNE 的求解問題,考慮了代價(jià)函數(shù)和約束函數(shù)不光滑的情況.另一方面,集群對(duì)抗是一個(gè)高動(dòng)態(tài)過程,無人集群的任務(wù)是時(shí)變的,因此,這種情況下多聯(lián)盟非合作博弈的納什均衡是一個(gè)軌跡,而不是一個(gè)靜態(tài)策略[19],這對(duì)納什均衡搜索算法的設(shè)計(jì)帶來了更大困難.

本文主要研究基于多聯(lián)盟非合作博弈的無人集群對(duì)抗的建模方法,提出多聯(lián)盟非合作博弈時(shí)變納什均衡的搜索策略,主要貢獻(xiàn)總結(jié)如下：

1）考慮多聯(lián)盟之間存在的耦合約束和局部約束,設(shè)計(jì)了一種障礙函數(shù)處理智能體的局部約束,可用于保證集群對(duì)抗的安全性.

2）將障礙函數(shù)引入博弈代價(jià)函數(shù)并轉(zhuǎn)化為新的多聯(lián)盟非合作博弈問題,證明了其廣義納什均衡是原問題的epsilon 廣義納什均衡.

3）基于障礙函數(shù)和原對(duì)偶方法設(shè)計(jì)了時(shí)變廣義納什均衡搜索算法.分析了該算法在集群對(duì)抗中分布式時(shí)變編隊(duì)隊(duì)形設(shè)計(jì)的應(yīng)用.

1 問題的提出

1.1 多聯(lián)盟非合作博弈模型

考慮集群博弈對(duì)抗場景下包含N 個(gè)聯(lián)盟的多聯(lián)盟非合作博弈廣義納什均衡搜索問題.

1.2 廣義納什均衡搜索

給出上述博弈問題的廣義納什均衡的定義.

對(duì)于所有的i∈P,j∈Pi成立,其中,.此外,如果存在集合Sij使得,對(duì)于任意的i∈P,j∈Pi和xij成立,那么是多聯(lián)盟非合作博弈的納什均衡.根據(jù)廣義納什均衡的定義,在滿足約束的前提下,當(dāng)各智能體采取廣義納什均衡策略時(shí),沒有一個(gè)參與者可以通過單方面改變策略來降低代價(jià)函數(shù).

在無人集群的多聯(lián)盟非合作博弈中,需考慮智能體的動(dòng)力學(xué)特性,設(shè)智能體的動(dòng)力學(xué)模型為無擾動(dòng)的二階積分器模型

關(guān)于通信拓?fù)洹⒓s束、代價(jià)函數(shù)有如下假設(shè).

假設(shè)1:對(duì)于每個(gè)智能體聯(lián)盟i,聯(lián)盟內(nèi)通信拓?fù)銰i是無向且連通的,聯(lián)盟間通信拓?fù)湟彩菬o向且連通的.

假設(shè)2: 局部集合約束Ωij是閉凸集且邊界是分段光滑的,聯(lián)盟內(nèi)耦合代價(jià)函數(shù)gij是凸函數(shù)且二次可微,滿足Slater 條件.

假設(shè)4: 對(duì)每個(gè)智能體,其代價(jià)函數(shù)時(shí)變部分的一階和二階微分是有界的.

為便于求解多聯(lián)盟非合作博弈的廣義納什均衡,引入變分不等式問題.

事實(shí)上,多聯(lián)盟非合作博弈的廣義納什均衡同樣也是上述變分不等式問題（5）的解.

引理1[6]: 在假設(shè)3 下,變分不等式問題（5）的任意一個(gè)解是多聯(lián)盟非合作博弈問題（1）的廣義納什均衡.

引理2[6]: 假設(shè)變分不等式問題（5）滿足Slater條件,那么x*是問題（5）的解當(dāng)且僅當(dāng)存在乘子,滿足

對(duì)比式（6）和式（7）可見,區(qū)別在于式（6）中同一聯(lián)盟i 中的對(duì)偶變量是相同的,即,因此,式（6）是式（7）的特殊情況.前面提到,偽梯度的強(qiáng)單調(diào)性保證了基于式（6）得到的廣義納什均衡的唯一性,且該廣義納什均衡屬于滿足式（7）的解的集合,特別地,將該廣義納什均衡稱為變分廣義納什均衡.

本文主要研究多聯(lián)盟非合作博弈的變分廣義納什均衡的搜索問題.變分廣義納什均衡的唯一性有利于納什均衡搜索算法的收斂,同時(shí)也有著重要的結(jié)構(gòu)和物理特性,即相同的對(duì)偶變量可使聯(lián)盟中耦合約束帶來的邊界代價(jià)對(duì)于各個(gè)參與者是均衡的.由于多聯(lián)盟非合作博弈的代價(jià)函數(shù)中引入了時(shí)變部分,博弈問題的納什均衡不再是固定的點(diǎn),而是時(shí)變的納什均衡軌跡.因此,納什均衡搜索算法要能夠較好地尋找并跟蹤納什均衡軌跡,這也是一個(gè)具有挑戰(zhàn)性的難題.

2 多聯(lián)盟非合作博弈變分廣義納什均衡搜索問題轉(zhuǎn)換

在多聯(lián)盟非合作博弈的變分廣義納什均衡搜索中,智能體的動(dòng)力學(xué)特性和局部約束的強(qiáng)制性是矛盾的,很難在滿足動(dòng)態(tài)搜索納什均衡的過程中時(shí)刻滿足局部約束.本章將設(shè)計(jì)一種障礙函數(shù)處理局部約束,將障礙函數(shù)引入代價(jià)函數(shù)中,從而將局部約束隱含在代價(jià)函數(shù)中,并得到新的多聯(lián)盟非合作博弈問題.

2.1 局部約束的障礙函數(shù)

多聯(lián)盟非合作博弈問題中參與者具有高階積分器動(dòng)力學(xué)特性或復(fù)雜動(dòng)力學(xué)特性,文獻(xiàn)中基于投影動(dòng)態(tài)系統(tǒng)（projected dynamical system）穩(wěn)定性設(shè)計(jì)的變分納什均衡搜索算法不再適用.將根據(jù)局部集合約束設(shè)計(jì)障礙函數(shù),使得納什均衡搜索過程始終保持在局部約束范圍內(nèi).

即便根據(jù)假設(shè)2,博弈策略的局部集合約束Ωij具有分段光滑邊界,但是對(duì)于一般集合Ωij,很難找到表達(dá)其解析表達(dá)式.受優(yōu)化理論中內(nèi)點(diǎn)方法的啟發(fā),針對(duì)集合約束Ωij可設(shè)計(jì)障礙函數(shù)

從式（8）可見,對(duì)于某一決策變量xij,障礙函數(shù)有限表示決策變量滿足局部約束,障礙函數(shù)為正無窮表示決策變量位于約束邊界或不滿足約束.障礙函數(shù)可以近似視為某個(gè)力場的勢函數(shù),當(dāng)智能體的決策變量xij靠近約束邊界時(shí),由邊界產(chǎn)生排斥力阻止其繼續(xù)接近約束邊界.對(duì)于任意形狀的凸集合Ωij,很難找到完美的勢函數(shù),但是,后續(xù)分析將證明,式（8）的障礙函數(shù)可同樣發(fā)揮勢函數(shù)的作用,使得決策變量在多聯(lián)盟非合作博弈納什均衡搜索中始終滿足局部約束.

對(duì)于完美的勢函數(shù),其勢場力為其負(fù)梯度方向.當(dāng)障礙函數(shù)作為近似勢函數(shù)時(shí),勢場力為,其中,當(dāng)在xij處可微時(shí),為的梯度;當(dāng)在xij處不可微時(shí),為的次梯度.障礙函數(shù)（8）的性質(zhì)由以下引理給出.

引理3: 在假設(shè)2 下,障礙函數(shù)（8）有以下性質(zhì):

如果xij在邊界上有多個(gè)投影點(diǎn),那么在xij處不可微,在xij處的次微分是集合的凸包.

2.2 ε-廣義納什均衡

通過引入障礙函數(shù)來處理局部集合約束,原多聯(lián)盟非合作博弈問題可以轉(zhuǎn)換為如下的博弈問題

對(duì)比問題（1）和問題（10）,可見問題（10）中障礙函數(shù)成為各智能體代價(jià)函數(shù)的一部分,而局部約束則放寬了邊界條件.障礙函數(shù)將隱性地起到局部約束的作用,在廣義納什均衡搜索過程中,由于障礙函數(shù)的懲罰作用,智能體的決策變量會(huì)避免穿越局部集合約束邊界.

后續(xù)將求解多聯(lián)盟非合作博弈問題（10）,而非問題（1）.由于障礙函數(shù)的作用,問題（10）的納什均衡搜索軌跡將始終保持在中,同時(shí)根據(jù)假設(shè)2,Slater 條件依然滿足.

為了說明多聯(lián)盟非合作博弈問題（10）和問題（1）的廣義納什均衡之間的關(guān)系,下面引入了ε-廣義納什均衡的概念.

下面的定理說明了多聯(lián)盟非合作博弈問題（10）的解是問題（1）的一個(gè)ε-廣義納什均衡.

定理1: 在假設(shè)1-3 下,多聯(lián)盟非合作博弈問題（1）和問題（10）均有唯一的變分廣義納什均衡.對(duì)于任意的ε>0,存在,使得問題（10）的變分廣義納什均衡是問題（1）的ε-廣義納什均衡.

證明: 在假設(shè)2 和3 下,多聯(lián)盟非合作博弈問題（1）的策略空間約束滿足Slater 條件,且代價(jià)函數(shù)偽梯度是強(qiáng)單調(diào)的,因此,基于多聯(lián)盟非合作博弈問題（1）定義的變分不等式（5）存在唯一解.根據(jù)引理1,多聯(lián)盟非合作博弈問題（1）的變分廣義納什均衡即為變分不等式（5）的解,同樣滿足存在性和唯一性.

對(duì)于多聯(lián)盟非合作博弈問題（10）,每個(gè)智能體的代價(jià)函數(shù)改寫為,根據(jù)引理3,是凸函數(shù)但不一定可微.可建立廣義變分問題: 尋找,滿足

根據(jù)式（13）,最終有

進(jìn)一步,對(duì)于任意聯(lián)盟i 中任意智能體j,可以定義類似的參數(shù)序列,對(duì)于任意的ε>0,可以找到一致的N,當(dāng)選擇n>N 時(shí),以及參數(shù)組,多聯(lián)盟非合作博弈問題（10）的變分廣義納什均衡是原問題（1）的ε-廣義納什均衡.這個(gè)結(jié)論很容易利用反證法證明.證畢.

3 分布式變分廣義納什均衡搜索算法設(shè)計(jì)與穩(wěn)定性分析

在多聯(lián)盟非合作博弈問題框架中,每個(gè)聯(lián)盟中的智能體通過通信網(wǎng)絡(luò)交互信息,并通過動(dòng)態(tài)平均一致性算法,實(shí)時(shí)估計(jì)聯(lián)盟代價(jià)函數(shù)對(duì)于各自決策變量的偏微分.采用原對(duì)偶方法處理聯(lián)盟中的可分耦合約束,每個(gè)智能體均需估計(jì)各自的對(duì)偶變量,并引入了輔助變量zij以確保聯(lián)盟內(nèi)所有智能體對(duì)于對(duì)偶變量的估計(jì)是一致的.

無人集群的多聯(lián)盟非合作博弈變分廣義納什均衡搜索算法設(shè)計(jì)為

定理2: 在假設(shè)1～3 下,x*是多聯(lián)盟非合作博弈（10）的變分廣義納什均衡,當(dāng)且僅當(dāng)存在使得是系統(tǒng)（15）的平衡點(diǎn),其中,.

是系統(tǒng)（15）的平衡點(diǎn),則有

根據(jù)引理1 和引理2,x*是多聯(lián)盟非合作博弈問題（10）的變分廣義納什均衡當(dāng)且僅當(dāng)存在滿足下述KKT 條件

因此,下面主要證明條件（16）～條件（19）與條件（20）～條件（21）的等價(jià)性.

對(duì)上述李雅普諾夫函數(shù)函數(shù)求導(dǎo),利用假設(shè)3和4,可依次證明級(jí)聯(lián)系統(tǒng)的輸入狀態(tài)穩(wěn)定,并且系統(tǒng)狀態(tài)收斂到納什均衡的鄰域內(nèi).

在多聯(lián)盟非合作博弈變分納什均衡搜索算法（14）中,直接使用了所有智能體決策變量的完全信息x 和v,所以策略（14）不是完全分布式的.事實(shí)上,類似對(duì)聯(lián)盟代價(jià)函數(shù)梯度的估計(jì),可以利用領(lǐng)導(dǎo)者-跟隨者一致性算法估計(jì)其他智能體的狀態(tài)信息,并用來計(jì)算代價(jià)函數(shù)偏微分和約束函數(shù)數(shù)值.

4 集群時(shí)變編隊(duì)干擾與反干擾對(duì)抗

4.1 集群時(shí)變編隊(duì)跟蹤的決策－控制架構(gòu)

本節(jié)將介紹多聯(lián)盟非合作博弈納什均衡搜索算法在分布式時(shí)變編隊(duì)控制中的應(yīng)用.

假設(shè)敵我雙方無人集群分別形成一個(gè)任務(wù)聯(lián)盟,每個(gè)聯(lián)盟內(nèi)分別有一個(gè)領(lǐng)導(dǎo)者,聯(lián)盟中跟隨著進(jìn)行時(shí)變編隊(duì)跟蹤以完成聯(lián)盟任務(wù).在已有文獻(xiàn)中,時(shí)變編隊(duì)隊(duì)形通常是指定的全局信息,本文通過多聯(lián)盟非合作博弈納什均衡搜索給出時(shí)變編隊(duì)隊(duì)形決策.假設(shè)我方聯(lián)盟P1中每個(gè)智能體均搭載有電磁干擾裝置,需與聯(lián)盟中其他智能體協(xié)作以產(chǎn)生對(duì)敵方聯(lián)盟P2最大干擾效果.聯(lián)盟P2則處于防御態(tài)勢,盡量形成緊密陣型維持聯(lián)盟內(nèi)通信拓?fù)涞倪B通性.在這一場景下,兩個(gè)聯(lián)盟均需協(xié)調(diào)聯(lián)盟內(nèi)智能體的策略,并找到各自最佳時(shí)變編隊(duì)隊(duì)形.

此外,各聯(lián)盟需滿足一些約束條件.要求聯(lián)盟中智能體與領(lǐng)導(dǎo)者的平均距離存在最大閾值以減小通信能量損耗.每個(gè)聯(lián)盟內(nèi)任意一個(gè)智能體有活動(dòng)范圍限制,該活動(dòng)范圍是以領(lǐng)導(dǎo)者為圓心,給定半徑的球,從而引入了聯(lián)盟中智能體的局部約束.

圖1 時(shí)變編隊(duì)跟蹤示意圖Fig.1 Schematic diagram of time-varying formation tracking

多聯(lián)盟非合作博弈變分廣義納什均衡搜索—分布式時(shí)變編隊(duì)跟蹤控制構(gòu)成了決策—控制的雙層結(jié)構(gòu),如圖2 所示.多聯(lián)盟非合作博弈變分廣義納什均衡搜索算法給出跟隨者最優(yōu)編隊(duì)構(gòu)型,隨后由編隊(duì)跟蹤控制算法實(shí)現(xiàn).領(lǐng)導(dǎo)者作為獨(dú)立節(jié)點(diǎn),是編隊(duì)跟蹤的目標(biāo),也是編隊(duì)構(gòu)型決策的參考點(diǎn).

圖2 時(shí)變編隊(duì)構(gòu)型決策—編隊(duì)跟蹤控制層次結(jié)構(gòu)Fig.2 Hierarchy structure of time-varying formation decisionmaking and formation tracking control

在上述博弈問題的代價(jià)函數(shù)定義中,假設(shè)聯(lián)盟P1的領(lǐng)導(dǎo)者是運(yùn)動(dòng)的,因此,代價(jià)函數(shù)與領(lǐng)導(dǎo)者的坐標(biāo)有關(guān),博弈問題的納什均衡是時(shí)變的.基于納什均衡搜索算法（14）以及編隊(duì)構(gòu)型的動(dòng)力學(xué)模型（2）可輸出時(shí)變編隊(duì)構(gòu)型,編隊(duì)構(gòu)型的一階導(dǎo)數(shù),以及二階導(dǎo)數(shù),其中,等于納什均衡搜索算法（14）給出的控制量.在此基礎(chǔ)上可設(shè)計(jì)聯(lián)盟P1的編隊(duì)跟蹤控制器,在跟蹤的同時(shí)實(shí)現(xiàn)時(shí)變編隊(duì)構(gòu)型的保持.

智能體動(dòng)力學(xué)仍為二階積分器模型,時(shí)變編隊(duì)跟蹤控制器設(shè)計(jì)由文獻(xiàn)[2]給出,其形式為:

4.2 仿真算例

在無人集群干擾及反干擾對(duì)抗場景以及多聯(lián)盟非合作博弈模型基礎(chǔ)上,應(yīng)用多聯(lián)盟非合作博弈納什均衡搜索算法（14）以及編隊(duì)跟蹤控制算法（24）,仿真結(jié)果如圖3～圖5 所示.圖3 給出了集群博弈對(duì)抗雙方軌跡曲線.聯(lián)盟P1跟隨其領(lǐng)導(dǎo)者環(huán)繞聯(lián)盟P2作圓周運(yùn)動(dòng).兩個(gè)聯(lián)盟根據(jù)干擾與反干擾作戰(zhàn)任務(wù)和博弈模型實(shí)時(shí)求解編隊(duì)構(gòu)型,在近似收斂到時(shí)變納什均衡后,聯(lián)盟P1在其領(lǐng)導(dǎo)者軌跡內(nèi)側(cè),抵近聯(lián)盟P2施加干擾,而聯(lián)盟P2則遠(yuǎn)離聯(lián)盟P1,兩個(gè)聯(lián)盟的運(yùn)動(dòng)形成了環(huán)繞聯(lián)盟P2中心節(jié)點(diǎn)的運(yùn)動(dòng)模式.

圖3 時(shí)變編隊(duì)跟蹤干擾-反干擾場景下集群博弈對(duì)抗雙方軌跡Fig.3 Trajectories of both sides of cluster game confrontation in the time-varying formation tracking interference and anti-interference scenario

兩個(gè)聯(lián)盟的狀態(tài)曲線如圖4 所示,不同于靜態(tài)納什均衡,本例中納什均衡是時(shí)變的編隊(duì)構(gòu)型,由于聯(lián)盟P1的領(lǐng)導(dǎo)者為規(guī)律的圓周運(yùn)動(dòng),可見各聯(lián)盟智能體的狀態(tài)也是周期性變化.聯(lián)盟的耦合約束如圖5所示.由于收斂誤差的存在,聯(lián)盟P1、P2的耦合約束圍繞0 附近上下波動(dòng).理想結(jié)果應(yīng)當(dāng)是耦合約束漸進(jìn)收斂到0,可通過RISE 方法設(shè)計(jì)納什均衡搜索策略,這會(huì)是本文后續(xù)的研究方向.

圖4 時(shí)變編隊(duì)跟蹤干擾-反干擾場景下集群博弈對(duì)抗雙方軌跡Fig.4 Trajectories of both sides of cluster game confrontation in the time-varying formation tracking interference and anti-interference scenario

圖5 時(shí)變編隊(duì)跟蹤干擾－反干擾場景下聯(lián)盟耦合約束Fig.5 Coalition coupling constraints of agents in the time-varying formation tracking interference and anti-interference scenario

5 結(jié)論

本文研究了嚴(yán)苛多約束下多聯(lián)盟非合作博弈變分廣義納什均衡搜索算法及其在無人集群博弈對(duì)抗中的應(yīng)用.在多聯(lián)盟非合作博弈中,智能體決策變量存在局部約束,以及聯(lián)盟內(nèi)的耦合約束.為使得決策變量始終滿足局部約束,設(shè)計(jì)了一種障礙函數(shù),其滿足凸性和可微性.隨后,設(shè)計(jì)了多聯(lián)盟非合作博弈變分廣義納什均衡搜索算法,證明了搜索算法的平衡點(diǎn)等價(jià)于變分廣義納什均衡點(diǎn),在多聯(lián)合非合作博弈目標(biāo)函數(shù)為時(shí)變的情況下,變分廣義納什均衡搜索算法可以收斂到變分廣義納什均衡點(diǎn)的鄰域.最后設(shè)計(jì)了集群干擾與反干擾的對(duì)抗場景,驗(yàn)證了多聯(lián)盟非合作博弈變分廣義納什均衡搜索算法在該場景中的應(yīng)用能力.