關于帶有協作/競爭機制時變積分器網絡一致性的收斂速率

馬麒超 秦家虎 李曼

摘要 本文探討了時變無向網絡達到狀態(tài)一致過程中的收斂速率問題.首先基于一般的時變無向網絡展開研究，證明了其收斂速率隨耦合權重的增加而提高.同時，給出了收斂速率的明確下界，并指出這個下界是耦合權重的線性函數.基于這些結論，本文研究了帶符號網絡的收斂速率問題，發(fā)現只要帶有正權值的邊具有（δ，T）連通性，就可以增大這些邊的權重而保持其余邊（帶有負權值）不變，使一致性以指數的速率達到.本文的證明過程主要基于完全一致可觀這一概念.另外，本文也得到了這樣的結論：一致性誤差值可以從系統一段時間內的相對狀態(tài)值中重建.這對于分布式網絡中濾波器的狀態(tài)估計有一定的借鑒意義.

關鍵詞??時變（分布式）網絡;指數收斂速率;帶符號網絡;完全一致可觀

中圖分類號? TP13

文獻標志碼? A

0 引言

近十幾年來多智能體系統理論廣受關注[1] .這是由于它能夠描述自然界中廣泛存在的有趣的生物群集現象，比如鳥類編隊以及螢火蟲同步閃光等.一般來說，多智能體系統是由多個智能體通過網絡互聯組成的，能夠完成復雜任務的系統[1] .這些個體具有一定感知、測量、儲存、計算、通信能力，并能夠對周圍環(huán)境做出反應.每個智能體通過與其相鄰個體溝通來協調自己的目標與行為，最終完成一項復雜的任務.多智能體系統的一致性在多智能體系統的研究中占有重要的地位.所謂一致性是指隨著時間的推移，多智能體系統中的所有智能體的狀態(tài)或者輸出達到相同的值.多智能體系統的其他行為模式，如聚集、編隊、蜂擁、同步等[1-2] ，都是以一致性為基礎的.

20世紀80年代，生態(tài)學家Reynolds提出了基于三條啟發(fā)式規(guī)則的Boid模型，通過計算機仿真模擬自然界中鳥群、魚群的群集行為.文獻[3]則從統計力學的角度提出了一個離散時間模型，能夠有效地描述簡單個體之間相互影響導致的群集行為.Ren等[4] 指出，在切換網絡情形下，有向通信拓撲具有聯合連通的性質能夠保證一致性的收斂.Moreau[5] 則進一步證明，在連續(xù)時變的系統中，對于上述聯合連通的有向通信拓撲，一旦有 δ，T 連通性（如果在任意給定的時間窗口 T 內權重積分大于δ的邊構成一個連通圖，則稱通信拓撲具有 δ，T 連通性），則能夠保證一致性的指數收斂.文獻[6]進一步確認了這一結論，并論證了在無向圖中指數收斂速率對初值具有一致性.文獻[7]探討了如何弱化上述 δ，T 連通性的要求.Shi等[7] 得出，如果有向圖的持續(xù)圖連通，即如果僅保留在[0，∞）上積分值為無窮大的邊仍能保持連通性，且不同邊的權值之間滿足一定的平衡關系，那么一致性能夠以漸近的形式達到.文獻[8]則給出了另一個有趣的結論，要求通信拓撲滿足 δ i，T i 條件，即不要求存在一個固定的時間窗口T使得通信拓撲聯合連通，而要求存在一列時間窗口使得聯合連通成立.這里的T i隨著i的增大可以趨近無窮大.在這個條件的基礎上，文獻[8]給出了使得時變無向圖中積分器系統全局漸近收斂的充分必要條件.上述結論盡管非常優(yōu)美，卻忽略了對于收斂速率的刻畫.

本文則進一步對時變無向圖中實現狀態(tài)一致的收斂速率進行了探討，證明了在一般的時變無向圖中，如果耦合權重增大，那么收斂速率也隨之提高.同時，給出了收斂速率的明確下界，并指出這個下界是耦合權重的線性函數.基于這一結論，本文針對帶符號的網絡進行了探討（即一個網絡中邊的權重可以為負數也可以為正數，這在社會網絡的建模和分析中能夠見到[9] ）.進一步，筆者發(fā)現只要帶有正權值的邊具有（δ，T）連通性，那么增大這些邊的權重而保持其余邊（帶有負權值）不變，即可使一致性以指數的速率達到.本文的證明主要基于完全一致可觀的概念.而且，在分析中可以得到一個額外但有意義的結論，即一致性誤差值可以從系統過去一段時間的相對狀態(tài)值中重建.這對于分布式網絡中濾波器的狀態(tài)估計有一定的借鑒意義.

1 圖論相關概念

由N個節(jié)點組成的有向圖可以用G= V，E 來表示，其中頂點集V={1，…，N}是有限的非空集合，邊集EV×V是有序節(jié)點對組成的邊的集合. i，j ∈E表示節(jié)點j能夠獲得節(jié)點i的信息，此時稱i是j的鄰居.記N i為節(jié)點i的鄰居的集合.與有向圖不同，無向圖中的 i，j 表示節(jié)點i和節(jié)點j能互相獲取對方的信息.

所以定理1，2在耦合強度足夠大的時候仍然成立.證明結束.

例2?? 考慮圖4所示的G ?a ，G ?b .它們都是無向圖，并且它們的并所得的圖中正權值的邊構成連通圖，即G ?a ∪G ?b 包含一個有正權值的邊構成的生成樹.在仿真驗證中，我們讓通信拓撲在G ?a ，G ?b 之間以周期1 ?s ?來回切換.系統的初值由隨機程序生成.G ?a ，G ?b 中邊的權重設置為c>0. 圖5表明當c=0.1，由于負邊的存在，系統并不收斂.當c增大到0.5時可以看到系統開始收斂，并以指數速率收斂，其速率小于0.2 （圖6）.當c=1即耦合強度增大時，可以看到收斂速率增加，并且大于0.4 （圖7）.這同樣驗證了本文的結論，耦合強度的增大能夠提升收斂的速率，同時抑制負邊帶來的影響使得系統達到一致.

7 總結

本文進一步對時變無向網絡中的收斂速率進行了探討.我們證明了，在一般的時變無向網絡中，如果耦合權重增大那么收斂速率也隨之提高.我們給出了收斂速率的明確下界，這個下界是耦合權重的線性函數.在此基礎上，針對帶符號網絡進行了探討，發(fā)現只要帶有正權值的邊具有（δ，T）連通性，那么增大這些邊的權重而保持其余邊（帶有負權值）不變，一致性就能以指數的速率達到.整個證明過程使用了完全一致可觀的概念.基于此還可以得到這樣的結論，即一致性誤差值可以從系統過去一段時間的相對狀態(tài)值中重建.

參考文獻

References

[ 1 ]

Qin ?J，Ma Q，Shi Y，et al.Recent advances in consensus of multi-agent systems：a brief survey[J].IEEE Transactions on Industrial Electronics，2017，64（6）：4972-4983

[ 2 ] Cao ?M，Morse A S，Anderson B D O.Reaching a consensus in a dynamically changing environment：convergence rates，measurement delays，and asynchronous events [J].Siam Journal on Control & Optimization，2008，47（2）：601-623

[ 3 ] Altafini C.Consensus problems on networks with antagonistic interactions[J].IEEE Transactions on Automatic Control，2013，58（4）：935-946

[ 4 ] 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

[ 5 ] Moreau ?L.Stability of continuous-time distributed consensus algorithms[C]∥

2014 43rd IEEE Conference on Decision and Control（CDC），2004：3998-4003

[ 6 ] Anderson ?B D O，Shi G，Trumpf J.Convergence and state reconstruction of time-varying multi-agent systems from complete observability theory[J].IEEE Trans Autom Control，2017，62（5）： 2519-2523

[ 7 ] Shi G，Johansson K H.The role of persistent graphs in the agreement seeking of social networks[J].IEEE Journal on Selected Areas in Communications，2013，31（9）：595-606

[ 8 ] Ortega ?R，Barabanov N.Global consensus of time-varying multi-agent systems without persistent excitation assumptions[J].IEEE Transactions on Automatic Control，2018，DOI： 10.1109/TAC.2018.2803114

[ 9 ] Shi ?G，Altafini C，Baras J S.Dynamics over signed networks[J].e-Print，2017，arXiv：1706.03362

[10] Anderson ?B D O，Moore J B.Detectability and stabilizability of time-varying discrete-time linear systems[J].Siam Journal on Control & Optimization，1981，19（1）：20-32

[11] Anderson ?B.Exponential stability of linear equations arising in adaptive identification[J].IEEE Trans Auto Control，1977，22（1）：83-88

[12] Antonio Lorí，Panteley E.Uniform exponential stability of linear time-varying systems：revisited[J].Systems & Control Letters，2002，47（1）：13-24

[13] Horn R A，Johnson C R.Matrix analysis[M].Cambridge：Cambridge University Press，1985

On convergence speed of interacting integrators over

cooperative and competitive undirected networks

MA Qichao 1 QIN Jiahu 1 LI Man 1

1 Department of Automation，University of Science and Technology of China，Hefei 230027

Abstract? The convergence speed in the distributed consensus of integrators over both cooperative and competitive undirected networks is investigated in this paper.It has been well known that as long as the （δ，T） connectivity condition is satisfied，exponential convergence of the consensus can be attained.We further show that，for a cooperative network，increasing the coupling strength can improve the convergence speed.The lower bound of the convergence is also explicitly specified with respect to the coupling strength.Based on this，in the competitive network，the convergence of consensus can be guaranteed by strong cooperative couplings dominating the competitive ones.The results of this paper are established by means of a uniformly completely observable theory.We also show that it is possible to reconstruct the consensus error at a certain time instant from the observations of the past relative state information over ?a fixed length interval.

Key words? time-varying network;convergence speed;signed networks;uniformly completely observable