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

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

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

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

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

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

0 引言

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

網(wǎng)絡化系統(tǒng)的一致性問題是分布式協(xié)同控制的一個重要研究方向[1-4]。所謂一致性是指隨著時間的演化，自主體通過相互作用、相互協(xié)調使得系統(tǒng)運動達到同步。文獻[5]研究了聯(lián)合連通條件下一階時滯多智能體系統(tǒng)的一致性問題，并采用Lyapunov-Krasovskii 泛函和矛盾分析法對系統(tǒng)進行了收斂性分析。在系統(tǒng)同時具有變時延和系統(tǒng)不確定性的情況下，文獻[6]研究了一階多智能體系統(tǒng)的魯棒一致性問題。文獻[7]研究了有向網(wǎng)絡中固定拓撲和切換拓撲兩種情況下一階時滯多智能體系統(tǒng)的一致性問題，提出了具有不確定拓撲的平均一致性控制算法。文獻[8]研究了具有時延和不確定拓撲的二階多智能體系統(tǒng)的平均一致性問題，在通信拓撲為聯(lián)合連通的情況下，利用Lyapunov-Krasovskii方法，以線性矩陣不等式的形式給出了系統(tǒng)達到平均一致性的充分條件。文獻[9]研究了二階連續(xù)多智能體系統(tǒng)的一致性問題，利用離散化和狀態(tài)變換的方法，將一致性問題轉化為了一系列矩陣的Schur穩(wěn)定性問題，并得到了一致性成立的充要條件。文獻[10]研究了具有通訊時延的分數(shù)階多智能體系統(tǒng)的一致性問題，應用分數(shù)階系統(tǒng)的Laplace變換和頻域理對系統(tǒng)進行了收斂性分析。

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

1 數(shù)學描述

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

L=D-A∈Rn×n

(1)

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

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

(2)

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

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

(3)

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

定義1[16]樹為一種特殊的圖，除了根結點外，每個結點僅有一個父結點。如果一個圖的生成子圖是樹，稱該子圖為生成樹。

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

定義3[18]設拓撲圖Tri=0與聯(lián)合圖G=G1∪G2∪…∪Gm具有相同的頂點集V；聯(lián)合圖G的邊集為所有圖G1,G2,…,Gm邊集的并，邊的連接權重是對應的鏈接權重之和。如果它們的聯(lián)合圖G是連通的，則稱G1,G2,…,Gm為聯(lián)合連通的。

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

基于有向網(wǎng)絡拓撲，考慮一個由n個智能體構成的一階網(wǎng)絡化系統(tǒng)，其動態(tài)方程描述為

(4)

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

(5)

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

(6)

引理1[17]如果一個有向圖的集合{Gt1,Gt2,…,Gtm}的并存在一棵生成樹，則矩陣積e-LtmΔtm…e-Lt2Δt2e-Lt1Δt1為SIA的，其中Ltd為對應于每個有向拓撲圖Gtd的Laplacian矩陣，Δtd>0,d∈{1,2,…,m}。

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

(7)

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

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

證明：根據(jù)上述分析，可知在有限個不重疊的時間間隔[tr,tr+1)內的通信拓撲結構保持不變。令σ(t)[0,∞)→{1,2,…,m}是一個切換信號，m為總拓撲數(shù). 記系統(tǒng)通信拓撲圖為Gσ(tr)，且Gσ(tr)相應的Laplacian矩陣用Lσ(tr)表示。

系統(tǒng)在時間段[tr,tr+1)內的動態(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。

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

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

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

注2：本文結論是基于強連通的有向網(wǎng)絡，對于一般的有向網(wǎng)絡該結論并不一定成立。盡管基于有向拓撲的所有智能體組成的通信拓撲圖集合的并存在一顆生成樹，并不能保證其生成樹的根節(jié)點為網(wǎng)絡化系統(tǒng)的全局最大狀態(tài)，即不能保證所有智能體取得全局最大同步。 假定有向網(wǎng)絡為強連通的，則能夠使網(wǎng)絡化系統(tǒng)的全局最大狀態(tài)作為生成樹的根節(jié)點，也就保證了所有智能體取得了全局最大同步。

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

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

3 實例分析

針對動態(tài)切換拓撲，考慮如下互連拓撲圖。圖3的4個互連圖均為非連通的，均不存在生成樹，但它們的并為強連通的，且存在著一棵生成樹。系統(tǒng)的拓撲在圖3中的4個子拓撲下切換，各智能體的初始狀態(tài)取為x(0)=[54 686.57]。假定互連拓撲圖在時刻t=kT,k=0,1,…,在圖4集合中隨機地切換，T取為0.5秒。圖5為系統(tǒng)在15秒計算機仿真時間內的運動軌跡，其中采樣間隔為0.1s。可見基于有向切換網(wǎng)絡，各智能體的狀態(tài)漸近收斂到了其狀態(tài)最大值，即取得了全局最大同步。

4 結論

本文提出了一種應用個體局部信息的分布式控制算法，在控制器中引入了動態(tài)參數(shù)，有效地解決了有向網(wǎng)絡的全局最大同步問題。基于固定拓撲的強連通有向網(wǎng)絡，具有動態(tài)參數(shù)的控制協(xié)議保證了分布式系統(tǒng)的全局最大同步。有向拓撲網(wǎng)絡化系統(tǒng)的強連通性及控制器動態(tài)參數(shù)的設計是系統(tǒng)實現(xiàn)收斂性的關鍵。二階系統(tǒng)及時滯拓撲情形有待進一步研究。

[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]曾耀武，馮偉. 具有時滯和不確定性多智能體魯棒一致性研究[J]. 復雜系統(tǒng)與復雜性科學，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]宋莉，伍清河. 具有時延和不確定拓撲的二階多智能體系統(tǒng)的平均一致性[J]. 控制理論與應用，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]高彥平，姜同強，王雯,等. 二階多智能體系統(tǒng)的一致性分析[J]. 復雜系統(tǒng)與復雜性科學，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] 楊洪勇，徐邦海，劉飛,等. 分數(shù)階多智能體系統(tǒng)的時延一致性[J]. 復雜系統(tǒng)與復雜性科學，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)有限時間一致性控制[J]. 控制理論與應用，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.

(責任編輯 李進)

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

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

王付永(1990-)，男，山東濟南人，碩士研究生，主要研究領域為復雜網(wǎng)絡、多智能體編隊控制。

楊洪勇(1967-)，男，山東德州人，博士，教授，主要研究領域為網(wǎng)絡應用技術、多智能體編隊控制、復雜網(wǎng)絡控制、非線性系統(tǒng)控制等。

TP27

A