馬麒超 秦家虎 李曼

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

關(guān)鍵詞??時(shí)變（分布式）網(wǎng)絡(luò);指數(shù)收斂速率;帶符號(hào)網(wǎng)絡(luò);完全一致可觀

中圖分類(lèi)號(hào)? TP13

文獻(xiàn)標(biāo)志碼? A

0 引言

近十幾年來(lái)多智能體系統(tǒng)理論廣受關(guān)注[1] .這是由于它能夠描述自然界中廣泛存在的有趣的生物群集現(xiàn)象，比如鳥(niǎo)類(lèi)編隊(duì)以及螢火蟲(chóng)同步閃光等.一般來(lái)說(shuō)，多智能體系統(tǒng)是由多個(gè)智能體通過(guò)網(wǎng)絡(luò)互聯(lián)組成的，能夠完成復(fù)雜任務(wù)的系統(tǒng)[1] .這些個(gè)體具有一定感知、測(cè)量、儲(chǔ)存、計(jì)算、通信能力，并能夠?qū)χ車(chē)h(huán)境做出反應(yīng).每個(gè)智能體通過(guò)與其相鄰個(gè)體溝通來(lái)協(xié)調(diào)自己的目標(biāo)與行為，最終完成一項(xiàng)復(fù)雜的任務(wù).多智能體系統(tǒng)的一致性在多智能體系統(tǒng)的研究中占有重要的地位.所謂一致性是指隨著時(shí)間的推移，多智能體系統(tǒng)中的所有智能體的狀態(tài)或者輸出達(dá)到相同的值.多智能體系統(tǒng)的其他行為模式，如聚集、編隊(duì)、蜂擁、同步等[1-2] ，都是以一致性為基礎(chǔ)的.

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

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

1 圖論相關(guān)概念

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

所以定理1，2在耦合強(qiáng)度足夠大的時(shí)候仍然成立.證明結(jié)束.

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

7 總結(jié)

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

參考文獻(xiàn)

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