對(duì)抗網(wǎng)絡(luò)下多智能體系統(tǒng)的能控性分析

曹少斌 紀(jì)志堅(jiān) 于海生 侯 婷

(青島大學(xué) 自動(dòng)化工程學(xué)院，山東 青島 266071)

近年來(lái)，多智能體系統(tǒng)(MAS)的協(xié)同控制研究得到了廣泛的研究，同時(shí)其研究成果已應(yīng)用于工程學(xué)，生態(tài)學(xué)，生物學(xué)，社會(huì)學(xué)，計(jì)算機(jī)通信等許多領(lǐng)域．基于MAS的協(xié)同控制研究了許多基本的重要問(wèn)題，包括一致性[1-3]，不可控拓?fù)浣Y(jié)構(gòu)[4]，開(kāi)關(guān)拓?fù)鋄5-6]等．可控性是MAS協(xié)同控制的基礎(chǔ)研究課題．MAS的可控性最初由Tanner[7]提出，其中一個(gè)智能體被作為領(lǐng)航者．基于最近鄰居互連協(xié)議，提出了一個(gè)在固定時(shí)不變拓?fù)湎吕绽咕仃嚳煽匦缘某浞直匾獥l件．據(jù)此，為MAS的可控性提供了一些充分/必要的條件．基于此，文獻(xiàn)[8]提出了另一種代數(shù)條件．之后，研究人員從圖論角度研究了MAS的可控性[9-10]．具體來(lái)說(shuō)，圖劃分的各種概念和性質(zhì)被用來(lái)研究MAS的可控性，例如等價(jià)劃分[11]，幾乎等價(jià)劃分[12]等．最近，還研究了MAS在某些特殊圖上的可控性．例如路圖和環(huán)圖[13]，星圖[14]等．因此，本文致力于解決MAS中對(duì)抗交互的能控性問(wèn)題．首先，領(lǐng)航者-跟隨者結(jié)構(gòu)被引入到對(duì)抗網(wǎng)絡(luò)中．接著，驗(yàn)證了Tanner(2004)提出的系統(tǒng)的必要條件和充分條件．結(jié)果表明，協(xié)作網(wǎng)絡(luò)下的可控條件并不完全適合對(duì)抗網(wǎng)絡(luò)，并給出了對(duì)抗網(wǎng)絡(luò)能控的兩個(gè)必要條件．最后，研究了對(duì)抗網(wǎng)絡(luò)下Peterson圖的能控性，并與協(xié)作網(wǎng)絡(luò)下的能控性進(jìn)行了對(duì)比，得到了Peterson圖在協(xié)作網(wǎng)絡(luò)下和對(duì)抗網(wǎng)絡(luò)下能控性等價(jià)的部分情形，并將其應(yīng)用到了Peterson圖以外的三部圖的情形下．

1 系統(tǒng)描述

考慮一個(gè)多智能體網(wǎng)絡(luò)，假設(shè)網(wǎng)絡(luò)中包含n個(gè)具有單積分器動(dòng)態(tài)的智能體，頂點(diǎn)集為V=(v1，v2，…，vn)．假設(shè)有m(m≤n)個(gè)智能體被選作領(lǐng)航者，每個(gè)領(lǐng)航者都賦給一個(gè)外部控制輸入，其余智能體被選作跟隨者．進(jìn)一步假設(shè)，頂點(diǎn)集中的前m個(gè)頂點(diǎn)被選作領(lǐng)航者，即領(lǐng)航者節(jié)點(diǎn)集合為VL={v1，…，vm}，跟隨者集合即為VF=VVL．

對(duì)抗網(wǎng)絡(luò)下，跟隨者i∈VF服從以下共識(shí)協(xié)議：

每個(gè)領(lǐng)航者i∈VL都賦給一個(gè)相應(yīng)的外部控制輸入ui且服從如下共識(shí)協(xié)議：

對(duì)抗網(wǎng)絡(luò)下的系統(tǒng)動(dòng)態(tài)方程可以表示為：

(1)

2 對(duì)抗網(wǎng)絡(luò)下的領(lǐng)航者-跟隨者結(jié)構(gòu)

包含n個(gè)智能體的網(wǎng)絡(luò)中，假設(shè)存在兩種不同的智能體：一些嚴(yán)格服從共識(shí)協(xié)議，另一些可給定外部輸入對(duì)其進(jìn)行控制，這兩種智能體分別稱(chēng)之為跟隨者和領(lǐng)航者．在對(duì)抗網(wǎng)絡(luò)系統(tǒng)(1)下，可以將系統(tǒng)方程重新寫(xiě)作如下形式：

(2)

其中Ll和Lf分別對(duì)應(yīng)領(lǐng)航者和跟隨者的編號(hào)，lfl表示從領(lǐng)航者到跟隨者的通信連接關(guān)系，u為外界控制輸入的迭加向量，xl和xf分別是所有領(lǐng)航者狀態(tài)和跟隨者狀態(tài)的迭加向量．根據(jù)領(lǐng)航者-跟隨者結(jié)構(gòu)劃分，上述系統(tǒng)可表示為：

(3)

研究對(duì)抗網(wǎng)絡(luò)系統(tǒng)(1)下的能控性問(wèn)題，就是研究對(duì)抗網(wǎng)絡(luò)中領(lǐng)航者對(duì)跟隨者的控制能力，即研究系統(tǒng)：

(4)

的能控性問(wèn)題．

對(duì)于給定的拓?fù)鋱DG，系統(tǒng)(4)是一個(gè)線(xiàn)性時(shí)不變系統(tǒng)，系統(tǒng)控制矩陣為：-Lf∈R(n-m)×(n-m)，系統(tǒng)輸入矩陣為：-lfl∈R(n-m)×m，與符號(hào)拉普拉斯矩陣L相關(guān)．當(dāng)領(lǐng)航者只有一個(gè)時(shí)(即m=1)，系統(tǒng)輸入矩陣-lfl將退化為一個(gè)列向量．

則系統(tǒng)(4)的可控性矩陣為：

以上分析表明Tanner領(lǐng)航者-跟隨者結(jié)構(gòu)劃分完全可以適用于對(duì)抗網(wǎng)絡(luò)下能控性問(wèn)題的分析，以下討論中將沿用Tanner關(guān)于領(lǐng)航者-跟隨者拓?fù)浣Y(jié)構(gòu)下的定義方式：

(5)

其中-F表示系統(tǒng)控制矩陣-Lf，-r表示系統(tǒng)輸入矩陣-lfl，則系統(tǒng)(5)可控性矩陣為：

C=[-r，F(xiàn)r，-F2r，…，(-1)nFn-1r]

因?yàn)闊o(wú)向圖下矩陣L是對(duì)稱(chēng)的，因此矩陣F也是對(duì)稱(chēng)的．則存在矩陣U滿(mǎn)足F=UDUT，其中矩陣U的列由矩陣F的相互正交的特征向量組成，矩陣D為元素由矩陣F的特征值構(gòu)成的對(duì)角矩陣，則矩陣C可寫(xiě)作：C=[-r，UDUTr，-(UDUT)2r，…，(-1)n·(UDUT)n-1r]．

可以簡(jiǎn)化為：C=[-r，UDUTr，-(UDUT)2r，…，(-1)n(UDUT)n-1r]=U[-UTr，DUTr，-D2UTr，…，(-1)nDn-1UTr]．

由于矩陣U是非奇異的，所以只需考慮右半部分的秩：[-UTr，DUTr，-D2UTr，…，(-1)nDn-1UTr]．

可知系統(tǒng)(-F，-r)與系統(tǒng)(-D，-UTr)有相同的能控性，則由PBH秩判據(jù)可得：

[siI+D，-UTr]

(6)

當(dāng)式(6)對(duì)于矩陣-D的任意特征值都是行滿(mǎn)秩時(shí)，即rank[siI+D-UTr]=n-m，系統(tǒng)可控．由于正交矩陣U是可逆矩陣，是滿(mǎn)秩的，U的列向量都是線(xiàn)性無(wú)關(guān)的，則有rank(UTr)=rank(r)．假設(shè)矩陣UTr的秩為p，即矩陣UTr有p行(列)線(xiàn)性無(wú)關(guān)，則當(dāng)對(duì)角矩陣D中任意元素λ的重?cái)?shù)超過(guò)p個(gè)時(shí)，取si=λ，則siI+D有大于p個(gè)零行，從而使得矩陣[sI+D-UTr]對(duì)于si=λ不滿(mǎn)秩，則可知對(duì)角矩陣D中任意元素λ的重?cái)?shù)不大于矩陣r的秩是系統(tǒng)可控的必要條件．

以上討論結(jié)果可得到以下定理：

1)F的相同的特征值的個(gè)數(shù)不大于r的秩；

2)F的任一特征向量與r不同時(shí)正交．

3 對(duì)抗網(wǎng)絡(luò)下的Peterson圖

如圖1(a)所示，Peterson圖是由10個(gè)節(jié)點(diǎn)15條邊構(gòu)成的無(wú)向圖．節(jié)點(diǎn)集V可以被劃分為3個(gè)兩兩不相交的非空子集，并且使得任意一條邊的兩個(gè)端點(diǎn)都不在同一子集內(nèi)，則稱(chēng)之為三部圖．

基于三部圖可給出Peterson圖的一種劃分如下：

π={{1，4，9}，{3，6，7}，{2，5，8，10}}

則相應(yīng)的拉普拉斯矩陣可寫(xiě)作：

L=

對(duì)于劃分π，其中V1={1，4，9}，V2={3，6，7}，V3={2，5，8，10}．矩陣C表示領(lǐng)航者-跟隨者結(jié)構(gòu)下的可控性矩陣．協(xié)作網(wǎng)絡(luò)下的可控性矩陣記為CE：

CE=[-rE，F(xiàn)rE，-F2rE，…，(-1)nFn-1rE]

圖1 對(duì)抗網(wǎng)絡(luò)下的Peterson圖及三部圖

如圖1(b)所示，將V1中所有節(jié)點(diǎn)選作領(lǐng)航者時(shí)，有：

F=

矩陣C和矩陣CE的秩分別為：

rank(C)=4，rank(CE)=4

類(lèi)似地，如圖1(c)所示，當(dāng)選取V1中所有節(jié)點(diǎn)作為領(lǐng)航者，同樣可以得到rank(C)=4，rank(CE)=4；當(dāng)選取V3中全部節(jié)點(diǎn)作為領(lǐng)航者，可得到如上同樣的結(jié)果．最后，如圖1(d)所示，當(dāng)選取V1中所有節(jié)點(diǎn)作為領(lǐng)航者時(shí)，可以得到同樣的結(jié)果rank(C)=4，rank(CE)=4；當(dāng)選取V3中全部節(jié)點(diǎn)作為領(lǐng)航者，可得到如上同樣的結(jié)果．由此可以佐證引理1．當(dāng)符號(hào)圖G的節(jié)點(diǎn)集V可以被劃分為兩個(gè)互不相交的子集V1和V2，使得V1和V2之間的每條邊都是負(fù)邊，其余邊都是正邊，則圖G是結(jié)構(gòu)平衡的．

引理1[15]當(dāng)交互對(duì)抗網(wǎng)絡(luò)是結(jié)構(gòu)平衡的．如果領(lǐng)航者選自同一子集，則系統(tǒng)(F，r)的能控性等價(jià)于系統(tǒng)(F，rE)．

結(jié)合上述分析和引理1可以得到以下定理：

定理2當(dāng)負(fù)邊與領(lǐng)航者的選擇滿(mǎn)足以下兩個(gè)條件時(shí)，對(duì)抗網(wǎng)絡(luò)下的Peterson圖的能控性等價(jià)于對(duì)應(yīng)協(xié)作網(wǎng)絡(luò)下的Peterson圖的能控性：

1)選取V1和V2/V3之間的所有邊都選作負(fù)邊；選取V1或V2/V3中所有節(jié)點(diǎn)作為領(lǐng)航者．

2)選取V1和V2(或V1和V3)之間所有邊作為負(fù)邊；選取V1，V2和V3其中任一子集中所有節(jié)點(diǎn)作為領(lǐng)航者．

4 仿 真

例1：如圖2所示的對(duì)抗網(wǎng)絡(luò)下，符號(hào)完備圖包含5個(gè)節(jié)點(diǎn)，拓?fù)鋱D中存在3條負(fù)邊，分別為e13，e23，e24，其余皆為正邊，其中E-={e13，e23，e24}．

圖2 五階符號(hào)完備圖

取節(jié)點(diǎn)1和節(jié)點(diǎn)2作為領(lǐng)航者，則符號(hào)拉普拉斯矩陣L和控制輸入矩陣M分別為：

根據(jù)Tanner領(lǐng)航者-跟隨者結(jié)構(gòu)劃分，系統(tǒng)控制矩陣和系統(tǒng)輸入矩陣分別為：

以上結(jié)果說(shuō)明，領(lǐng)航者-跟隨者結(jié)構(gòu)在對(duì)抗網(wǎng)絡(luò)下也是適用的，并且與協(xié)作網(wǎng)絡(luò)下系統(tǒng)能控性的分析有著共通性，兩種網(wǎng)絡(luò)內(nèi)在的聯(lián)系將在以后的文章中進(jìn)行深入研究和進(jìn)一步的闡述．

例2：如圖3所示，網(wǎng)絡(luò)中包含9個(gè)節(jié)點(diǎn)，將節(jié)點(diǎn)按照三部圖劃分為π，其中π={V1，V2，V3}．

圖3 三部圖劃分下的9階對(duì)抗網(wǎng)絡(luò)

當(dāng)選擇紅色連接邊為負(fù)邊，選擇V2中全部節(jié)點(diǎn)作為領(lǐng)航者時(shí)，拉普拉斯矩陣和控制輸入矩陣分別為：

根據(jù)Tanner領(lǐng)航者-跟隨者結(jié)構(gòu)劃分：

對(duì)抗網(wǎng)絡(luò)下和對(duì)應(yīng)的協(xié)作網(wǎng)絡(luò)下的跟隨者控制輸入矩陣分別為：

根據(jù)卡爾曼秩判據(jù)，rank[-rFr-F2rF3r-F4rF5r]=6，rank[-rnFrn-F2rnF3rn-F4rnF5rn]=6．

這說(shuō)明，定理2也適用于其他可進(jìn)行三部圖劃分的拓?fù)鋱D．

5 結(jié) 論

本文在領(lǐng)航者-跟隨者結(jié)構(gòu)的基礎(chǔ)上，研究了對(duì)抗網(wǎng)絡(luò)下的多智能體系統(tǒng)的能控性．本文將對(duì)抗作用引入到領(lǐng)航者-跟隨者拓?fù)浣Y(jié)構(gòu)中，對(duì)比協(xié)作網(wǎng)絡(luò)下的研究得出了對(duì)抗網(wǎng)絡(luò)下多智能體系統(tǒng)能控的兩個(gè)必要條件．此外，基于三部圖劃分下的Peterson圖，研究得出了關(guān)于負(fù)邊和領(lǐng)航者選擇的兩個(gè)條件下，對(duì)抗網(wǎng)絡(luò)與對(duì)應(yīng)的協(xié)作網(wǎng)絡(luò)下能控性的等價(jià)性，并在推導(dǎo)過(guò)程中給出了定量分析．之后的工作將在此基礎(chǔ)上對(duì)對(duì)抗網(wǎng)絡(luò)下的簡(jiǎn)單圖，例如路圖、星圖以及環(huán)圖等，進(jìn)行能控性分析．