多智能體離散時間系統一致性研究

魏 宇，范洪達，單 珊

（海軍航空工程學院兵器科學與技術系，山東 煙臺 264001）

從上世紀90年代末期開始，隨著多智能體系統的廣泛應用，比如多無人機編隊協同控制[1-2]、分布式傳感器網絡[3]、衛星群的姿態校準和通信網絡的擁塞控制[4]，一些研究人員開始對多智能體網絡分布式協作進行深入探索[5-10]。這些研究正是分布式計算領域的基礎[1]。

為了解決分布式決策系統和并行計算中異步漸進一致問題，Borkar 等[11-15]的開創性工作為基于網絡的分布式計算研究奠定了理論基礎。在多智能體網絡中，“一致性”表示多個智能體就某一感興趣量達成一致，而這個達成一致的量依賴于所有智能體的狀態。“一致性算法(協議)”就是指定某一智能體與相鄰智能體之間信息交換的規則。

近年來，多智能體一致性問題及相關研究取得了大量研究成果。Vicsek 等[16]提出了一種離散時間分布式模型，證明了該模型在群體密度足夠大且噪聲較小的情況下可以使多智能體達到一致。Jadbabaie 等[17]研究了線性Vicsek模型，并證明了在相互連結圖是連通圖的情況下所有智能體能夠趨于一個穩定的狀態。文獻[18]研究了一階離散狀態多智能體系統的一致性問題，得出了每個單智能體的狀態趨于一致需要滿足的必要或充分條件。Olfati等[19]提出并解決了一階單積分多智能體系統的一致性問題，并且在通信有時滯的情況下找到了系統達到一致的條件。該研究表明對于固定無向網絡拓撲結構的多智能體系統，在假定通信時滯相等且存在上界的情況下，智能體可以收斂到一致。文獻[20]將Olfati的模型擴展到了離散時間條件下，也得出了類似的結論。但上述結論都是在時滯相等條件下給出的，在實際應用方面還有一定的局限性。本文在此基礎上，研究了基于無向圖且存在不相等時滯情況下的多智能體一致性問題。

1 一致性問題數學描述及預備知識

令 G={V,E,A}表示一個有向加權圖，其中V={v1,v2,…,vn}表示圖中的n個節點的集合。圖中的邊集合用E ? V×V表示。邊(i,j)表示智能體j可以獲得來自智能體i的信息，反之不成立，其中i 稱為父節點，j 稱為子節點。對無向圖來講，節點之間沒有順序，邊(i,j)表示節點i、j 間可交流信息而沒有方向性。無向圖可以看作有向圖的特例，無向圖中的邊(i,j)對應于有向圖中的邊(i,j)及(j,i)。

有向路徑由有向圖中有序相鄰的邊連接組成，如 (n1,n2),(n2,n3),…。無向圖中的無向路徑也可由類似方法定義。當有向圖中的任何兩個節點之間都存在有向路徑，這個有向圖稱為強連通的。當無向圖中任何兩個節點之間都存在無向路徑，這個無向圖稱為連通的。如果一個有向圖除了一個節點(根節點)其余節點都只有唯一的一個父節點，根節點沒有父節點，并且根節點到所有其余節點都存在有向路徑，這樣的有向圖稱為有向樹。對于無向圖，若任意兩個節點都由唯一的無向路徑連接，這樣的無向圖稱為樹。

可以用矩陣來描述有向圖中個節點之間的關系。為此，引入鄰接矩陣的概念，鄰接矩陣 nA中的元素取值如下：

式中，wij為(vj,vi)的權值，一般來講假設aii=0。同時，定義矩陣 Ln=[lij]∈?n×n為

考慮信息狀態由下述離散時間模型描述

式中：xi∈?、ui∈?分別是第i個智能體的信息狀態和信息控制輸入。

一致性算法一般由下式給出[13]

本文的研究目的是考察存在延時條件下一致性算法的收斂情況。因此，需要在上述模型中引入延時參數。

一般而言，智能體對接收到的信息進行處理需要一個過程，對整個系統來講，可以將這個過程看作是一個輸入延時，本文記作τ。由于本文考慮的是離散時間模型，因此輸入延時取非負整數。假設智能體i的輸入延時為iτ，式(3)可改寫為：

可以把式(4)、(5)合寫為：

下面引入在后文證明中需要的一個重要引理。

引理[21]：若有 Q=Q*＞0，L=diag{li}，li∈?，則σ(QL)=σ(LQ) ? ρ(Q) Co(0 ∪ {li})。其中：σ (?)表示矩陣的特征值；ρ (?)表示矩陣的譜半徑；Co(?)表示凸包。

2 存在輸入延時的一致性分析

本節主要研究存在輸入延時的多智能體系統一致性問題，其數學模型由式(6)表示。這里首先考慮最簡單的信息交換拓撲結構，即無向連通圖。

定理：由式(6)描述的多智能體離散時間系統，在信息交換拓撲為無向連通圖的條件下達到漸近一致的充分條件是：

式中，[?]為下取整函數。

證明：對式(6)進行Z變換，并將其寫成矩陣形式：

易知其特征方程為：

至此，可以把由式(4)、(5)描述的多智能體系統一致性問題分析和由式(8)描述的離散時間系統穩定性分析聯系起來。實際上，由離散時間系統相關理論可知，要使多智能體系統達到漸進一致，式(9)的特征根必須位于單位圓內。下面證明除了z=1，其余解的模都小于1。

令z=1，式(9)變為det(Ln)=0。因為假設信息交換拓撲為無向連通圖，故0是Ln的簡單特征值(代數多重度為0)，即det(Ln)=0且Rank(Ln)=n?1。這也就證明了z=1確實是式(9)唯一的模為1的解。

接下來證明其余解的模都小于1。為了分析的方便，引入式(10)，顯然式(9)、(10)同解(當z≠1)。

由廣義Nyquist 穩定性判據可知，式(10)的解的模小于1，等價于當ω∈ [0,2π]時，的特征軌跡不包含點(?1,0j)。

圖1 τ=2時，Mi?Fi(ω)在復平面上的曲線

圖2 τ=5時，Mi?Fi(ω)在復平面上的曲線

從圖1、2中可清楚地看到曲線和實軸第一次相交于點(?1,0j)。為了利用上述特性，將 G (ejω)改寫為如下形式：

由矩陣特征值的相關理論可知

因為假設信息交換拓撲為無向連通圖，所以nL為實對稱矩陣，現令

顯然有Q*=Q＞0，于是應用引理可得

那么進而就可以證明 G (ejω)的特征軌跡不包含點(?1,0 j)。

對于矩陣 diag{Mi?1}Ln，其譜半徑小于等于它的任何一種范數，這里取行范數，也即

由nL的定義可知顯然當成立時，的譜半徑滿足又由式(11)可得因此，的特征軌跡不包含點(?1,0j)，也就是說式(10)的解的模小于1。至此，已經證明了式(9)的解除了z=1，其余解的模都小于1。

綜上所述，式(6)描述的多智能體系統的特征方程(9)除了零點z=1，其余零點的模都小于1。因此，式(6)描述的離散系統漸近收斂到一個穩定狀態 x*，也即其中，由前述分析可知det(Ln)=0且Rank(Ln)=n?1，所以，Lnx=0的解只能以x*=c[1,1,…,1]T的形式存在，其中c為常數。進一步有至此，就證明了由式(6)描述的多智能體系統可以達到漸近一致。

3 仿真計算

本文采用的信息交換拓撲及節點之間的連接權重如圖3所示。

由式(7)得τ1≤3、τ2≤2、τ3≤4、τ4≤3，4個值分別稱為各節點的標準延時。表1是各節點在不同仿真實例中輸入延時的取值情況。假設各節點的狀態是一維的，且初始狀態分別為1、2、3、4。

圖3 包含4個節點的無向連通圖

表1 預測滲層表面的成分

圖4～6分別為無延時、小于或等于標準延時、大于標準延時時的系統狀態圖。

圖4 無延時情況下的系統狀態圖

圖5 小于或等于標準延時情況下的系統狀態圖

圖6 大于標準延時情況下的系統狀態圖

從圖4可以看出，在沒有輸入延時的情況下各節點很快就可以達到一致。在仿真實例2中，各節點的輸入延時取值均在標準延時范圍內，從圖5可以看出在經過一段時間的震蕩之后，各節點依然可以達到一致。進一步觀察可以發現，輸入延時取值越大，其狀態曲線震蕩也越強烈，這也符合直覺認識。而在仿真實例3中，節點2的輸入延時取值大于其標準延時，其余節點的輸入延時取值仍然在各標準延時范圍內。從圖6看出，即使只有一個節點的輸入延時取值超過其標準延時，整個系統也不可能穩定，也就是說，系統內各節點無法達成一致。

4 結論

本文研究了在無向連通圖條件下，帶有輸入延時的多智能體離散時間系統一致性問題。利用廣義Nyquist 穩定性判定準則和矩陣特征值相關理論，導出了多智能體離散時間系統在信息交換拓撲為無向連通圖的條件下達到漸近一致的充分條件。該充分條件給出了各節點對應的輸入延時的取值范圍，任何一個節點的輸入延時超出其對應范圍都將導致整個系統無法達到一致。最后，用仿真實例驗證了前面建立的數學模型及所得理論結果的正確性

[1]OLFATI SABER R,MURRAY R M.Distributed cooperative control of multiple vehicle formations using structural potential functions[C]//The 15th IFAC World Congress.2002∶1-7.

[2]EREN T,BELHUMEUR P N,MORSE A S.Closing ranks in vehicle formations based on rigidity[C]//Proc.of the IEEE Conference on Decision and Control.2002∶2959-2969.

[3]CORTES J,BULLO F.Coordination and geometric optimization via distributed dynamical systems[J].SIAM Journal on Control and Optimization,2004,25(6)∶469-474.

[4]PAGANINI F,DOYLE J,LOW S.Scalable laws for stable network congestion control[C]//Proc.of the Int.Conf.on Decision and Control,Orlando,FL,2001∶185-190.

[5]AGARWAL P K,SHARIR M.Efficient algorithms for geometric optimization[J].Computing Surveys,1998,30(4)∶412-458.

[6]BAILLIEUL J,SURI A.Information patterns and hedging Brockett’s theorem in controlling vehicle formations[C]//IEEE Conference on Decision and Control.2003∶556-563.

[7]FAGNANI F,ZAMPIERI S.Average consensus with packet drop communication[J].Journal on Control and Optimization,2009,48(1)∶102-133.

[8]DIMAROGONAS D V,KYRIAKOPOULOS K J.On the rendezvous problem for multiple nonholonomic agents[J].IEEE Transactions on Automatic Control,2007,52(5)∶916-922.

[9]LEE D,SPONG M W.Stable flocking of multiple inertial agents on balanced graphs[J].IEEE Transactions on Automatic Control,2007,52(8)∶1469- 1475.

[10]MOORE B J,PASSINO K M.Distributed task assignment for mobile agents[J].IEEE Transactions on Automatic Control,2007,52(4)∶749-753.

[11]LYNCH N A.Distributed Algorithms[M].San Francisco,CA∶Morgan Kaufmann,1997∶1-904.

[12]BORKAR V.Asymptotic agreement in distributed estimation[J].IEEE,Trans.Autom.Control,1982,27(3)∶650-655.

[13]TSITSIKLIS J N.Problems in Decentralized Decision Making and Computation[M].Cambridge,MA∶Dept.Electr.Eng.Comput.Sci.,Lab.Inf.Decision Syst.,Massachusetts Inst.Technol.,1984∶1-134.

[14]TSITSIKLIS J N,BERTSEKAS D P,ATHANS M.Distributed asynchronous deterministic and stochastic gradient optimization algorithms[J].IEEE,Trans.Automatic Control,1986,31(9)∶803-812.

[15]BERTSEKAS D P,TSITSIKLIS J.Parallell and Distributed Computation[M].Upper Saddle River,NJ∶Prentice-Hall,1989∶1-730.

[16]VICSEK T,CZIROK A,SCHOCHET O.Novel type of phase transitions in a system of self-driven particles[J].Phys.Rev.Lett.,1995,75∶1226-1229.

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

[18]MOREAU L.Stability of multi-agent systems with time dependent communication links[J].IEEE Transactions on Automatic Control,2005,50(2)∶169-182.

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

[20]楊洪勇,張嗣瀛.離散時間系統的多智能體的一致性[J].控制與決策,2009,24(3)∶413-416.

[21]VINNICOMBE G.On the stability of end-to-end congestion control for the Internet[R].Department Engineering University of Cambridge,2000∶1-6.