具有對抗關系和時變拓撲的耦合離散系統(tǒng)有界雙向同步

翟世東 劉佩 高輝

同步(一致)行為是生物、生態(tài)、工程和社會科學等領域中最普遍的群聚現(xiàn)象之一.在過去十幾年里,耦合系統(tǒng)中僅由局部交互引起的同步問題引起了大量研究者的關注[1-5].在自然和工程系統(tǒng)中,合作、競爭關系普遍存在,且很多實際系統(tǒng)同時存在合作與競爭關系,例如社會網(wǎng)絡[6]、存在合作與競爭的種群[7]、競爭性細胞神經(jīng)元[8]和個性化推薦[9].為了描述系統(tǒng)中的合作與競爭關系,研究者們引入了符號圖,其中正數(shù)邊表示合作關系,負數(shù)邊表示競爭關系.

目前,越來越多的研究人員開始利用符號圖來研究網(wǎng)絡中的各種群聚現(xiàn)象[10-16].在文獻[10]中,Altafini 研究了定義在符號圖上的一個積分器網(wǎng)絡,并得到了關于雙向一致的一些定理.這里的雙向一致表示所有的智能體都收斂到一個模量相等、符號不同的值.其中,作者假設符號圖是結構平衡的,即所有節(jié)點可以被分為兩個陣營,每個陣營內部是合作關系,兩個陣營之間是競爭關系.這個假設對雙向一致性結論的得出至關重要.文獻[10]的結論推廣到了更一般的線性多智能體系統(tǒng)[11-13],其中每個智能體都由一個線性時不變系統(tǒng)表示.例如對于有向圖上的積分器網(wǎng)絡,文獻[13]在符號圖含有生成樹的情況下得到了達到雙向一致的一些充分條件.很多研究者陸續(xù)對各種特定網(wǎng)絡展開了雙向同步問題研究,例如雙向聚集[14]、區(qū)間雙向一致[15]、含有時滯的雙向一致[16]等.基于壓縮性分析,文獻[17]研究了耦合非線性網(wǎng)絡的雙向同步問題.對于耦合離散系統(tǒng)構成的網(wǎng)絡,其雙向同步問題也受到了很多研究者的關注[18-19].對于更多的關于雙向同步的研究,可以參見綜述文獻[20-21].

在實際系統(tǒng)中,隨著時間的推移,網(wǎng)絡的拓撲結構可能會發(fā)生變化.而且,網(wǎng)絡所形成的符號圖可能不滿足結構平衡特性.例如,在社會網(wǎng)絡中,個體之間的關系可能會由合作(友誼)到競爭(敵意)變化,反之亦然;在多黨制的國家,很多成員經(jīng)常會從一個黨派轉向另一個黨派.當符號圖不滿足結構平衡性時,網(wǎng)絡不能達到雙向同步.在文獻[22]中,作者利用矩陣的最終為正性質,分別研究了連續(xù)和離散時間輿論動力學模型的動力學行為.當符號圖隨著時間變化的時候,網(wǎng)絡構成一個切換系統(tǒng).文獻[23-24]考慮了所有符號圖在結構上都是平衡的,且敵對陣營的成員隨著時間的推移是不變的情況.具體地,在文獻[23]中,作者得到了使非線性系統(tǒng)達到模同步的充分條件;在文獻[24]中,作者設計了一種牽引控制,使閉環(huán)系統(tǒng)實現(xiàn)雙向同步.如果這些符號圖中的節(jié)點隨著時間變化,那么雙向同步將不可能達到.

本文將研究含有對抗性關系和時變拓撲的耦合離散系統(tǒng)的有界雙向同步(Bounded bipartite synchronization,BBS)問題.考慮以下情形:1)在某些時刻,所有個體不能被分為兩個敵對陣營;2)雖然所有個體可以被劃分為兩個陣營.但所形成敵對陣營中的成員會隨時間改變.當情形1)和2)出現(xiàn)時,將這種耦合離散系統(tǒng)看成是一個特定網(wǎng)絡的擾動,在這個特定網(wǎng)絡中,所有的個體都可以被分成兩個敵對陣營,且二者中的成員隨著時間的推移會保持不變.在該特定網(wǎng)絡的所有符號圖都是連通的條件下,本文得到了使系統(tǒng)達到有界雙向同步的一些充分條件.最后,利用一個數(shù)值例子來說明所得結論的有效性.

本文符號說明如下:|x|表示實數(shù)x的絕對值,Z+表示正整數(shù)域,||y||表示向量y的范數(shù),IN表示N維單位矩陣,1N表示元素都為 1的N維列向量,運算符?表示Kronecker 積.對于矩陣A,符號λmin(A),λmax(A)分別表示矩陣A的最小特征值和最大特征值. diag{·}表示一個對角矩陣,sgn(·)代表符號函數(shù).如果對于每個固定的s,函數(shù)β(r,s)是嚴格遞增的且β(0,s)≡0,對于每個固定的r,函數(shù)β(r,s)是嚴格遞減的且 lims→∞β(r,s)=0,那么函數(shù)β(r,s)稱為 KL 類函數(shù).

1 問題描述

考慮包含N個離散系統(tǒng)的網(wǎng)絡

其中,i=1,2,···,N.xi∈Rn是第i個節(jié)點的狀態(tài),A,B是常數(shù)矩陣,ui(k)是控制輸入.假設網(wǎng)絡的拓撲在p個無向符號圖G(Ek)(符號圖定義見附錄A),k=1,2,···,p之間切換,其中切換信號是σ(k):Z+→P:={1,2,···,p},它是一個分段右連續(xù)的函數(shù).控制輸入ui(k)設計為

其中,K是一個需要設計的增益矩陣,eij是圖G(Ek)的邊值.令是σ(k)的切換時刻.存在正常數(shù)T＞1,使得ki+1-ki≥T,?i ≥0.

注1.網(wǎng)絡在切換信號下構成一個切換系統(tǒng).本文中要求存在正常數(shù)T＞1,使得ki+1-ki≥T,?i ≥0.這里的T＞1 可以看成是駐留時間.如果沒有駐留時間,那么在有限時間內可能會有無限次切換,對于系統(tǒng)的收斂性會有很大影響.

通常來說,如果符號圖結構平衡,那么其所有節(jié)點可以劃分為兩個敵對陣營,其中每個陣營中的個體之間的關系是合作的,屬于不同陣營的個體之間的關系是對立的.對于符號圖G(Ek),k=1,2,···,p,可能存在以下情況:1)雖然每一個符號圖都滿足結構平衡,即每個符號圖都可以劃分為兩個敵對陣營,但是每一個符號圖的兩個敵對陣營中的個體是不一樣的,例如在多黨派執(zhí)政的國家,一些個體隨著時間變化從一個陣營轉移到另一個陣營;2)可能存在某些不滿足結構平衡的符號圖.在這些情況下,網(wǎng)絡很難達到雙向同步.為了研究這兩種情況下的網(wǎng)絡的同步問題,將這些符號圖看成是某些特定結構平衡符號圖的擾動.具體地,假設符號圖G(Ek)的鄰接矩陣可以分為兩個鄰接矩陣,即其中,是關于符號圖G()的一個鄰接矩陣.把控制輸入(2)中的符號圖改為G(可以得到一個新的輸入

因此,由符號圖GEk形成的耦合系統(tǒng)(1)和(2)可以看成是由符號圖G()形成的耦合系統(tǒng)(1)和(3)的擾動.而且,假設符號圖G(),k=1,2,···,p的節(jié)點{1,2,···,N}可以劃分為兩個敵對陣營V1,V2,且存在一個符號矩陣Ψ(Ψ=diag{σ1,···,σN},σi∈{±1}),使得矩陣 ΨEˉkΨ,k=1,2,···,p都是非負矩陣.

接下來,本文將研究當控制輸入為式(2)時,網(wǎng)絡(1)將在何種條件下達到有界雙向同步.雙向同步和有界雙向同步的定義分別如下.

定義1.如果存在依賴于非零初始條件的函數(shù)ζ(k)≠=0,使得以下條件成立:limk→∞(xi(k)-ζ(k))=0,?i∈V1,limk→∞(xi(k)+ζ(k))=0,?i∈V2,那么控制輸入為式(3)的網(wǎng)絡(1)達到雙向同步.

定義2.如果滿足以下兩個條件,那么控制輸入為式(2)的網(wǎng)絡(1)達到有界雙向同步:1)網(wǎng)絡(1)在形式為式(3)的控制輸入下達到雙向同步;2)存在一個正常數(shù)ξ(依賴于非零初始條件),一個KL 類函數(shù)β(·,·)(依賴于圖G(Ek),k=1,2,···,p),使得||δ(k)||≤β(||δ(0)||,t)+ξ成立,其中δ(k)=x(k)-

2 主要結論

本節(jié)將研究以下兩種情形:1)在某些時刻,所有個體不能劃分為兩個敵對陣營;2)雖然所有個體可以劃分為兩個陣營,但形成的敵對陣營中的成員會隨時間改變.如果符號圖G(),k=1,2,···,p都是連通的,那么可以得到條件使得控制輸入為式(2)的網(wǎng)絡(1)達到有界雙向同步.為此,給出以下假設:

假設1.假設矩陣A的所有特征值是模為1 的半單特征值,即所有約當塊都是一維的.

進而,針對存在對抗關系和時變拓撲的耦合離散系統(tǒng),可以得到定理1.

定理1.考慮網(wǎng)絡(1),假定假設1 成立且符號圖G(),k=1,2,···,p連通.如果存在μ使得不等式(4)成立(其中 Δj=Lj-),

證明.選擇K=μBTPTPA,則控制輸入為式(2)的網(wǎng)絡(1)變?yōu)?/p>

其中,i=1,2,···,N.式(5)可以寫成如下所示的緊湊形式.

由于圖G(),k=1,2,···,p的節(jié)點{i=1,2,···,N}可劃分為兩個敵對陣營V1和V2,且圖G(),k=1,2,···,p是連通的,基于定理1[25],可知網(wǎng)絡(1)和(3)在任意切換信號下達到雙向同步.

令z(k)=(Ψ?P)x(k),則控制輸入為式(2)的網(wǎng)絡(1)可表示為

其中,不等式第1 部分可由條件(4)得到.由于圖G(),k=1,2,···,p是連通的,因而存在正交矩陣Qσ(k)∈RN×N,使得

其中,0＜θ＜1.所以下面的關系成立:

當式(16)成立時,式(15)成立.

從而得到控制輸入為式(2)的網(wǎng)絡(1)達到有界雙向同步.□

注2.由定理1 的證明過程可以看出,最終界為因此,為了使最終界比較小,可以選擇使‖x(0)‖很小或者α很大的初始條件.

注3.在定理1 中,假設矩陣A的所有特征值是模為1 的半單特征值,即所有約當塊都是一維的.在這種假設條件下,矩陣A是正交矩陣,即ATA=I.這時矩陣A是中立穩(wěn)定的.

3 數(shù)值例子

本節(jié)將給出一個數(shù)值例子來驗證所得結論的有效性.

例1.對于網(wǎng)絡(1),令N=4,其中矩陣A,B為

因為矩陣A是正交的,所以假設1 成立.定義切換信號σ(k)如式(21),其中s∈Z+.

假設有兩個無向圖G(Ei),i=1,2,如圖1 所示,圖G(E2)的節(jié)點不能劃分為兩個敵對陣營V1和V2.假設分別對應于圖2(a)和圖2(b).可知圖G(Eˉi),i=1,2 的節(jié)點能劃分為兩個敵對陣營V1={1,2},V2={3,4}.

圖1 無向圖G(Ei),i=1,2Fig.1 The undirected signed graphG(Ei),i=1,2

圖2 無向圖G(),i=1,2Fig.2 The undirected signed graphG(),i=1,2

對于圖G(),i=1,2,可選擇符號矩陣 Ψ=diag{1,1,-1,-1}使得 ΨΨ,k=1,2 是非負矩陣,根據(jù)其拉普拉斯矩陣

圖3 四智能體網(wǎng)絡在拓撲為圖2、切換信號為σ(k)時的時間演變過程Fig.3 Time evolution of 4-agent network with topologies in Fig.2 and switching signalσ(k)

圖4 四智能體網(wǎng)絡在拓撲為圖1、切換信號為σ(k)時的時間演變過程Fig.4 Time evolution of 4-agent network with topologies in Fig.1 and switching signalσ(k)

圖5 四智能體網(wǎng)絡在切換信號σ(k)下的范數(shù)誤差和終值Fig.5 Norm error of the 4-agent network with switching signalσ(k)

4 結論

當存在對抗關系和切換拓撲時,本文研究了耦合離散線性系統(tǒng)的同步問題.針對實際中可能存在的兩種情形,研究了耦合離散系統(tǒng)的有界雙向同步問題,得到了使閉環(huán)系統(tǒng)在任意切換信號下達到有界雙向同步的充分條件.數(shù)值仿真驗證了本文所得理論的正確性.本文的結論對于系統(tǒng)矩陣有一定的要求,后續(xù)工作將考慮更一般的情況.

附錄 A 符號圖

符號圖G(V,ε)由一個有限節(jié)點集和一個邊集組成,節(jié)點集記為V={1,2,···,N},邊集記為ε={(i,j):i≠j,i,j∈V}?V ×V.令E=(eij)是圖G的一個鄰接矩陣,利用G(E)來表示鄰接矩陣為E的符號圖,圖G(E)的拉普拉斯矩陣定義為L=Cr-E,其中由i到j的邊 (i,j)∈ε是有向邊,其中節(jié)點i,j分別稱為父節(jié)點和子節(jié)點.如果 (j,i),(i,j)∈ε,那么圖G(E)是無向圖.文中定義ε+={(i,j)|eij＞0},ε-={(i,j)|eij＜0},ε=ε+∪ε-.由不同節(jié)點 (i1,i2),(i2,i3),···,(il-1,il)所組成的邊的一個序列稱為路徑(路徑長度為l-1).若符號圖中的任意兩個不同節(jié)點之間存在路徑,則該圖稱為是強連通的.已知包含相同節(jié)點集的p個符號圖G(Ek)= (V,εk,Ek),k=1,2,···,p,則在切換信號σ(k)下,可以定義一個時變符號圖,即G(Eσ(k))= (V,εσ(k),Eσ(k)).

附錄B 預備引理

考慮如下差分方程

其中,x∈Rn,f:Rn→Rn是連續(xù)的,f(0)=0.

引理1.令V:Rn→Rn是一個連續(xù)函數(shù),且滿足

其中,?k ≥0,?x∈Rn,c,c1,c2,c3是正常數(shù).那么,對每個初始狀態(tài)x(0),存在正常數(shù)ρ≥1,0＜γ＜1,有T≥0 (取決于x(0)和c),使得系統(tǒng)(B1)的解滿足

證明.本引理證明類似于定理4.18[26]的證明.令Ωc={x∈Rn|V(x)≤c},若初始x(0)∈Ω,則系統(tǒng) (B1)的解依賴于 Ωc,這是因為V(x(k))在邊界上是負的.對于 Rn-Ωc內部的某個解,令T是它進入 Ωc的起始時刻,則對于所有的k∈[0,T]∩Z+,有下式成立:

又由于V(x(k))≥0,易得c3/c2＜1.所以(1-c3/c2)＜1.可以得到