基于NE結(jié)果的多智能體系統(tǒng)模型及其能控性

國俊豪，紀志堅

(青島大學自動化學院，山東 青島 266071)

0 引言

博弈論主要研究的是個體所做決策如何影響其他個體決策，其中最核心的概念是納什均衡(Nash Equilibrium)，納什均衡是指在個體之間在相互作用中達到一種均衡狀態(tài)，在此狀態(tài)下不會有個體通過單方面改變策略來增加收益。它有助于解釋人們是如何做出復雜決策的，并廣泛應用于國際關(guān)系的處理以及心理學的研究。在生活中，我們不難發(fā)現(xiàn)肯德基和麥當勞的選址位置總是相近的，也就是說肯德基的附近幾乎也會存在一家麥當勞。再比如星巴克附近總會有好幾家咖啡店，這是因為每家店的決策者總會選擇最優(yōu)的地理位置，以獲得最大的客流量，因此同一類型的商家會出現(xiàn)在相近的地方，而不是分散開來，便利不同位置的顧客。從經(jīng)濟學的角度來看，一旦有一家偏離了最優(yōu)位置，收益就會減少，因此達到了納什均衡。我們用圖1a表示上述情況，L1,L2附近有4條街道，L3,L4附近有兩條街道，其中L1,L2,L3,L4表示不同店鋪。由于納什均衡的存在，L1,L2都期望有四條街的客流量，因而都期望能在四條街的中心位置。同理L3,L4為了同時擁有第5條街和第6條街的客流量，最終也開在了相近的位置。如圖1b所示，L1,L2均與街道F1,F2,F3,F4相連接，因此有相同的選址。

圖1 等鄰居模型的圖論描述

基于上述情景，可以看到進行博弈并期望達到納什均衡的是Li,i=1,2,3,4，因此Li做出的決策對整個系統(tǒng)的狀態(tài)具有決定性的影響，我們將其稱作領(lǐng)導者，并在本文中只考慮領(lǐng)導者之間的博弈；客流量的多少取決于領(lǐng)導者的決策是否使自己受益，因此在這種情況下，將客流量視作跟隨者。在這里，領(lǐng)導者i的決策用rj(i)表示。在博弈論中，類似的情況還有很多，比如著名的囚徒困境，兩個囚徒會聽到警察所提供的相同的判刑規(guī)則，這時我們將進行博弈的囚徒們建模為領(lǐng)導者，警察(或警察提供的規(guī)則)為跟隨者，此時領(lǐng)導者們的跟隨者鄰居是相同的，所以囚徒們做出相同的決策，即都選擇了坦白罪行，并獲得了同樣的處罰，達到納什均衡的結(jié)果。

上述實際問題可以從圖論的角度進行刻畫，因此可以讓每個智能體遵循預先設(shè)定的協(xié)議，然而智能體顯著的特點是高智商性，因此智能體可以通過博弈來決策自己的行為。本文考慮既能夠遵循預先設(shè)定的協(xié)議又能自主做出決策的智能體?；谌缟纤觯疚慕⒘艘活愋碌哪Ｐ汀揉従幽Ｐ?，即在領(lǐng)導者—跟隨者架構(gòu)下，如果不同的領(lǐng)導者含有相同的鄰居集合(如上述情景所示，這里的鄰居僅由跟隨者構(gòu)成)，則這些領(lǐng)導者會有相同的決策，否則領(lǐng)導者做出不同的決策。在此模型下，由領(lǐng)導者自身的決策所形成的納什均衡能否改變系統(tǒng)的狀態(tài)是本文研究的主要問題，即對基于納什均衡的多智能體系統(tǒng)的能控性研究。與現(xiàn)有的對能控性問題的研究方法不同，我們不是從能控的秩判據(jù)等角度考慮問題，而是研究等鄰居模型與常用模型之間的能控性關(guān)系，來得到等鄰居模型能控的條件。

到目前為止，在研究系統(tǒng)的能控性時[1-7]，大部分內(nèi)容是通過如式(1)所示的這類系統(tǒng)得到信息拓撲結(jié)構(gòu)與系統(tǒng)的能控性之間的關(guān)系：

(1)

A,B分別為系統(tǒng)矩陣和輸入矩陣。值得注意的是，這些研究成果雖然均是基于系統(tǒng)(1)這樣的形式得到的，但是基于輸入矩陣的不同，得到的能控性結(jié)論也不同。因此，如果模型之間不能等價轉(zhuǎn)換，或者不清楚兩個模型等價的條件，那么在一個固定模型下得到的那些研究成果的價值也會減少。例如，在運用一些結(jié)論或者引理時，需要特別考慮該結(jié)論是在什么模型下產(chǎn)生的，如文獻[8]中所得到的能控圖、條件能控圖、不能控圖的劃分標準是在廣播控制下成立的，在其他模型下并不成立，所謂的廣播控制是指在不存在智能體—智能體通信的前提下，不加區(qū)別地向所有智能體發(fā)送相同的信號，從而控制多智能體系統(tǒng)；領(lǐng)導者—跟隨者網(wǎng)絡(luò)的可控性首先在文獻[9]中提出，Tanner等人在他們的模型下使用系統(tǒng)矩陣的頻譜分析來描述可控性；對于多領(lǐng)導者的情形，文獻[10]做了深入討論。在Tanner模型下，得到了關(guān)于能控性的大量研究結(jié)果，如在文獻[11]中提出了一個幾乎等價劃分的充要條件，闡明了拉普拉斯矩陣L與一般拉普拉斯矩陣Lπ的關(guān)系；文獻[12]研究了多智能體系統(tǒng)在等價劃分下的能控性問題。在多智能體系統(tǒng)中添加博弈的思想是十分重要的，張人仁[13]等人研究的是當一個宏觀觀測器給予決策后，剩下的智能體試圖優(yōu)化各自的目標函數(shù)以達到可能的納什均衡；馬晶瑩[14]等人研究了通過博弈來決定自己行為而不遵循任何預先設(shè)定的協(xié)議的智能體。而本文結(jié)合圖論以及多智能體系統(tǒng)的分布式協(xié)議研究了多智能體能夠自主地做出決策的情況。

在物理系統(tǒng)的數(shù)學建模中，人們總是面臨一個兩難的境地：建立一個精確的模型會使得操作困難，但是，如果建立一個相對容易操作的模型又會使實用性降低。綜合考慮，我們發(fā)現(xiàn)一方面每個個體都有自己的選擇、都有自己的算計、都期望自己利益最大化，因此多個個體構(gòu)成的多智能體系統(tǒng)，有考慮博奕和納什均衡的必要性，這是實際需求的驅(qū)使；另一方面，多智能體網(wǎng)絡(luò)系統(tǒng)的根本特點是包含了圖拓撲結(jié)構(gòu)和分布式協(xié)議。結(jié)合以上兩方面，本文建立了領(lǐng)導者—跟隨者框架下的等鄰居模型。該模型首次將納什均衡與圖的拓撲結(jié)構(gòu)建立聯(lián)系，使得納什均衡的結(jié)果更具直觀性：具體來說，本文建立的這類模型，是模擬了當不同的領(lǐng)導者含有相同的鄰居集合時，他們會做出相同的決策的情況，無論哪一個領(lǐng)導者改變自己的決策都會使自己的收益減少，因此領(lǐng)導者的決策是否相同，可以從圖的拓撲結(jié)構(gòu)上分析他們是否有相同的鄰居集；其次，該模型更具有實際應用價值，更便于問題的處理；不僅如此，我們發(fā)現(xiàn)該模型能夠轉(zhuǎn)化為常見模型的形式，因此，在研究其能控性問題時，我們不是從能控的秩判據(jù)等角度考慮問題，而是研究等鄰居模型與常用模型之間的能控性關(guān)系，來得到等鄰居模型能控的條件。

1 預備知識

本文將智能體視為頂點,智能體間的通信(或敏感關(guān)系)視為邊,則整個系統(tǒng)的通信關(guān)系可用一個圖G描述,稱G為系統(tǒng)的信息拓撲。若智能體之間的通信是雙向的,則用無向圖表示;否則,視為有向圖。本文研究連通的沒有權(quán)重的無向圖。若系統(tǒng)的信息拓撲不隨時間變化,即智能體之間的邊不會隨時間的變化增加或減少,則稱為固定拓撲。本文研究固定拓撲結(jié)構(gòu)下的能控性問題。

一個無向圖G由頂點集V(G)和邊集E(G)?V(G)×V(G)組成。若圖G為具有n個頂點的有限圖,則可以將V(G)和E(G)分別表示為V(G)={1,2,…,n},E(G)={(i,j)|i,j∈V(G)}。頂點i的鄰居集合定義為N(i)={j∈V(G)|(i,j)∈E(G)}。如果圖G中任2個不同的頂點i,j間都存在1條道路,則稱圖G是連通的。圖的鄰接矩陣定義為A(G)=[aij]n×n,其中

引理1[15]n維連續(xù)時間線性時不變系統(tǒng)(1)完全能控的充分必要條件為矩陣A不存在與B正交的非零左特征向量，即對矩陣A的所有特征值λi,i=1,2,…,n,使得同時滿足

αTA=λiαT,αTB=0

的左特征向量αT=0。

引理2[15]對n維連續(xù)時間線性時不變系統(tǒng)(1),構(gòu)造能控性判別矩陣:Q=[BABA2B…An-1B],則系統(tǒng)完全能控的充分必要條件為rank(Q)=n。

2 等鄰居模型

2.1 等鄰居模型

在等鄰居模型下，根據(jù)協(xié)議能夠彼此之間進行博弈后做出自己決策的智能體稱為領(lǐng)導者，我們將領(lǐng)導者i的決策用ri表示；僅僅遵循預先設(shè)定好的協(xié)議而無法進行博弈的智能體稱為跟隨者，跟隨者的狀態(tài)受到領(lǐng)導者的影響。值得注意的是：同一個領(lǐng)導者可以有多個不同的決策，這與廣播控制的控制輸入不同；如果不同的領(lǐng)導者含有相同的鄰居集合NF(i)，且NF(i)?VF,則這些領(lǐng)導者會做出相同的決策。

我們假定領(lǐng)導者的所有決策均不相等，這保證了同一領(lǐng)導者不會做出相同的決策。此時，n個智能體中的前m個智能體i表示為

(2)

(3)

即m個跟隨者遵循式(3)，剩下的n-m個領(lǐng)導者用式(4)表示

(4)

其中,ui為跟隨者遵循的協(xié)議，rj表示領(lǐng)導者i與彼此之間進行博弈后做出的決策。結(jié)合店鋪選址問題，可以發(fā)現(xiàn)如果領(lǐng)導者i1與i2滿足NF(i1)=NF(i2)時，則有rj(i1)=rj(i2)。

我們發(fā)現(xiàn)考慮能進行博弈的智能體依舊可以寫成如式(1)的形式，進而研究線性系統(tǒng)的能控性問題，如圖2c所示。

則上述問題可以轉(zhuǎn)換成

(5)

其中，L為拉普拉斯矩陣，B=[bij]∈Rn×(n-m)是二元矩陣，當節(jié)點i∈V與節(jié)點j∈VF有連接時，bij=1，否則bij=0，其中，VF是跟隨者的集合。例如圖2c中的節(jié)點1,2,4的跟隨者鄰居均為節(jié)點5,因此做出相同的決策r5,領(lǐng)導者節(jié)點1,3有相同的跟隨者鄰居6，因此也有相同的決策r6。值得注意的是，該模型說明同一領(lǐng)導者可以同時做出不同決策，這也是符合實際的，例如商家選址時所做的決策并非只受一類鄰居的影響，因此可以做出不同的決策。另外，在此模型中，基于納什均衡的存在，存在不同領(lǐng)導者自主做出相同的決策的情況。

通過對基于博弈的多智能體系統(tǒng)模型的轉(zhuǎn)換，可以看到這與常見的模型存在形式上的相似性，于是下面介紹了常見的模型，并從模型角度研究等鄰居模型的能控性。

2.2 常用模型[16]

在這類模型下，圖2中的部分節(jié)點(領(lǐng)導者)會被施加外部控制信號，而剩余節(jié)點(跟隨者)將會被該類節(jié)點及其自身拓撲結(jié)構(gòu)控制，如圖2a所示。其中每一個跟隨者的狀態(tài)由式(6)決定

圖2 三類模型在同一拓撲結(jié)構(gòu)下的表示

(6)

每一個領(lǐng)導者的狀態(tài)j∈VL由式(7)決定

(7)

向量x=[x1,…,xn]T∈Rn表示系統(tǒng)中所有的狀態(tài)，向量u=[u1,…,un-m]T∈Rn-m表示系統(tǒng)中的控制輸入，且這些控制輸入不相同。因此可將(6)和(7)表達成如式(8)的形式。

(8)

2.3 Tanner模型[17]

求得跟隨者的動力學方程為

(9)

在此類模型下，僅僅考慮領(lǐng)導者與跟隨者之間的連邊向跟隨者節(jié)點注入的控制信號，而不考慮領(lǐng)導者節(jié)點的狀態(tài)。

通過具體的例子，分析上述三類模型的不同：

如圖2所示，假定系統(tǒng)中只有兩個領(lǐng)導者。在由6個點構(gòu)成的固定拓撲結(jié)構(gòu)下，選擇節(jié)點5和6作為領(lǐng)導者，它們有相同的拉普拉斯矩陣，所以在不同的模型下，我們只需要考慮它們的輸入矩陣。由上述定義，分別得到他們的輸入矩陣

結(jié)果表明，這三類模型的輸入矩陣的形式(維數(shù),符號)并不相同。

綜上所述，等鄰居模型與常見模型的區(qū)別在于領(lǐng)導者個體能否通過博弈自主做出決策，我們考慮的是跟隨者鄰居相同的那部分領(lǐng)導者會做出相同的決策，以便達到納什均衡的狀態(tài)。特別地，我們發(fā)現(xiàn)等鄰居模型在形式上可以與系統(tǒng)(1)進行轉(zhuǎn)化，而系統(tǒng)(1)是多智能體系統(tǒng)的根本特點，因此我們研究不同模型與等鄰居模型的關(guān)系來得到在這類新模型下系統(tǒng)能控的條件。

3 主要結(jié)果

本文首次研究遵循一定協(xié)議并能自主做出決策的智能體。在此類系統(tǒng)下，能研究的問題很多，比如一致性問題、包圍控制問題、事件誘導控制等問題，而本文僅考慮系統(tǒng)的狀態(tài)是否可以通過領(lǐng)導者自主做出的決策來驅(qū)動任意給定的初始狀態(tài)到達任意的期望狀態(tài)，我們通過能控性的概念進行研究。

定義1(領(lǐng)導者—跟隨者架構(gòu)下的納什均衡狀態(tài))在等鄰居模型下，每個領(lǐng)導者都期望做出使自己利益最大化的決策，基于納什均衡的存在，進行博弈的領(lǐng)導者做出的決策相等，即rj(i1)=rj(i2)=…=rj(ik),其中ik表示領(lǐng)導者，此時系統(tǒng)形成的狀態(tài)我們稱為領(lǐng)導者—跟隨者架構(gòu)下的納什均衡狀態(tài)。

定義2系統(tǒng)(2)(3)(4)被稱為能控的，如果對于任意給定的初始狀態(tài)x(0)和終點狀態(tài)x(T),都存在領(lǐng)導者策略r(t),t∈[0,T],在此策略下，系統(tǒng)存在唯一的領(lǐng)導者—跟隨者架構(gòu)下的納什均衡狀態(tài)x*(t)=x(T)。

假設(shè)1假設(shè)在多智能體網(wǎng)絡(luò)系統(tǒng)中總是存在唯一的領(lǐng)導者—跟隨者架構(gòu)下的納什均衡狀態(tài)，此時領(lǐng)導者所做決策滿足等鄰居模型的條件。

由于等鄰居模型可以化為常見模型的形式，我們很自然地從研究不同模型之間的關(guān)系入手，研究在等鄰居模型下的能控性問題。由于一般模型中領(lǐng)導者不能自主做出決策，但是存在控制輸入u，因此在研究兩者的關(guān)系時，假定等鄰居模型中的決策r與這里的u等價；另外，等鄰居模型中，決定決策r是否相等的因素是跟隨者，因此等鄰居模型中的跟隨者在一般模型中表示的是領(lǐng)導者的角色。因此，在定理1中，我們提到的“在同一拓撲結(jié)構(gòu)下”意思是每個智能體的連接方式均相等，而且需要將領(lǐng)導者跟隨者的角色互換，從而研究兩類模型的關(guān)系。如圖2所示，a,c即表示“同一拓撲結(jié)構(gòu)”，雖然在a中，選擇節(jié)點5,6為領(lǐng)導者，在c中，選擇節(jié)點1,2,3,4為領(lǐng)導者，但是c中的領(lǐng)導者所做決策取決于節(jié)點5,6，因此在研究不同模型的關(guān)系時，我們稱節(jié)點5,6為領(lǐng)導者。此時稱a,c有相同的領(lǐng)導者5,6，也有相同的跟隨者1,2,3,4。

上述引理反映了智能體之間變換序號對整個系統(tǒng)的動力學方程的影響，即系統(tǒng)矩陣左乘并右乘對應的置換矩陣P,則輸入矩陣需要左乘對應的置換矩陣P。其實，改變節(jié)點的編號，圖并不會發(fā)生實質(zhì)改變，只是“人為定義的名稱”發(fā)生了改變。在(L,M)下，并不能保證前m個序號為跟隨者，而在Tanner模型中，一般令前m個智能體為跟隨者。因此，研究不同模型下的智能體狀態(tài)時，可運用該引理使之對應。

引理4[18](L,M)是不可控的，當且僅當L(G)的特征向量中對應于領(lǐng)導者的位置的元素均為零。

定理1(L,M)模型與Tanner模型、等鄰居模型在同一拓撲結(jié)構(gòu)下，有如下關(guān)系：

1)在一階系統(tǒng)下，(L,M)與(Lf,Lfl)等價。即(L,M)能控的充分必要條件是Tanner模型能控；

2)若假設(shè)1成立：

(1)當|VL|=1時，不妨設(shè)該領(lǐng)導者為n,若dn=n-1，則(L,M)能控的充分必要條件為(L,B)能控；若dn

(2)當|VL|>1時，若存在|N(p)|≠0,vip≠0,p∈VL,N(p)?VL,使得|N(p)|≠λi,i=1,2,…,n，則(L,M)是能控的，當且僅當(L,B)能控。

證明 1)要證(L,M)與Tanner模型等價，只要證明在相同的拓撲結(jié)構(gòu)下，當選擇相同的領(lǐng)導者時，兩模型有相同的能控性。

(2)當|VL|>1時，在上述條件下，若(L,M)不能控，則(L,B)不能控，其證明與(1)類似，在此省略。下面只需要證明若(L,M)能控，則(L,B)能控。

在研究(L,M)與等鄰居模型的關(guān)系時，我們得到兩模型能控性相同的充分必要條件，當該充分必要條件不成立時，我們發(fā)現(xiàn)兩個模型的能控性并不相同。如圖3a所示，選擇領(lǐng)導者集合為VL={6,7,8},此時不存在|N(p)|≠0,vip≠0,p∈VL,N(p)?VL,使得|N(p)|≠λi,i=1,2,…,8。此時，兩個模型的輸入矩陣分別為

計算得rank[Q(M)]=8,rank[Q(B)]=7,因此具有不同的能控性。因此，正是這個限制條件的存在，在一定程度上也會限制該多智能體系統(tǒng)模型推廣于實際應用。

例1如圖3b所示，其拉普拉斯矩陣及其特征值和特征向量分別為

圖3 選擇6,7,8為領(lǐng)導者的八點圖

推論1在定理1的2)(2)的條件下，(L,B)不能控的充分必要條件為存在L的一個特征向量vi,使vi對應的領(lǐng)導者的位置全為零。

證明：在定理1的2)(2)的條件下,(L,B)與(L,M)有相同的能控性，因此由引理4可得該結(jié)論成立。

4 結(jié)論和展望

本文基于納什均衡得到的結(jié)果建立了一類新的模型，即等鄰居模型，并分析了在這類模型下多智能體系統(tǒng)的能控性問題。我們先研究了一般性模型與Tanner模型之間的關(guān)系，發(fā)現(xiàn)在一階積分器下，兩個模型是等價的，即具有相同的能控性，進而我們研究了等鄰居模型與一般性模型的能控性關(guān)系，得到了等鄰居模型在固定條件下能夠與其他模型產(chǎn)生相同能控性的結(jié)論。接下來，我們計劃進一步研究在一般性的模型下得到的結(jié)論能否應用到等鄰居模型，或者添加合適的條件使得原有的研究成果在等鄰居模型下成立。另外，弱化定理1 2)中的條件，以增強該多智能體系統(tǒng)模型推廣于實際應用的可能性也是我們將要繼續(xù)完成的工作。