李英楨，紀(jì)志堅(jiān)，劉 帥，楊儀龍

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

0 引言

多智能體系統(tǒng)研究的熱點(diǎn)問(wèn)題是其一致性，一致性是一種普遍的群集行為，在自然界中，魚(yú)群聚集、鳥(niǎo)類遷徙及螢火蟲(chóng)同時(shí)閃光；在人類社會(huì)中，掌聲的同步及人類生物振蕩器的同步都可以歸納為一致性問(wèn)題。一致性是多智能體實(shí)現(xiàn)協(xié)同合作共同完成任務(wù)的基礎(chǔ)，其在包括群集、分布式計(jì)算、傳感器網(wǎng)絡(luò)及編隊(duì)控制等許多領(lǐng)域都有廣泛應(yīng)用，如機(jī)器人編隊(duì)控制、無(wú)人機(jī)協(xié)調(diào)控制以及人造衛(wèi)星控制等。目前關(guān)于一致性的研究大多基于個(gè)體間的合作關(guān)系，然而在實(shí)際的問(wèn)題中，如社會(huì)學(xué)，飛機(jī)編隊(duì)，個(gè)體間除了合作關(guān)系，還常常存在競(jìng)爭(zhēng)關(guān)系。關(guān)于多智能體之間的合作關(guān)系，最初R.Olfati-Saber在文獻(xiàn)[1]中構(gòu)造了基礎(chǔ)一致性協(xié)議，在連通無(wú)向圖下研究了平均一致性問(wèn)題。之后W.Ren和R.W.Bread在文獻(xiàn)[2]中提到一個(gè)解決一般一致性問(wèn)題的充分必要條件是相互作用的有向圖存在一個(gè)生成樹(shù)。關(guān)于多智能體之間的競(jìng)爭(zhēng)關(guān)系，S.Ermon等人[3]提及的對(duì)于自治網(wǎng)絡(luò)在工程應(yīng)用中的事實(shí)估計(jì)的情況，這種關(guān)系可以用符號(hào)圖表示，即圖中邊的權(quán)重可以是負(fù)的，其中正權(quán)表示智能體間的合作關(guān)系，負(fù)權(quán)表示智能體間的競(jìng)爭(zhēng)關(guān)系。關(guān)于正負(fù)混合權(quán)重的情形，C.Altanfini在文獻(xiàn)[4]中研究了關(guān)于連通符號(hào)圖(或強(qiáng)連通符號(hào)圖)的二分一致性問(wèn)題，并證明了在結(jié)構(gòu)平衡的符號(hào)(有向)圖下，基礎(chǔ)一致性協(xié)議能夠解決二分一致性問(wèn)題。之后Zhang等[5]研究了系統(tǒng)達(dá)到二分一致性的條件，討論了二分一致性和一般一致性之間的等價(jià)關(guān)系，擴(kuò)展了基于黎卡提方程的協(xié)同跟蹤控制器以解決二分一致性問(wèn)題。

上述關(guān)于二分一致性的結(jié)論都是以節(jié)點(diǎn)動(dòng)態(tài)來(lái)描述，但是在現(xiàn)實(shí)生活中，有很多物體，例如道路，電線，甚至個(gè)體間的相互關(guān)系和作用的實(shí)體等并不能簡(jiǎn)單地用通常的節(jié)點(diǎn)動(dòng)態(tài)來(lái)描述，而是用邊動(dòng)態(tài)來(lái)描述。拿交通網(wǎng)絡(luò)來(lái)舉例，用邊動(dòng)態(tài)來(lái)描述更合理準(zhǔn)確，具體而言，對(duì)于單行道，用有向邊來(lái)表示，對(duì)于雙行道，用無(wú)向邊或雙向邊表示，我們期望交通網(wǎng)絡(luò)中不存在一些道路擁堵而一些道路冷清的情況，使所有道路的交通狀況能達(dá)成一致，即道路交通網(wǎng)達(dá)成邊動(dòng)態(tài)一致性。關(guān)于邊動(dòng)態(tài)的研究目前很少，Wang等人[6]研究了一階多智能體系統(tǒng)的邊動(dòng)態(tài)一致性問(wèn)題，在有向圖下建立了邊動(dòng)態(tài)一致性協(xié)議，利用了線圖這個(gè)工具，解決邊動(dòng)態(tài)問(wèn)題，并且證實(shí)了在強(qiáng)連通有向圖下，多智能體系統(tǒng)能實(shí)現(xiàn)邊動(dòng)態(tài)一致性。

此外，實(shí)際問(wèn)題中智能體之間的信息傳遞往往會(huì)存在通訊時(shí)滯，導(dǎo)致系統(tǒng)的動(dòng)態(tài)特性變差甚至導(dǎo)致系統(tǒng)無(wú)法實(shí)現(xiàn)穩(wěn)定性，因而針對(duì)含有通訊時(shí)滯的多智能體系統(tǒng)的問(wèn)題研究也受到了廣泛關(guān)注。2004年，Saber等人[7]研究了一階動(dòng)態(tài)系統(tǒng)在均勻固定交流時(shí)滯下有向網(wǎng)絡(luò)的平均一致性問(wèn)題。之后，Du在[8]中研究了一階多智能體系統(tǒng)在具有正負(fù)混合權(quán)及通訊時(shí)滯的無(wú)向拓?fù)湎碌亩忠恢滦詥?wèn)題，構(gòu)造了含不均勻時(shí)滯的一致性協(xié)議，給出了時(shí)滯多智能體系統(tǒng)實(shí)現(xiàn)二分一致性的結(jié)論。Li等人[9]研究了無(wú)向拓?fù)湎乱活惡泄潭〞r(shí)滯的二階多智能體系統(tǒng)的二分一致性問(wèn)題，其中對(duì)于含有交流時(shí)滯情形下的一致性及二分一致性問(wèn)題的分析，借助了一類等價(jià)變換，將系統(tǒng)的一致性問(wèn)題等價(jià)為穩(wěn)定性問(wèn)題。2018年，Tian在[10]中研究了二階時(shí)滯系統(tǒng)正負(fù)混合加權(quán)的系統(tǒng)二分一致性問(wèn)題，利用矩陣論的方法對(duì)二階系統(tǒng)進(jìn)行降階處理，簡(jiǎn)化分析。上述關(guān)于符號(hào)圖下系統(tǒng)的二分一致性都是在結(jié)構(gòu)平衡這個(gè)條件下得到，2017年Jiang在[11]中對(duì)非結(jié)構(gòu)平衡條件下系統(tǒng)的二分一致性進(jìn)行了研究，并設(shè)計(jì)了不需要整個(gè)拓?fù)鋱D信息的完全分布式控制器。目前對(duì)時(shí)滯系統(tǒng)的穩(wěn)定性分析主要有兩類方法，一類是頻域方法，如[12]、[13]，主要研究系統(tǒng)傳遞函數(shù)，一類是時(shí)域方法，如[14]、[15]，主要研究系統(tǒng)狀態(tài)方程。對(duì)于含不均勻時(shí)滯的多智能體系統(tǒng)，通常采用時(shí)域法利用Lyapunov穩(wěn)定性理論進(jìn)行處理。其中[16]詳細(xì)說(shuō)明了Matlab中的LMI(線性矩陣不等式)工具箱，據(jù)此可以解決由Lyapunov方程產(chǎn)生的線性矩陣不等式的求解問(wèn)題。

在上述工作的基礎(chǔ)上，本文基于邊動(dòng)態(tài)重新設(shè)計(jì)了一階和二階系統(tǒng)模型的二分一致性協(xié)議，使系統(tǒng)在實(shí)現(xiàn)二分一致性時(shí)系統(tǒng)各邊狀態(tài)趨于模相等。在考慮邊動(dòng)態(tài)時(shí)，利用線圖這一工具，將系統(tǒng)模型的邊動(dòng)態(tài)轉(zhuǎn)化為節(jié)點(diǎn)動(dòng)態(tài)，之后在研究二分一致性問(wèn)題時(shí)利用規(guī)范變換將其等價(jià)為普通的一致性問(wèn)題，并通過(guò)矩陣變換將多智能體系統(tǒng)的一致性問(wèn)題等價(jià)為穩(wěn)定性問(wèn)題，利用邊與節(jié)點(diǎn)之間的轉(zhuǎn)化關(guān)系分別得到一階、二階系統(tǒng)實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性的充分條件。與[4]不同，由于在實(shí)際多智能體網(wǎng)絡(luò)中，信息在傳遞過(guò)程中存在著不同的損耗和時(shí)滯，因此，本文在上述邊動(dòng)態(tài)二分一致性的基礎(chǔ)上，進(jìn)一步在協(xié)議中加入了不均勻的通訊時(shí)滯。在解決含時(shí)滯系統(tǒng)的二分一致性問(wèn)題時(shí)，在上述穩(wěn)定性問(wèn)題的基礎(chǔ)上，利用Lyapunov漸近穩(wěn)定性理論，構(gòu)造含時(shí)滯信息的Lyapunov-Krasovskii泛涵，并對(duì)泛函進(jìn)行求導(dǎo)，在求解Lyapunov-Krasovskii泛涵時(shí)，本文利用Matlab中的LMI工具箱對(duì)其進(jìn)行處理，利用gevp求解器解出滿足系統(tǒng)穩(wěn)定時(shí)的最大通訊時(shí)滯，進(jìn)一步得到含時(shí)滯多智能體系統(tǒng)實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性的充分條件。

本文的結(jié)構(gòu)如下安排：第2節(jié)介紹了線圖、結(jié)構(gòu)平衡等相關(guān)圖論知識(shí)以及邊動(dòng)態(tài)下的一階(二階)系統(tǒng)的二分一致性協(xié)議；第3節(jié)給出了關(guān)于一階(二階)系統(tǒng)關(guān)于二分一致性的結(jié)論及證明；第4節(jié)針對(duì)上章結(jié)論分別進(jìn)行了仿真，并給出了仿真結(jié)果；第5節(jié)總結(jié)了本文所做工作。

1 預(yù)備知識(shí)

1.1 圖論

1.1.1 結(jié)構(gòu)平衡

定義1結(jié)構(gòu)平衡：如果強(qiáng)連通的有向圖的所有的環(huán)都是正的，那么它是結(jié)構(gòu)平衡的。換一種說(shuō)法，如果強(qiáng)連通的有向圖的節(jié)點(diǎn)都可以被分為V1,V2，其中V1∪V2=V,V1∩V2=φ且aij≥0,?i,j∈Vp,(p∈{1,2}),aij≤0,?i∈Vp,j∈Vq,(p,q∈(1,2),p≠q)，則其是結(jié)構(gòu)平衡的。否則，稱為結(jié)構(gòu)不平衡。

引理1[4]當(dāng)且僅當(dāng)以下等式成立，對(duì)邊符號(hào)對(duì)稱的強(qiáng)連通有符號(hào)的有向圖G(A)結(jié)構(gòu)平衡：

1)G(A)的所有有向環(huán)均為正；

2)?D使得DAD所有的元素都是正的；

3)0是L的特征值。

推論1當(dāng)且僅當(dāng)0是拉普拉斯矩陣L的單特征值，也就是說(shuō)rank(L)=n-1，對(duì)邊符號(hào)對(duì)稱的強(qiáng)連通的有符號(hào)有向圖G(A)是結(jié)構(gòu)平衡的。

1.1.2 線圖

n個(gè)節(jié)點(diǎn)m條邊的有向圖G={V,E,A}，其線圖L(G)定義為[6]：

1)L(G)中的節(jié)點(diǎn)(i,j)對(duì)應(yīng)于G中的有向邊(i,j)；

2)對(duì)于G的節(jié)點(diǎn)i，在線圖L(G)中其入邊(i,j)與其出邊(k,i)相鄰，其中i,j,k=1,2,…,n。

值得注意的是，我們?cè)诜?hào)的有向圖及其線圖中有以下規(guī)則：

1)從原始圖的負(fù)加權(quán)入邊生成的線圖中的邊取負(fù)權(quán)重；

2)從原始圖的正加權(quán)入邊生成的線圖中的邊取正權(quán)重。

注：虛線表示負(fù)邊，實(shí)線表示正邊圖1 原始有向拓?fù)鋱D和邊轉(zhuǎn)化為節(jié)點(diǎn)后的線圖

關(guān)于原始拓?fù)鋱D及其線圖有如下引理：

引理2[10]如果有向圖G包含超過(guò)一個(gè)節(jié)點(diǎn)且是強(qiáng)連通的，則其線圖L(G)也是強(qiáng)連通的。

引理3[10]當(dāng)且僅當(dāng)G是結(jié)構(gòu)平衡的，對(duì)于強(qiáng)連通的對(duì)邊符號(hào)對(duì)稱有符號(hào)有向圖G，其線圖L(G)是結(jié)構(gòu)平衡的。

1.2 一致性協(xié)議

假設(shè)多智能體系統(tǒng)有n個(gè)多智能體，這n個(gè)多智能之間有M個(gè)邊，用邊動(dòng)態(tài)來(lái)表示多智能體之間的連接關(guān)系：

(1)

(2)

上述(1)為一階系統(tǒng)模型，(2)為二階系統(tǒng)模型，其中xij(t)∈R表示邊ij的狀態(tài)，vij(t)∈R表示邊ij的速度，uij(t)∈R表示邊ij的控制協(xié)議或輸入。為了方便描述，下面的敘述中在不引起混淆的情況下省略時(shí)間變量t，例如uij(t)寫成uij。

(3)

其中，c為任意常數(shù)，則稱該系統(tǒng)可以實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性。

對(duì)于系統(tǒng)(2)，其實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性時(shí)，各邊狀態(tài)如下：

(4)

對(duì)于二分一致性問(wèn)題(3)、(4)，在多智能體系統(tǒng)(1)、(2)不受通訊時(shí)滯影響的情況下，考慮其一致性控制協(xié)議分別為：

(5)

(6)

(7)

基于L′=[l′ij]M×M=C′-A′可知，將協(xié)議(5)、(6)分別用于系統(tǒng)(1)、(2)，可得：

(8)

(9)

在實(shí)際應(yīng)用中，各智能體間的信息傳輸往往不可避免地存在著通訊時(shí)滯。為了解決通訊時(shí)滯問(wèn)題，我們?cè)谝恢滦詤f(xié)議(5)、(6)中分別加入不均勻通訊時(shí)滯得到如下協(xié)議：

(10)

(11)

其中,τij表示第i個(gè)智能體獲得第j個(gè)智能體狀態(tài)信息時(shí)存在的通訊時(shí)滯,對(duì)于邊動(dòng)態(tài)系統(tǒng)，由于研究對(duì)象是圖的邊，而時(shí)滯信息主要存在于邊上，因此將原始拓?fù)鋱D轉(zhuǎn)化為線圖之后，其線圖的邊并不存在時(shí)滯，時(shí)滯信息儲(chǔ)存在線圖的節(jié)點(diǎn)中，我們做出如下定義:

定義2線圖中節(jié)點(diǎn)之間的時(shí)滯由發(fā)送信息的節(jié)點(diǎn)(即圖1b的非箭頭端節(jié)點(diǎn))確定。

由于不同智能體之間的通訊距離不一定相同，設(shè)多智能體系統(tǒng)中不同的通訊時(shí)滯個(gè)數(shù)為m，其中m≤M,記第k個(gè)通訊時(shí)滯為τk,k∈{1,2,…,m}，并且令0<τ1<τ2<…<τm≤d，其中，d為通訊時(shí)滯上界。那么將協(xié)議(9)，(10)分別用于系統(tǒng)(1)，(2)可得如下模型：

(12)

其中，N(k,i)={j|j≠i,τij=τk}。

2 主要結(jié)論

2.1 一階無(wú)時(shí)滯系統(tǒng)的邊動(dòng)態(tài)二分一致性

首先，引入一類正交矩陣D，其定義為:D={diag(σ),σ=[σ1,σ2,…,σn],σi∈{-1,1}}其中，D滿足DTD=DDT=I(單位陣)，并且D-1=D。

(13)

其中，常數(shù)c′滿足|c′|=|c|。

(14)

(15)

基于上述二分一致性條件(3)并根據(jù)引理4，容易看出一致性等價(jià)地表示為

(16)

即多智能體系統(tǒng)的一致性問(wèn)題可以轉(zhuǎn)換成一個(gè)關(guān)于Y的穩(wěn)定性問(wèn)題。由(9)可得：

(17)

(18)

(19)

(20)

(21)

根據(jù)上述描述，可以得到以下結(jié)論。

對(duì)H求導(dǎo)如下：

2.2 一階含時(shí)滯系統(tǒng)的邊動(dòng)態(tài)二分一致性

引理7[17]設(shè)x,y為任意n維實(shí)向量，H為n×n維可逆對(duì)稱矩陣，則下面的矩陣不等式成立：

2xTy≤xTH-1x+yTHy

1)S<0；

對(duì)一階多智能體系統(tǒng)存在通訊時(shí)滯的情形，類似于式(20)的建立，我們由式(11)可得：

(22)

定理2對(duì)于一個(gè)有向強(qiáng)連通圖G(A),如果G(A)是結(jié)構(gòu)平衡的。假設(shè)存在m個(gè)固定時(shí)滯τk，當(dāng)存在對(duì)稱正定矩陣P,Qk,Wk∈R(M-1)×(M-1)，k∈{1,2,…,M}使下面式子成立：

(23)

(24)

那么，一階含時(shí)滯多智能體系統(tǒng)能夠?qū)崿F(xiàn)邊動(dòng)態(tài)二分一致性。

證明：構(gòu)造Lyapunov-Krasovskii泛函：

V(t)=V1(t)+V2(t)+V3(t)

其中：

對(duì)V(t)求導(dǎo)可得：

由Newton-Leibniz公式和引理8可知：

得到：

其中,

(25)

(26)

2.3 二階無(wú)時(shí)滯系統(tǒng)的邊動(dòng)態(tài)二分一致性

如同一階系統(tǒng)，二階系統(tǒng)經(jīng)規(guī)范變換之后模型如下：

(27)

其中,

如一階模型分析可得如下結(jié)果：

(28)

(29)

(30)

2.4 二階含時(shí)滯系統(tǒng)的邊動(dòng)態(tài)二分一致性

將協(xié)議(10)代入到(28)中可得到如下系統(tǒng)模型：

(31)

類似一階系統(tǒng)，將上述模型轉(zhuǎn)換為式(20)的形式，則轉(zhuǎn)換之后的系統(tǒng)模型如下：

(32)

證明：

必要性：根據(jù)W的定義，顯然必要性成立，即二階系統(tǒng)實(shí)現(xiàn)二分一致性時(shí)降階系統(tǒng)的每個(gè)解均趨于0。

根據(jù)上述分析，可以將一致性的證明轉(zhuǎn)化為對(duì)轉(zhuǎn)換系統(tǒng)的漸近穩(wěn)定性的證明。

定理4在協(xié)議(10)下，對(duì)于給定的最大通訊時(shí)滯d，如果存在正定對(duì)稱矩陣P,Qk,Rk使下式成立：

(33)

那么系統(tǒng)(2)能實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性。其中：

(34)

證明：同上述一階系統(tǒng)，選取如下Lyapunov-Krasovskii泛函：

其中P,Qk,Rk定義如上文所述，分別求導(dǎo)后結(jié)果如下：

將上述泛函整理成矩陣形式：

(35)

圖2 無(wú)時(shí)滯情況下一階系統(tǒng)的邊動(dòng)態(tài)二分一致性情況

3 仿真

3.1 無(wú)時(shí)滯多智能體系統(tǒng)的邊動(dòng)態(tài)二分一致性仿真

考慮由5個(gè)節(jié)點(diǎn)構(gòu)成的多智能體系統(tǒng)，其有向拓?fù)溥B接如圖1a，其中實(shí)線表示個(gè)體之間的合作關(guān)系，權(quán)重取+1，虛線表示的是個(gè)體之間的競(jìng)爭(zhēng)關(guān)系，相應(yīng)的權(quán)重取-1。將其轉(zhuǎn)化為線圖之后，其對(duì)應(yīng)的邊動(dòng)態(tài)有向拓?fù)鋱D如圖1b所示，可以看出原始拓?fù)鋱D和線圖均為強(qiáng)連通，并且都是結(jié)構(gòu)平衡的?？紤]一階系統(tǒng)模型(1)，取各邊初始狀態(tài)為：x21=-3,x13=2,x34=1.5,x45=-2,x52=-4,x42=1。其仿真結(jié)果如圖2所示，可以看出當(dāng)系統(tǒng)中不存在時(shí)滯時(shí)，對(duì)邊符號(hào)對(duì)稱的一階強(qiáng)連通有向多智能體系統(tǒng)能實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性。進(jìn)一步考慮二階系統(tǒng)模型(2)，取各邊初始狀態(tài)為：x21=-3,x13=2,x34=1.5,x45=-2,x52=-4,x42=1，v21=2,v13=-1,v34=-3,v45=7,v52=6,v42=3。其仿真結(jié)果如圖3所示，可以看出二階強(qiáng)連通有向多智能體系統(tǒng)也可實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性。

圖3 無(wú)時(shí)滯情形下二階系統(tǒng)的邊動(dòng)態(tài)二分一致性仿真

3.2 含時(shí)滯多智能體系統(tǒng)的邊動(dòng)態(tài)二分一致性仿真

考慮將時(shí)滯加到多智能體系統(tǒng)中，對(duì)系統(tǒng)(1)進(jìn)行分析,利用控制協(xié)議(9),同樣選取圖1a為系統(tǒng)的拓?fù)浣Y(jié)構(gòu)，取系統(tǒng)的6個(gè)邊的初始狀態(tài)為：x21=-3,x13=2,x34=1.5,x45=-2,x52=-4,x42=1，根據(jù)式(22)和式(23)可求得通訊時(shí)滯上界d=0.555 3，在通訊時(shí)滯上界的范圍內(nèi)，我們選取τ21=0.455 3,τ13=0.355 3,τ34=0.255 3,τ45=0.155 3,τ52=0.055 3,τ42=0.555 3，作為對(duì)照，另選取一組時(shí)滯使其超過(guò)通訊時(shí)滯上界τ21=0.855 3,τ13=0.553,τ34=0.7,τ45=0.6,τ52=0.055 3,τ42=0.555 3，仿真結(jié)果如圖4所示，圖4a表明在不超過(guò)通訊時(shí)滯上界的前提下，對(duì)邊符號(hào)對(duì)稱的強(qiáng)連通有向圖加入時(shí)滯后依然可以實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性，圖3b表面當(dāng)邊緣時(shí)滯超過(guò)了通訊時(shí)滯上界后，系統(tǒng)無(wú)法再實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性。進(jìn)一步考慮二階系統(tǒng)模型(2),采用式(10)表示的控制協(xié)議，根據(jù)式(30)可求得通訊時(shí)滯上限d=0.146 0,在通訊時(shí)滯上界的范圍內(nèi)，我們選取τ21=0.146 0,τ13=0.106 0,τ34=0.046 0,τ45=0.086 0,τ52=0.076 0,τ42=0.026 0，仿真結(jié)果如圖5所示。

圖4 含時(shí)滯一階系統(tǒng)的邊動(dòng)態(tài)二分一致性仿真

圖5 含時(shí)滯二階系統(tǒng)的邊動(dòng)態(tài)二分一致性仿真

4 總結(jié)

本文基于邊動(dòng)態(tài)分別設(shè)計(jì)了無(wú)時(shí)滯和含時(shí)滯多智能體系統(tǒng)的二分一致性協(xié)議，研究了對(duì)邊符號(hào)對(duì)稱的強(qiáng)連通有向圖下的多智能體系統(tǒng)的邊動(dòng)態(tài)二分一致性問(wèn)題。分別針對(duì)一階和二階系統(tǒng)給出證明，得到系統(tǒng)在無(wú)時(shí)滯和含時(shí)滯情況下實(shí)現(xiàn)邊動(dòng)態(tài)二分一致性的充分條件，并利用Matlab進(jìn)行數(shù)值仿真驗(yàn)證方法的合理性。最后本文的結(jié)論仍在結(jié)構(gòu)平衡這個(gè)限制條件下得到，未來(lái)的研究重點(diǎn)是打破這個(gè)限制條件。