網絡化分布式協作系統的最大同步

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

網絡化分布式協作系統的最大同步

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

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

網絡化系統；最大同步；分布式控制；有向圖；聯合連通

0 引言

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

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

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

1 數學描述

設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)表示所有結點的狀態，且滿足下面微分方程：

(2)

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

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

(3)

圖的所有結點在有限時間T>0關于χ取得了協同一致，當且僅當所有結點兩兩滿足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與聯合圖G=G1∪G2∪…∪Gm具有相同的頂點集V；聯合圖G的邊集為所有圖G1,G2,…,Gm邊集的并，邊的連接權重是對應的鏈接權重之和。如果它們的聯合圖G是連通的，則稱G1,G2,…,Gm為聯合連通的。

2 分布式網絡化系統的最大同步

基于有向網絡拓撲，考慮一個由n個智能體構成的一階網絡化系統，其動態方程描述為

(4)

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

(5)

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

(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連續時間網絡化系統(4)-(5)當t→∞時取得漸近同步，當且僅當

(7)

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

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

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

系統在時間段[tr,tr+1)內的動態方程可表示為

(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。

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

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

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

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

注3：基于有向切換網絡，由若干智能體構成的連續時間網絡化系統取得最大同步的充分條件為系統拓撲圖的集合在整個有限時間區間內為聯合強連通的。

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

3 實例分析

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

4 結論

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

[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]. 復雜系統與復雜性科學，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]宋莉，伍清河. 具有時延和不確定拓撲的二階多智能體系統的平均一致性[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]高彥平，姜同強，王雯,等. 二階多智能體系統的一致性分析[J]. 復雜系統與復雜性科學，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]. 復雜系統與復雜性科學，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] 王芳，陳鑫，何勇，等. 聯合連通條件下的二階多智能體系統有限時間一致性控制[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-)，男，山東濟南人，碩士研究生，主要研究領域為復雜網絡、多智能體編隊控制。

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

TP27

A