魏 宇，范洪達(dá)，單 珊

（海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系，山東 煙臺(tái) 264001）

從上世紀(jì)90年代末期開(kāi)始，隨著多智能體系統(tǒng)的廣泛應(yīng)用，比如多無(wú)人機(jī)編隊(duì)協(xié)同控制[1-2]、分布式傳感器網(wǎng)絡(luò)[3]、衛(wèi)星群的姿態(tài)校準(zhǔn)和通信網(wǎng)絡(luò)的擁塞控制[4]，一些研究人員開(kāi)始對(duì)多智能體網(wǎng)絡(luò)分布式協(xié)作進(jìn)行深入探索[5-10]。這些研究正是分布式計(jì)算領(lǐng)域的基礎(chǔ)[1]。

為了解決分布式?jīng)Q策系統(tǒng)和并行計(jì)算中異步漸進(jìn)一致問(wèn)題，Borkar 等[11-15]的開(kāi)創(chuàng)性工作為基于網(wǎng)絡(luò)的分布式計(jì)算研究奠定了理論基礎(chǔ)。在多智能體網(wǎng)絡(luò)中，“一致性”表示多個(gè)智能體就某一感興趣量達(dá)成一致，而這個(gè)達(dá)成一致的量依賴于所有智能體的狀態(tài)?！耙恢滦运惴?協(xié)議)”就是指定某一智能體與相鄰智能體之間信息交換的規(guī)則。

近年來(lái)，多智能體一致性問(wèn)題及相關(guān)研究取得了大量研究成果。Vicsek 等[16]提出了一種離散時(shí)間分布式模型，證明了該模型在群體密度足夠大且噪聲較小的情況下可以使多智能體達(dá)到一致。Jadbabaie 等[17]研究了線性Vicsek模型，并證明了在相互連結(jié)圖是連通圖的情況下所有智能體能夠趨于一個(gè)穩(wěn)定的狀態(tài)。文獻(xiàn)[18]研究了一階離散狀態(tài)多智能體系統(tǒng)的一致性問(wèn)題，得出了每個(gè)單智能體的狀態(tài)趨于一致需要滿足的必要或充分條件。Olfati等[19]提出并解決了一階單積分多智能體系統(tǒng)的一致性問(wèn)題，并且在通信有時(shí)滯的情況下找到了系統(tǒng)達(dá)到一致的條件。該研究表明對(duì)于固定無(wú)向網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的多智能體系統(tǒng)，在假定通信時(shí)滯相等且存在上界的情況下，智能體可以收斂到一致。文獻(xiàn)[20]將Olfati的模型擴(kuò)展到了離散時(shí)間條件下，也得出了類似的結(jié)論。但上述結(jié)論都是在時(shí)滯相等條件下給出的，在實(shí)際應(yīng)用方面還有一定的局限性。本文在此基礎(chǔ)上，研究了基于無(wú)向圖且存在不相等時(shí)滯情況下的多智能體一致性問(wèn)題。

1 一致性問(wèn)題數(shù)學(xué)描述及預(yù)備知識(shí)

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

有向路徑由有向圖中有序相鄰的邊連接組成，如 (n1,n2),(n2,n3),…。無(wú)向圖中的無(wú)向路徑也可由類似方法定義。當(dāng)有向圖中的任何兩個(gè)節(jié)點(diǎn)之間都存在有向路徑，這個(gè)有向圖稱為強(qiáng)連通的。當(dāng)無(wú)向圖中任何兩個(gè)節(jié)點(diǎn)之間都存在無(wú)向路徑，這個(gè)無(wú)向圖稱為連通的。如果一個(gè)有向圖除了一個(gè)節(jié)點(diǎn)(根節(jié)點(diǎn))其余節(jié)點(diǎn)都只有唯一的一個(gè)父節(jié)點(diǎn)，根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，并且根節(jié)點(diǎn)到所有其余節(jié)點(diǎn)都存在有向路徑，這樣的有向圖稱為有向樹(shù)。對(duì)于無(wú)向圖，若任意兩個(gè)節(jié)點(diǎn)都由唯一的無(wú)向路徑連接，這樣的無(wú)向圖稱為樹(shù)。

可以用矩陣來(lái)描述有向圖中個(gè)節(jié)點(diǎn)之間的關(guān)系。為此，引入鄰接矩陣的概念，鄰接矩陣 nA中的元素取值如下：

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

考慮信息狀態(tài)由下述離散時(shí)間模型描述

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

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

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

一般而言，智能體對(duì)接收到的信息進(jìn)行處理需要一個(gè)過(guò)程，對(duì)整個(gè)系統(tǒng)來(lái)講，可以將這個(gè)過(guò)程看作是一個(gè)輸入延時(shí)，本文記作τ。由于本文考慮的是離散時(shí)間模型，因此輸入延時(shí)取非負(fù)整數(shù)。假設(shè)智能體i的輸入延時(shí)為iτ，式(3)可改寫(xiě)為：

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

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

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

2 存在輸入延時(shí)的一致性分析

本節(jié)主要研究存在輸入延時(shí)的多智能體系統(tǒng)一致性問(wèn)題，其數(shù)學(xué)模型由式(6)表示。這里首先考慮最簡(jiǎn)單的信息交換拓?fù)浣Y(jié)構(gòu)，即無(wú)向連通圖。

定理：由式(6)描述的多智能體離散時(shí)間系統(tǒng)，在信息交換拓?fù)錇闊o(wú)向連通圖的條件下達(dá)到漸近一致的充分條件是：

式中，[?]為下取整函數(shù)。

證明：對(duì)式(6)進(jìn)行Z變換，并將其寫(xiě)成矩陣形式：

易知其特征方程為：

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

令z=1，式(9)變?yōu)閐et(Ln)=0。因?yàn)榧僭O(shè)信息交換拓?fù)錇闊o(wú)向連通圖，故0是Ln的簡(jiǎn)單特征值(代數(shù)多重度為0)，即det(Ln)=0且Rank(Ln)=n?1。這也就證明了z=1確實(shí)是式(9)唯一的模為1的解。

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

由廣義Nyquist 穩(wěn)定性判據(jù)可知，式(10)的解的模小于1，等價(jià)于當(dāng)ω∈ [0,2π]時(shí)，的特征軌跡不包含點(diǎn)(?1,0j)。

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

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

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

由矩陣特征值的相關(guān)理論可知

因?yàn)榧僭O(shè)信息交換拓?fù)錇闊o(wú)向連通圖，所以nL為實(shí)對(duì)稱矩陣，現(xiàn)令

顯然有Q*=Q＞0，于是應(yīng)用引理可得

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

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

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

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

3 仿真計(jì)算

本文采用的信息交換拓?fù)浼肮?jié)點(diǎn)之間的連接權(quán)重如圖3所示。

由式(7)得τ1≤3、τ2≤2、τ3≤4、τ4≤3，4個(gè)值分別稱為各節(jié)點(diǎn)的標(biāo)準(zhǔn)延時(shí)。表1是各節(jié)點(diǎn)在不同仿真實(shí)例中輸入延時(shí)的取值情況。假設(shè)各節(jié)點(diǎn)的狀態(tài)是一維的，且初始狀態(tài)分別為1、2、3、4。

圖3 包含4個(gè)節(jié)點(diǎn)的無(wú)向連通圖

表1 預(yù)測(cè)滲層表面的成分

圖4～6分別為無(wú)延時(shí)、小于或等于標(biāo)準(zhǔn)延時(shí)、大于標(biāo)準(zhǔn)延時(shí)時(shí)的系統(tǒng)狀態(tài)圖。

圖4 無(wú)延時(shí)情況下的系統(tǒng)狀態(tài)圖

圖5 小于或等于標(biāo)準(zhǔn)延時(shí)情況下的系統(tǒng)狀態(tài)圖

圖6 大于標(biāo)準(zhǔn)延時(shí)情況下的系統(tǒng)狀態(tài)圖

從圖4可以看出，在沒(méi)有輸入延時(shí)的情況下各節(jié)點(diǎn)很快就可以達(dá)到一致。在仿真實(shí)例2中，各節(jié)點(diǎn)的輸入延時(shí)取值均在標(biāo)準(zhǔn)延時(shí)范圍內(nèi)，從圖5可以看出在經(jīng)過(guò)一段時(shí)間的震蕩之后，各節(jié)點(diǎn)依然可以達(dá)到一致。進(jìn)一步觀察可以發(fā)現(xiàn)，輸入延時(shí)取值越大，其狀態(tài)曲線震蕩也越強(qiáng)烈，這也符合直覺(jué)認(rèn)識(shí)。而在仿真實(shí)例3中，節(jié)點(diǎn)2的輸入延時(shí)取值大于其標(biāo)準(zhǔn)延時(shí)，其余節(jié)點(diǎn)的輸入延時(shí)取值仍然在各標(biāo)準(zhǔn)延時(shí)范圍內(nèi)。從圖6看出，即使只有一個(gè)節(jié)點(diǎn)的輸入延時(shí)取值超過(guò)其標(biāo)準(zhǔn)延時(shí)，整個(gè)系統(tǒng)也不可能穩(wěn)定，也就是說(shuō)，系統(tǒng)內(nèi)各節(jié)點(diǎn)無(wú)法達(dá)成一致。

4 結(jié)論

本文研究了在無(wú)向連通圖條件下，帶有輸入延時(shí)的多智能體離散時(shí)間系統(tǒng)一致性問(wèn)題。利用廣義Nyquist 穩(wěn)定性判定準(zhǔn)則和矩陣特征值相關(guān)理論，導(dǎo)出了多智能體離散時(shí)間系統(tǒng)在信息交換拓?fù)錇闊o(wú)向連通圖的條件下達(dá)到漸近一致的充分條件。該充分條件給出了各節(jié)點(diǎn)對(duì)應(yīng)的輸入延時(shí)的取值范圍，任何一個(gè)節(jié)點(diǎn)的輸入延時(shí)超出其對(duì)應(yīng)范圍都將導(dǎo)致整個(gè)系統(tǒng)無(wú)法達(dá)到一致。最后，用仿真實(shí)例驗(yàn)證了前面建立的數(shù)學(xué)模型及所得理論結(jié)果的正確性

[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]楊洪勇,張嗣瀛.離散時(shí)間系統(tǒng)的多智能體的一致性[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.