線性離散一致性系統均方偏差上界

竇全勝，厲玉蓉，姜平

(1. 山東工商學院計算機科學與技術學院，山東 煙臺 264005；2. 山東省車聯網工程技術中心，山東 煙臺 264005)

線性離散一致性系統均方偏差上界

竇全勝1,2，厲玉蓉1，姜平1

(1. 山東工商學院計算機科學與技術學院，山東 煙臺 264005；2. 山東省車聯網工程技術中心，山東 煙臺 264005)

一致性問題是多智能體協同控制的基礎，有廣泛的應用背景。之前的研究已經給出了線性一致性協議實現均方一致的充分條件，在此基礎上，對線性離散均方一致性問題進行了更加深入的討論，以圖論和隨機分析為基礎，進一步給出并嚴格證明線性離散均方一致性問題噪聲偏差的上界，同時以4種不同的網絡拓撲為例，對所提理論結果進行了說明。結論將為線性離散一致性系統的噪聲估計和控制提供理論依據。

群體智能；多智能體系統；一致性協議；噪聲問題；均方一致性

1 引言

所謂多智能體(multi-agent)一致性問題是指在多智能體系統(MAS, multi-agents system)中，智能體通過與相鄰智能體的信息交換來修訂自身狀態，最終達成所有智能體狀態上的趨同。由于在傳感網、社交網、協同控制等諸多領域具有廣泛的應用背景，該問題受到越來越多研究者的關注，已成為集群智能及分布式控制研究的熱點領域之一。關于多智能體一致性問題的研究可以追溯到 20世紀，一些研究者試圖通過建模與仿真來發掘這些多個體系統行為背后的內在機理，Reynolds[1]對自然界中鳥群、魚群等生物群體行為進行了頗為細致的研究，并利用計算機加以仿真，提出了著名的 Boid模型，這個模型在集群智能領域至今仍有廣泛影響；Vicsek等[2]提出了基于統計力學理論的Vicsek模型，模型中分布在二維平面上的N個智能體運動速率保持不變，并根據其鄰域內所有智能體的運動方向決定其自身運動方向，研究者采用離散時間一階非線性系統來模擬群體的相位變化，該模型比較真實地模擬了自然界中的一些群集同步現象；Jadbabaie等[3]利用代數圖論對Vicsek模型進行了理論解釋，并對幾個與Vicsek模型類似的模型的收斂性進行了理論分析，給出了Vicsek線性化模型的理論分析結果。隨著研究的深入和應用范圍的不斷拓展，越來越多新的研究不斷涌現，在理論和應用 2個層面不斷推動這一領域向前發展。針對一般有向圖的情形，Ren等[4]在研究中指出，在連續有界的時間隔內，若連接拓撲的并圖包含有向生成樹，則一致性系統漸近收斂，這個結論與后來Cao等[5]的研究結果是一致的。在對一致性問題的理論研究中，通常采用動力系統相關理論和方法作為工具，通過構造Lyapunov函數或LaSalle不變集性原理分析一致性系統收斂到一致子空間的條件，討論了分布式一致跟蹤控制問題，并將問題抽象成二階非線性動力系統，通過對 Lyapunov函數的討論給出了關于系統收斂性的充分條件；同樣，針對跟蹤控制問題，提出了分布式跟蹤算法，該算法可以在有限時間內收斂至一致狀態；Li等[9～13]針對多智能體一致性和復雜網絡的同步問題，提出基于高階線性系統的多智能體控制構架，并取得一系列成果；等[14]提出了采用“黑盒”代替具體動力學模型的方法，每一次迭代都采用了所謂的SOO(simultaneous optimistic optimization)方法對agent未來的動作進行規劃，由于與具體的動力學模型無關，該方法能更廣泛地應用于某些非線性一致性問題；關于線性一致性系統的研究，Olfati-Saber等[15～19]的工作最具影響，在其發表的一系列論文中，以圖理論和動力學理論為基礎，建立了一個相對完整的理論框架，并在此基礎上對不同類型的一致性問題進行了系統的分析；等[20]將平均一致性問題轉換成矩陣分解問題，并采用機器學習方法對矩陣分解問題進行求解；在實際應用中，通常存在agent狀態與agent間傳遞的數據無關的情況，針對這一問題，Yu等[21～23]進行了深入的研究和討論，提出了確保一致性協議收斂到一致狀態的3個充分必要條件；針對固定拓撲網絡存在可測噪聲的情形，Huang等[24,25]給出了系統達到均方一致(mean square consensus)的隨機近似方法；同樣在固定拓撲結構下，Liu等[26]針對線性一致性協議中的噪聲和信號延遲問題進行了研究，從理論上給出在non_leader_follower和leader_ follower這2種模式下，強一致(strong consensus)和均方一致的充分必要條件；Dou等[27]對線性一致性協議的噪聲問題進行了研究，給出了線性一致性協議噪聲可控的充分條件；在Long等[28]的研究中，agent收到的信息中含有噪聲的強度與相鄰 agent狀態有關，在一定假設基礎上，分析了固定拓撲結構、動態切換拓撲及隨機切換拓撲結構下的一致性算法，并給出了確保均方一致性的充分條件；Xia等[29]從固定拓撲入手，并進一步對切變和時滯拓撲下一致性問題進行了討論；Ren等[30]以矩陣論和控制論為工具，對非線性一致性問題進行了研究，并對給出的理論結果進行了驗證；近年來這一領域的研究不斷涌現，文獻[31,32]對各類一致性問題進行了較為系統的綜述與概括，指出了這一領域當前的主要研究成果，并分析了存在的問題及未來的發展趨勢。

關于線性均方一致性噪聲偏差問題的研究，通常從連續和離散時間系統出發，分別加以討論，本文的主要貢獻是：以圖論和隨機分析為基礎，嚴格證明了線性離散均方一致性問題噪聲偏差的上界，為線性離散一致性系統的噪聲估計和控制提供了理論依據。

2 預備知識

2.1 一致性協議（consensus protocol）

本文所述的MAS可用無向圖G=(V, ε)表示，其中，V={1,2,…,n}是圖G的頂點集，每個頂點可視作agent的抽象，通常用序號i表示。ε∈V×V為圖 G中所有邊構成的集合，如果存在(i, j)∈ε，則意味著節點i和j之間存在著信息交互。對于G中節點i,用Ni={j∈V|(i, j)∈ε,j≠i} 表示與i相鄰節點構成的集合，為節點i鄰居的個數。

定義1節點的度（degree）：設i∈V為圖G的一個節點，稱與i相鄰節點的個數為節點i的度，記作di，以di為對角線其他元素均為0的矩陣D=diag[d1,…,dn]稱為圖G的度矩陣。

定義2鄰接矩陣（adjacency matrix）[15]A，稱n階矩陣A=[aij]為圖G的鄰接矩陣，其中，

定義3Laplacian矩陣（Laplacian matrix）[15]L，稱n階矩陣L=[lij]n×n為圖G的Laplacian矩陣。

這里 A和 L均為對稱矩陣，且有 L=In?A。用λ1(L)≤λ2(L)≤…≤λn( L)表示矩陣L的 n個特征值，1=[1,…,1]T為單位向量，L具有以下性質[15]。

性質1L1=0。

性質2L最小的特征值 λ1(L)=0。

性質3當且僅當G為聯通圖時，L的次小特征值λ2(L)＞0。

設?和?+分別表示實數集和非負整數集，對于?i∈V，xi ( t)∈?,t∈?+為agenti在t時刻的狀態，agent按某種機制進行狀態的修訂，若對于?i, j∈V ，有

則稱上述系統為一致性系統，agent的狀態修訂機制為一致性協議。通常稱式(2)為離散線性一致性協議。

其中，μ＞0為一充分小常數，且滿足μdi≤ 1。令x(k)=[x1(k),…,x(k)]T，則式(2)可寫成如式(3)所示

n的矩陣形式。

對于任意初始狀態x (0)=[x1(0),…,xn(0)]T，線性一致性協議式(3)將漸進收斂至一致狀態。

2.2 均方一致性（mean square consensus）

設r為任意滿足正態分布的隨機數，用mean( r)和var( r)分別表示r的均值和方差，若為一隨機向量，則則為該隨機向量聯合分布的方差矩陣。

當agenti接收到的信息中包含著相互獨立的噪聲干擾時，則式(2)變為

其中，ξj～N(0,1)為j所攜帶的噪聲量，記ξ=[ξ1,…,，則var( ξ)=I，式(5)的矩陣形式為n

其中，Q=?L+ D。

定義 4均方一致[24]，在噪聲條件下，對于?i∈V ，若，且，則稱一致性協議能夠達成均方一致。

定義 5系統偏差[24]，稱在 t時刻每個 agent狀態分布方差之和為一致性系統在t時刻的系統偏差。

先前的研究[25,26]已經給出 Z(t)存在上界的充分條件，在此基礎上，進一步給出Z(t)的具體上界值。

3 離散均方一致性系統的偏差上界

其中，ε∶?+→?+，被稱為增益函數（gain function）。

引理1設t∈?+，若函數ε( t)滿足條件1和條件2，式(6)可達到均方一致。

事實上，引理1給出了一致性協議式(7)實現均方一致的充分條件，其證明過程在文獻[26,27]中已有詳盡的論述。

引理2設y∈?為一個實數，若0≤y＜1，則式(8)成立。

證明若 0≤ y＜1，根據 e?y的泰勒展開式有

在式(9)兩側同時取對數，得

因此，式(13)成立。

在上述引理基礎上，給出本文的主要結論。

定理1若G為連通圖，每個節點的輸出中攜有標準噪聲，增益函數ε滿足引理1中的2個條件，且，則當t趨于無窮大時，線性離散一致性協議式(7)的系統偏差滿足

其中，λ2( L)為圖G相應Laplacian矩陣L最小非零特征值，h=tr(QQT)，g為與ε有關的確定常數。

證明考察式(7)的矩陣形式

由L矩陣性質1可知，Lx*=L1x*=0，因此在式（17）右側加一項?Lx*，等式關系不變。

用Ft表示由生成的σ?代數，考察二階矩的條件期望

之前的研究[21]已經證明了

將式(23)代入式(22)中，從而得到式(24)。

由引理 3可知：當 t趨于無窮時，式(25)右側第一項為 0，因此，在式(25)兩端同時求極限可得

已知ε( k)滿足引理1中的條件，因此必有?k1，當k＞k1時，有

記

考察式(24)右側第2項，由引理2可得

綜合式(28)和式(31)，有

即

由式(33)進一步推出

綜合式(26)和式(34)，即得

定理1嚴格地給出了線性離散均方一致性協議系統偏差 Z(t)的上界，以下通過具體示例對定理 1的使用進行說明。

4 示例

本節以星型(star)、線型(path)、環型(circle)、4-鄰居環型(circle_N4)共4種不同的網絡結構為例（如圖1所示），對定理1的使用加以說明。

圖14種agent網絡結構

在圖1所示的4種不同網絡拓撲中，每種結構包括8個節點，即n=8，每個節點與一個agent相對應，每個agent除鄰節點個數不同外，其他結構完全一致。設置參數μ=0.125，不難計算，4種結構對應的Laplacian矩陣L的次小特征值如表1所示。

表1Laplacian矩陣L的次小特征值λ2(L)

考察增益函數 ε( t)分別為(t+1)?0.6和(t+1)?1時的情形，對于?k??+這2種情況均有，因此g=0。當 ε( t)=(t+1)?1時，而當ε( t)=(t+1)?0.6時，求存在一定困難，可以通過式(35)求該無窮級數的一個上界

根據定理1，可以計算出以上4種結構在噪聲條件下的系統偏差，具體如表2所示。

表24種網絡結構系統偏差上界（當 ε(t)分別為(t+1)?0.6和(t+1) ?1時）

需要說明的是，在定理1假設agent所攜帶噪聲為標準噪聲，然而在現實中這個假設通常不能滿足，這種情況不難通過適當變換，將噪聲變成標準噪聲，因此，并不影響定理1的使用。

5 結束語

多智能體協同在傳感網、社交網、協同控制等諸多領域有著廣泛的應用背景，一致性問題是多智能體協同問題的核心。在現實環境中，智能體間信息的傳遞往往會攜有噪聲，一致性協議通常無法收斂至理想狀態,此時噪聲對系統的影響程度是本文最關心的問題。關于均方一致性方差的研究，最理想的結果是直接給出均方一致性問題方差的解析表達式，斯坦福大學和普林斯頓大學的研究者[33]做了以下嘗試：首先構造關于協方差矩陣極限的李雅普諾夫方程，通過求解該方程獲得協方差矩陣極限。但這些研究似乎忽略了這樣一個事實，即在噪聲條件下，沒有引入增益函數的一致性協議的方差是不收斂的，只有引入增益函數且增益函數滿足引理1的2個條件時，均方一致性問題的方差才存在極限[26,27]，然而在引入增益函數后，之前構造的李雅普諾夫方程退化成恒等方程，沒有實際意義。在近期的一些研究中[26,27]，大多給出了噪聲條件下，各類網絡結構的線性一致系統實現均方收斂的充分條件，鮮有研究對均方一致性系統偏差做定量的估計。本文定理1給出的結論是對之前研究成果的補充。

線性均方一致性協議噪聲偏差問題的研究，通常從連續和離散時間系統出發，分別加以討論，本文的主要貢獻是：對線性離散均方一致性問題進行了討論，以圖論和隨機分析為基礎，對線性離散一致系統的噪聲偏差做了定量估計，給出了線性離散均方一致性問題噪聲偏差的一個理論上界，為線性離散一致性系統的噪聲分析和控制提供理論依據。

關于連續時間均方一致性問題，通常以代數圖論、Itō積分及隨機過程相關理論為依托，理論工具、分析方法和離散系統存在一定不同，由于篇幅所限，相應結論將在另外的研究中具體給出。

[1]REYNOLDS C W. Flocks, herds, and schools: a distributed behavioral model[C]//Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques. New York, 1987: 25-34.

[2]VICSEK T, CZIROK A, BEN-JACOB E, et al. Novel type of phase transition in a system of self-driven particles[J]. Physical Review Letters, 1995, 75(6):1226-1229.

[3]JADBABAIE A, LIN J, MORSE A. Coordination of groups of mobile autonomous agents using nearest neighbor rules[J]. IEEE Transactions on Automatic Control, 2003, 48(6): 988-1001.

[4]REN W, BEARD R W. Consensus seeking in multiagent systems under dynamically changing interaction topologies[J]. IEEE Trans Autom. Control, 2005, 50(5): 655-661.

[5]CAO M, MORSE A S, ANDERSON B D O. Reaching a consensus in a dynamically changing environment: a graphical approach[J]. Siam Journal on Control amp; Optimization, 2008, 47(2): 601-623.

[6]WEN G G, PENGA Z X, RAHMANIA A, et al. Distributed leader-following consensus for second-order multi-agent systems with nonlinear inherent dynamics[J]. International Journal of Systems Science, 2014, 45(9): 1892-1901.

[7]WEN G G, YU Y G, PENG Z X, et al. Distributed consensus tracking for second-order nonlinear multi-agent systems with a specified reference state[J]. Mathematical Problems in Engineering, 2014, 2014:320687.

[8]LU X Q, LU R Q, CHEN S H, et al. Finite-time distributed tracking control for multi-agent systems with a virtual leader[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2013, 60(2): 352-362.

[9]LI Z, DUAN Z S, CHEN G R, et al. Consensus of multi-agent systems and synchronization of complex networks: a unified viewpoint[J].IEEE Transactions on Circuits and Systems I: Regular Papers, 2010,57(1): 213-224.

[10]LI Z, DUAN Z S, CHEN G. Dynamic consensus of linear multi-agent systems[J]. Control Theory amp; Applications,2011, IET 5 (1): 19-28.

[11]LI Z, LIU X, REN W, et al. Distributed tracking control for linear multiagent systems with a leader of bounded unknown input[J]. IEEE Transactions on Automatic Control, 2013, 58(2): 518-523.

[12]WEN G, DUAN Z, LI Z, et al. Consensus and its 2-gain performance of multi-agent systems with intermittent information transmissions[J].International Journal of Control, 2012, 85(4): 384-396.

[13]WEN G, DUAN Z, LI Z, et al. Flocking of multi‐agent dynamical systems with intermittent nonlinear velocity measurements[J]. International Journal of Robust and Nonlinear Control, 2012, 22(16):1790-1805.

[14]BUSONIU L, MORARESCU I C. Consensus for agents with general dynamics using optimistic optimization[C]//Proceedings of 2013 Conference on Decision and Control (CDC-13). Florence, Italy, 2013:6735-6740.

[15]OLFATI-SABER R, FAX J A, MURRAY R M. Consensus and cooperation in networked multi-agent systems[J]. Proceedings of IEEE,2007, 95(1): 215-233.

[16]OLFATI-SABER R. Evolutionary dynamics of behavior in social networks[C]//Proc of the 46th IEEE Conference on Decision and Control, 2007.

[17]OLFATI-SABER R, JALALKAMALI P. Coupled distributed estimation and control for mobile sensor networks[J]. IEEE Trans on Automatic Control, 2012, 57(9): 2609-2614.

[18]OLFATI-SABER R. Flocking for multi-agent dynamic systems: algorithms and theory[J]. IEEE Transactions on Automatic Control, 2006,51(3): 401-420.

[19]OLFATI-SABER R, FAX J A, MURRAY R M. Consensus problems in networks of agents with switching topology and time-delays[J]. IEEE Trans. on Automatic Control, 2015, 49(9): 1520-1533.

[20]TRAN T M D, KIBANGOU A Y. Distributed design of finite-time average consensus protocols[C]//The 4th IFAC Workshop on Distributed Estimation and Control in Networked Systems. 2013, 4: 227-233.

[21]YU C H, NAGPAL R. A self-adaptive framework for modular robots in dynamic environment: theory and applications[J]. The International Journal of Robotics Research, 2011, 30(8): 1015-1036.

[22]YU C H. Biologically-inspired control for self-adaptive multiagent systems[D]. MA Cambridge: Harvard University, 2010.

[23]YU C H, NAGPAL R. Biologically-inspired control for multi-agent self-adaptive tasks[C]//Proc of the 24th AAAI Conference on Artifical Intelligence. 2010: 1702-1709.

[24]HUANG M, MANTON J H. Coordination and consensus of networked agents with noisy measurements: stochastic algorithms and asymptotic behavior[J]. SIAM Journal on Control and Optimization,2009, 48(1): 134-161.

[25]HUANG M, MANTON J H. Stochastic consensus seeking with noisy and directed inter-agent communication: fixed and randomly varying topologies[J]. Institute of Electrical and Electronics Engineers, Transactions on Automatic Control, 2010, 55(1): 235-241.

[26]LIU S, XIE L, ZHANG H. Distributed consensus for multi-agent systems with delays and noises in transmission channels[J]. Automatica, 2011, 47(5): 920-934.

[27]DOU Q S, CHONG L, JIANG P. Research on discrete linear consensus algorithm with noises[J]. Acta Automatica Sinica, 2015, 41(7):1328-1340.

[28]LONG Y, LIU S, XIE L. Distributed consensus of discrete-time multi-agent systems with multiplicative noises[J]. International Journal of Robust and Nonlinear Control, 2015, 25(16): 3113-3131.

[29]XIA H, HUANG T Z, SHAO J L, et al. Group consensus of multi-agent systems with communication delays[J]. Neuro Computing,2016, 171 (C): 1666-1673.

[30]REN T, WANG Y F, LIU MM, et al. The consensus of nonlinear multi-agent system with switching topologies and communication failure[J]. Journal of Intelligent and Fuzzy Systems, 2016, 30(2): 1199-1206.

[31]GARIN F, SCHENATO L. Distributed estimation and control applications using linear consensus algorithms[EB/OL]. http: //citeseerx.ist.psu.edu /viewdoc/summary?doi=10.1.1.382.9187.

[32]MIN H B, LIU Y, WANG S C, et al. An overview on coordination control problem of multi-agent system[J]. Acta Automatica Sinica,2012, 38(10): 1557-1570.

[33]YOUNG G F, SCARDOVI L, LEONARD N E. Robustness of noisy consensus dynamics with directed communication[C]//American Control Conference. 2010: 6312-6317.

Upper bound of mean-square deviation of discrete linear consensus system

DOU Quan-sheng1,2, LI Yu-rong1, JIANG Ping1
(1. School of Computer Science and Technology, Shandong Institute of Business and Technology, Yantai 264005, China;2. Shandong Vehicle Networking Engineering Technology Research Center, Yantai 264005, China)

The consistency problem is the basis of cooperative control of multi-agents, and has wide application background. The previous research has given the sufficient condition for the linear consistency protocol to realize mean-square consistency problem . Based on graph theory and random analysis, the noise-deviation upper bound of linear discrete mean-square consistency problem was strictly proved further, at the same time, four different network were used as examples to explain the theoretical results. The conclusion provides theoretical basis for the noise evaluation and control of the linear discrete consistency system.

collective intelligence, multi-agent system, consensus protocol, noisy problem, mean square consensus

s:The National Natural Science Foundation of China (No.61272244, No. 61672327, No.71471103), The National Basic Research Program of China (973 Program) (No. 2013CB329502), The Natural Science Foundation of Shandong Province(No.ZR2014FL007)

TP301.6

A

10.11959/j.issn.1000-436x.2016193

2016-05-12；

2016-08-21

國家自然科學基金資助項目（No.61272244, No.61672327, No.71471103）；國家重點基礎研究發展計劃（“973”計劃）基金資助項目（No.2013CB329502）；山東省自然科學基金資助項目（No.ZR2014FL007）

竇全勝（1971-），男，黑龍江大慶人，博士，山東工商學院教授，主要研究方向為智能計算和復雜自適應系統。

厲玉蓉（1975-），女，黑龍江牡丹江人，博士，山東工商學院教授，主要研究方向為計算幾何及最優化理論等。

姜平（1979-），男，山東煙臺人，山東工商學院副教授，主要研究方向為圖形圖像處理。