王付永，楊洪勇(魯東大學(xué)信息與電氣工程學(xué)院，山東 煙臺(tái) 264025)

網(wǎng)絡(luò)化分布式協(xié)作系統(tǒng)的最大同步

王付永，楊洪勇
(魯東大學(xué)信息與電氣工程學(xué)院，山東 煙臺(tái) 264025)

基于網(wǎng)絡(luò)化系統(tǒng)的拓?fù)浣Y(jié)構(gòu)特性，研究了分布式系統(tǒng)的最大同步問(wèn)題。提出了一種應(yīng)用個(gè)體局部信息的線性分布式控制協(xié)議。運(yùn)用現(xiàn)代控制理論、代數(shù)圖論和SIA等理論工具，對(duì)控制算法進(jìn)行了穩(wěn)定性分析，得到了網(wǎng)絡(luò)化系統(tǒng)的最大同步收斂條件。最后應(yīng)用仿真實(shí)驗(yàn)驗(yàn)證了所得結(jié)論的正確性。

網(wǎng)絡(luò)化系統(tǒng)；最大同步；分布式控制；有向圖；聯(lián)合連通

0 引言

近年來(lái)，分布式多智能體協(xié)同控制系統(tǒng)在移動(dòng)機(jī)器人編隊(duì)、無(wú)人航天器的協(xié)同控制、衛(wèi)星定位調(diào)姿和智能電網(wǎng)調(diào)度等軍事和民用領(lǐng)域得到了廣泛應(yīng)用，逐漸成為控制理論、應(yīng)用數(shù)學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域研究的熱點(diǎn)問(wèn)題。分布式協(xié)作問(wèn)題是多智能體或多機(jī)器人基于動(dòng)態(tài)網(wǎng)絡(luò)通過(guò)協(xié)調(diào)控制使其狀態(tài)取得決策值，例如多智能體通過(guò)相互協(xié)調(diào)使得運(yùn)動(dòng)速度或運(yùn)動(dòng)方向趨于同步，或者到達(dá)同一集合點(diǎn)等。

網(wǎng)絡(luò)化系統(tǒng)的一致性問(wèn)題是分布式協(xié)同控制的一個(gè)重要研究方向[1-4]。所謂一致性是指隨著時(shí)間的演化，自主體通過(guò)相互作用、相互協(xié)調(diào)使得系統(tǒng)運(yùn)動(dòng)達(dá)到同步。文獻(xiàn)[5]研究了聯(lián)合連通條件下一階時(shí)滯多智能體系統(tǒng)的一致性問(wèn)題，并采用Lyapunov-Krasovskii 泛函和矛盾分析法對(duì)系統(tǒng)進(jìn)行了收斂性分析。在系統(tǒng)同時(shí)具有變時(shí)延和系統(tǒng)不確定性的情況下，文獻(xiàn)[6]研究了一階多智能體系統(tǒng)的魯棒一致性問(wèn)題。文獻(xiàn)[7]研究了有向網(wǎng)絡(luò)中固定拓?fù)浜颓袚Q拓?fù)鋬煞N情況下一階時(shí)滯多智能體系統(tǒng)的一致性問(wèn)題，提出了具有不確定拓?fù)涞钠骄恢滦钥刂扑惴?。文獻(xiàn)[8]研究了具有時(shí)延和不確定拓?fù)涞亩A多智能體系統(tǒng)的平均一致性問(wèn)題，在通信拓?fù)錇槁?lián)合連通的情況下，利用Lyapunov-Krasovskii方法，以線性矩陣不等式的形式給出了系統(tǒng)達(dá)到平均一致性的充分條件。文獻(xiàn)[9]研究了二階連續(xù)多智能體系統(tǒng)的一致性問(wèn)題，利用離散化和狀態(tài)變換的方法，將一致性問(wèn)題轉(zhuǎn)化為了一系列矩陣的Schur穩(wěn)定性問(wèn)題，并得到了一致性成立的充要條件。文獻(xiàn)[10]研究了具有通訊時(shí)延的分?jǐn)?shù)階多智能體系統(tǒng)的一致性問(wèn)題，應(yīng)用分?jǐn)?shù)階系統(tǒng)的Laplace變換和頻域理對(duì)系統(tǒng)進(jìn)行了收斂性分析。

在某些實(shí)際應(yīng)用中，如最小時(shí)間交會(huì)、最優(yōu)目標(biāo)跟蹤、尋找最優(yōu)路徑等，一類特殊的一致性問(wèn)題，即最大一致性問(wèn)題，引起了人們的關(guān)注。在這種情況下，如果系統(tǒng)中所有成員最終都能達(dá)到同一狀態(tài)且為初始最大狀態(tài)，則稱系統(tǒng)能夠?qū)崿F(xiàn)最大一致性。文獻(xiàn)[11]針對(duì)動(dòng)態(tài)多智能體系統(tǒng)的一致性問(wèn)題，提出了一族單參數(shù)的有界分布式一致性算法，其算法包含了平均一致性和最小一致性兩種特殊的一致性算法。文獻(xiàn)[12]針對(duì)離散時(shí)間多智能體系統(tǒng)的一致性問(wèn)題，提出了最大一致性控制算法，并利用max-plus代數(shù)的方法分析了算法的收斂性。文獻(xiàn)[13-14]分別研究了時(shí)間相關(guān)和狀態(tài)相關(guān)的多智能體系統(tǒng)的一致性問(wèn)題，提出了一種結(jié)合平均一致性和最大一致性的廣義一致性控制算法。本文研究有向拓?fù)湎戮W(wǎng)絡(luò)化系統(tǒng)的最大同步問(wèn)題，本文與前面文獻(xiàn)不同之處在于提出了一種基于個(gè)體局部信息的分布式動(dòng)態(tài)控制算法，應(yīng)用代數(shù)圖論和SIA等理論工具，分析了有向網(wǎng)絡(luò)拓?fù)湎路植际蕉嘀悄荏w系統(tǒng)的最大一致性算法的收斂問(wèn)題。

1 數(shù)學(xué)描述

設(shè)G=(V,E,A)是n個(gè)結(jié)點(diǎn)的權(quán)重有向圖，V={v1,v2,…,vn}為一個(gè)頂點(diǎn)(或結(jié)點(diǎn))集合，E?V×V為一個(gè)邊的集合，A=[aij]為權(quán)重鄰接矩陣，其中eij=(vi,vj)∈E，vi,vj∈V；對(duì)于?i,j∈I={1,2,…,n}:i≠j,aij≥0；對(duì)于?i∈I,aii=0。結(jié)點(diǎn)vi的鄰接集合定義為Ni={j∈I:aij≥0}。定義D=diag{d1,d2,…,dn}∈Rn×n為圖G的度矩陣，其中di=∑j∈Niaij，i=1,2,…,n。權(quán)重圖G的Laplacian矩陣定義為

L=D-A∈Rn×n

(1)

由定義可知，1n是L零特征根的一個(gè)右特征向量。圖G的一條長(zhǎng)度為N的道路是一個(gè)不同頂點(diǎn){v1,v2,…,vN+1}的有序集合，且?i∈[1,N],(vi,vi+1)∈E。一個(gè)有向圖G稱為是強(qiáng)連通的，當(dāng)且僅當(dāng)圖G的任意兩個(gè)不同的頂點(diǎn)之間有一條有向通道。進(jìn)一步，如果G為強(qiáng)連通的，則rank(L)=n-1[15]。

設(shè)x=(x1,x2,…,xn)表示所有結(jié)點(diǎn)的狀態(tài)，且滿足下面微分方程：

(2)

假設(shè)χ:Rn→R為x的函數(shù)，其值y=χ(x)稱為決策值，其中最大同步?jīng)Q策值滿足

χ(x)=Max(x)=Max{x1,x2,…,xn}

(3)

圖的所有結(jié)點(diǎn)在有限時(shí)間T>0關(guān)于χ取得了協(xié)同一致，當(dāng)且僅當(dāng)所有結(jié)點(diǎn)兩兩滿足xi(T)=χ(x(0)),?i∈I。

定義1[16]樹(shù)為一種特殊的圖，除了根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)僅有一個(gè)父結(jié)點(diǎn)。如果一個(gè)圖的生成子圖是樹(shù)，稱該子圖為生成樹(shù)。

定義2[17]令Mn(R)表示所有n階實(shí)方陣的集合，如果矩陣A∈Mn(R)的所有元素均非負(fù)，則稱矩陣A為非負(fù)矩陣，記為A≥0。一個(gè)非負(fù)矩陣，如果其行和為+1，稱其為(行)隨機(jī)矩陣。一個(gè)隨機(jī)矩陣P，如果滿足limn→∞Pn=1nyΤ，其中y為某個(gè)列向量，1n=(1,1,…,1)Τ，則稱隨機(jī)矩陣P為非周期不可分的(SIA)。

定義3[18]設(shè)拓?fù)鋱DTri=0與聯(lián)合圖G=G1∪G2∪…∪Gm具有相同的頂點(diǎn)集V；聯(lián)合圖G的邊集為所有圖G1,G2,…,Gm邊集的并，邊的連接權(quán)重是對(duì)應(yīng)的鏈接權(quán)重之和。如果它們的聯(lián)合圖G是連通的，則稱G1,G2,…,Gm為聯(lián)合連通的。

2 分布式網(wǎng)絡(luò)化系統(tǒng)的最大同步

基于有向網(wǎng)絡(luò)拓?fù)洌紤]一個(gè)由n個(gè)智能體構(gòu)成的一階網(wǎng)絡(luò)化系統(tǒng)，其動(dòng)態(tài)方程描述為

(4)

其中xi(t)∈R,ui(t)∈R分別為第i個(gè)智能體的狀態(tài)和控制輸入。本文研究一階網(wǎng)絡(luò)化系統(tǒng)的最大同步問(wèn)題，假設(shè)其控制協(xié)議為

(5)

其中，αij(選擇系數(shù))的取值滿足如下定義：

(6)

引理1[17]如果一個(gè)有向圖的集合{Gt1,Gt2,…,Gtm}的并存在一棵生成樹(shù)，則矩陣積e-LtmΔtm…e-Lt2Δt2e-Lt1Δt1為SIA的，其中Ltd為對(duì)應(yīng)于每個(gè)有向拓?fù)鋱DGtd的Laplacian矩陣，Δtd>0,d∈{1,2,…,m}。

引理3連續(xù)時(shí)間網(wǎng)絡(luò)化系統(tǒng)(4)-(5)當(dāng)t→∞時(shí)取得漸近同步，當(dāng)且僅當(dāng)

(7)

其中，I表示單位矩陣，1n表示分量均為1的n×1列向量，y為一個(gè)n×1常向量，Φ(t,0)表示系統(tǒng)轉(zhuǎn)移矩陣，-L(σ1),-L(σ2),…表示系統(tǒng)在σ1,σ2…時(shí)的系數(shù)矩陣。

分析：本文研究具有固定拓?fù)涞木W(wǎng)絡(luò)化系統(tǒng)，由于控制協(xié)議中參數(shù)αij的動(dòng)態(tài)變化，造成了系統(tǒng)局部拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化，這樣就不能保證有向網(wǎng)絡(luò)為時(shí)不變的。為了更好地解決這一問(wèn)題，我們引入了聯(lián)合連通的概念及其相關(guān)理論。

證明：根據(jù)上述分析，可知在有限個(gè)不重疊的時(shí)間間隔[tr,tr+1)內(nèi)的通信拓?fù)浣Y(jié)構(gòu)保持不變。令σ(t)[0,∞)→{1,2,…,m}是一個(gè)切換信號(hào)，m為總拓?fù)鋽?shù). 記系統(tǒng)通信拓?fù)鋱D為Gσ(tr)，且Gσ(tr)相應(yīng)的Laplacian矩陣用Lσ(tr)表示。

系統(tǒng)在時(shí)間段[tr,tr+1)內(nèi)的動(dòng)態(tài)方程可表示為

(8)

x(1)=e-Lσ(t1)Δt1x(0)，x(2)=e-Lσ(t2)Δt2x(1),…,x(m)=e-Lσ(tm)Δtmx(m-1)

(9)

即有：

x(m)=e-Lσ(tm)Δtm…e-Lσ(t2)Δt2e-Lσ(t1)Δt1x(0)

(10)

其中，Δtd=td+1-td,d=1,…,m。

下面討論各智能個(gè)體與其鄰接成員關(guān)系的不同情形，并定性分析各種情況下各智能個(gè)體的動(dòng)態(tài)特性：

1)當(dāng)智能體i的鄰域內(nèi)任意智能體j的狀態(tài)xj均不大于其狀態(tài)xi時(shí)，由αij的定義可知αij=0，則有

注1：狀態(tài)轉(zhuǎn)移矩陣具有性質(zhì)Φ(tm,t0)=Φ(tm,tm-1)Φ(tm-1,tm-2)…Φ(t1,t0)，Φ(tr+1,tr)=e-Lσ(tr)Δtr，

注2：本文結(jié)論是基于強(qiáng)連通的有向網(wǎng)絡(luò)，對(duì)于一般的有向網(wǎng)絡(luò)該結(jié)論并不一定成立。盡管基于有向拓?fù)涞乃兄悄荏w組成的通信拓?fù)鋱D集合的并存在一顆生成樹(shù)，并不能保證其生成樹(shù)的根節(jié)點(diǎn)為網(wǎng)絡(luò)化系統(tǒng)的全局最大狀態(tài)，即不能保證所有智能體取得全局最大同步。 假定有向網(wǎng)絡(luò)為強(qiáng)連通的，則能夠使網(wǎng)絡(luò)化系統(tǒng)的全局最大狀態(tài)作為生成樹(shù)的根節(jié)點(diǎn)，也就保證了所有智能體取得了全局最大同步。

注3：基于有向切換網(wǎng)絡(luò)，由若干智能體構(gòu)成的連續(xù)時(shí)間網(wǎng)絡(luò)化系統(tǒng)取得最大同步的充分條件為系統(tǒng)拓?fù)鋱D的集合在整個(gè)有限時(shí)間區(qū)間內(nèi)為聯(lián)合強(qiáng)連通的。

推論1設(shè)t1,t2,…,tm為一個(gè)有限的時(shí)間序列，拓?fù)鋱DG(t)、權(quán)重因子aij(t)和選擇系數(shù)αij(t)在時(shí)間序列t1,t2,…,tm這些時(shí)間點(diǎn)切換。如果存在一個(gè)一致有界、不相重疊的時(shí)間區(qū)間的有限序列[tr,tr+1),r=0,1,…,m，t0為初始時(shí)刻，且有向圖的集合{Gi1,Gi2,…,Gim}?G在區(qū)間[t0,tm]聯(lián)合強(qiáng)連通，則基于動(dòng)態(tài)切換網(wǎng)絡(luò)的連續(xù)時(shí)間網(wǎng)絡(luò)化系統(tǒng)取得最大漸近同步。

3 實(shí)例分析

針對(duì)動(dòng)態(tài)切換拓?fù)?，考慮如下互連拓?fù)鋱D。圖3的4個(gè)互連圖均為非連通的，均不存在生成樹(shù)，但它們的并為強(qiáng)連通的，且存在著一棵生成樹(shù)。系統(tǒng)的拓?fù)湓趫D3中的4個(gè)子拓?fù)湎虑袚Q，各智能體的初始狀態(tài)取為x(0)=[54 686.57]。假定互連拓?fù)鋱D在時(shí)刻t=kT,k=0,1,…,在圖4集合中隨機(jī)地切換，T取為0.5秒。圖5為系統(tǒng)在15秒計(jì)算機(jī)仿真時(shí)間內(nèi)的運(yùn)動(dòng)軌跡，其中采樣間隔為0.1s?？梢?jiàn)基于有向切換網(wǎng)絡(luò)，各智能體的狀態(tài)漸近收斂到了其狀態(tài)最大值，即取得了全局最大同步。

4 結(jié)論

本文提出了一種應(yīng)用個(gè)體局部信息的分布式控制算法，在控制器中引入了動(dòng)態(tài)參數(shù)，有效地解決了有向網(wǎng)絡(luò)的全局最大同步問(wèn)題?；诠潭ㄍ?fù)涞膹?qiáng)連通有向網(wǎng)絡(luò)，具有動(dòng)態(tài)參數(shù)的控制協(xié)議保證了分布式系統(tǒng)的全局最大同步。有向拓?fù)渚W(wǎng)絡(luò)化系統(tǒng)的強(qiáng)連通性及控制器動(dòng)態(tài)參數(shù)的設(shè)計(jì)是系統(tǒng)實(shí)現(xiàn)收斂性的關(guān)鍵。二階系統(tǒng)及時(shí)滯拓?fù)淝樾斡写M(jìn)一步研究。

[1]Dai P P, Liu C L, Liu F. Consensus problem of heterogeneous multi-agent systems with time delay under fixed and switching topologies[J]. International Journal of Automation and Computing, 2014, 11(3): 340-346.

[2]Diao M, Duan Z S, Wen G H. Consensus tracking of linear multi-agent systems under networked observability conditions[J]. International Journal of Control, 2014, 87(8): 1478-1486.

[3]Jiang Y L, Liu J C, Wang S Q. Cooperative output feedback tracking control for multi-agent consensus with time-varying delays and switching topology[J]. Transactions of the Institute of Measurement and Control, 2015, 37(4): 550-559.

[4]Sakurama K, Nakano K. Necessary and sufficient condition for average consensus of networked multi-agent systems with heterogeneous time delays[J]. International Journal of Systems Science, 2015, 46(5): 818-830.

[5]Lin P, Jia Y. Multi-agent consensus with diverse time-delays and jointly-connected topologies[J]. Automatica, 2011, 47(4): 848-856.

[6]曾耀武，馮偉. 具有時(shí)滯和不確定性多智能體魯棒一致性研究[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2013，10(3)：75-80. Zeng Yaowu, Feng Wei. Robust consensus analysis of milti-agent systems with both time-delay and uncertainty[J]. Complex System and Complexity Science, 2013, 10(3), 75-80.

[7]Shang Y. Average consensus in multi-agent systems with uncertain topologies and multiple time-varying delays[J]. Linear Algebra and Its Applications, 2014, 459: 411-429.

[8]宋莉，伍清河. 具有時(shí)延和不確定拓?fù)涞亩A多智能體系統(tǒng)的平均一致性[J]. 控制理論與應(yīng)用，2013，30(8)：1047-1052. Song Li, Wu Qinghe. Average consensus of second-order multi-agent systems with time-delays and uncertain topologies[J]. Control Theory & Applications, 2013, 30(8): 1047-1052.

[9]高彥平，姜同強(qiáng)，王雯,等. 二階多智能體系統(tǒng)的一致性分析[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2014，11(4)：87-91. Gao Yanping, Jiang Tongqiang, Wang Wen, et al. Consensus analysis of second-order multi-agent systems[J]. Complex System and Complexity Science, 2014, 11(4), 87-91.

[10] 楊洪勇，徐邦海，劉飛,等. 分?jǐn)?shù)階多智能體系統(tǒng)的時(shí)延一致性[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2013，10(3)：81-85. Yang Hongyong, Xu Banghai, Liu Fei, et al. Consensus of fractional-order multi-agent systems with communication delay[J]. Complex System and Complexity Science, 2013, 10(3), 81-85.

[11] Tahbaz-Salehi A, Jadbabaie A. A one-parameter family of distributed consensus algorithms with boundary: From shortest paths to mean hitting times[C]∥ 2006 45th IEEE Conference on Decision and Control, San Dlego,CA,VSA. 2006: 4664-4669.

[12] Nejad B M, Attia S A, Raisch J. Max-consensus in a maxplus algebraic setting: The case of fixed communication topologies[C]. Int Symposium on Information, Communication and Automation Technologies, Sarajevo,Bosnia and Herzegovina.2009:1-7.

[13] Shi G, Johansson K H. Convergence of distributed averaging and maximizing algorithms part I: time-dependent graphs[C]. 2013 American Control Conference (ACC) Washington, DC, USA,2013.

[14] Shi G, Johansson K H. Convergence of distributed averaging and maximizing algorithms part II: state-dependent graphs[C]. 2013 American Control Conference (ACC) Washington, DC, USA, 2013.

[15] Olfati-Saber R, Murray R M. Consensus problems in networks of agents with switching topology and time-delays[J]. IEEE Transactions on Automatic Control, 2004, 49(9):1520-1533.

[16] Godsil C D, Royle G, Godsil C D. Algebraic Graph Theory[M]. New York: Springer, 2001.

[17] Ren W, Beard R W. Consensus seeking in multiagent systems under dynamically changing interaction topologies[J]. IEEE Transactions on Automatic Control, 2005, 50(5): 655-661.

[18] 王芳，陳鑫，何勇，等. 聯(lián)合連通條件下的二階多智能體系統(tǒng)有限時(shí)間一致性控制[J]. 控制理論與應(yīng)用，2014，31(7)：981-986. Wang Fang, Chen Xin, He Yong, et al. Finite-time consensus control of second-order multi-agent systems with jointly-connected topologies[J]. Control Theory & Applications, 2014, 31(7): 981-986.

(責(zé)任編輯 李進(jìn))

Maximum Synchronization of Networked Systems with Distributed Collaboration

WANG Fuyong, YANG Hongyong

(School of Information and Electrical Engineering, Ludong University, Yantai 264025,China)

Based on the topology feature of networked systems, maximum synchronization of distributed systems is studied. A distributed control protocol with individual′s local information is proposed. By using theoretical tools of modern control theory, algebraic graph theory and SIA, the stability of control algorithm is analyzed. The convergence condition of the maximum synchronization for networked systems is achieved. Finally, simulation examples are given to verify the correctness of the conclusion.

networked systems; maximum synchronization; distributed control protocol; directed graph; jointly-connected

10.13306/j.1672-3813.2016.04.009

2015-01-28；

2015-09-17

國(guó)家自然科學(xué)基金(61273152,61304052,51407088)；山東省自然科學(xué)基金(BS2015DX018)

王付永(1990-)，男，山東濟(jì)南人，碩士研究生，主要研究領(lǐng)域?yàn)閺?fù)雜網(wǎng)絡(luò)、多智能體編隊(duì)控制。

楊洪勇(1967-)，男，山東德州人，博士，教授，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)應(yīng)用技術(shù)、多智能體編隊(duì)控制、復(fù)雜網(wǎng)絡(luò)控制、非線性系統(tǒng)控制等。

TP27

A