多智能體系統(tǒng)一致性綜述

多智能體系統(tǒng)一致性綜述一引言多智能體系統(tǒng)在20世紀(jì)80年代后期成為分布式人工智能研究中的主要研究對象。研究多智能體系統(tǒng)的主要目的就是期望功能相對簡單的智能體系統(tǒng)之間進(jìn)行分布式合作協(xié)調(diào)控制，最終完成復(fù)雜任務(wù)。多智能體系統(tǒng)由于其強(qiáng)健、可靠、高效、可擴(kuò)展等特性，在科學(xué)計(jì)算、計(jì)算機(jī)網(wǎng)絡(luò)、機(jī)器人、制造業(yè)、電力系統(tǒng)、交通控制、社會仿真、虛擬現(xiàn)實(shí)、計(jì)算機(jī)游戲、軍事等方面廣泛應(yīng)用。多智能體的分布式協(xié)調(diào)合作能力是多智能體系統(tǒng)的基礎(chǔ)，是發(fā)揮多智能體系統(tǒng)優(yōu)勢的關(guān)鍵，也是整個(gè)系統(tǒng)智能性的體現(xiàn)。在多智能體分布式協(xié)調(diào)合作控制問題中，一致性問題作為智能體之間合作協(xié)調(diào)控制的基礎(chǔ)，具有重要的現(xiàn)實(shí)意義和理論價(jià)值。所謂一致性是指隨著時(shí)間的演化，一個(gè)多智能體系統(tǒng)中所有智能體的某一個(gè)狀態(tài)趨于一致。一致性協(xié)議是智能體之間相互作用、傳遞信息的規(guī)則，它描述了每個(gè)智能體和其相鄰的智能體的信息交互過程。當(dāng)一組智能體要合作共同去完成一項(xiàng)任務(wù)，合作控制策略的有效性表現(xiàn)在多智能體必須能夠應(yīng)對各種不可預(yù)知的形式和突然變化的環(huán)境，必須對任務(wù)達(dá)成一致意見，這就要求智能體系統(tǒng)隨著環(huán)境的變化能夠達(dá)到一致。因此，智能體之間協(xié)調(diào)合作控制的一個(gè)首要條件是多智能體達(dá)到一致。近年來，一致性問題的研究發(fā)展迅速，包括生物科學(xué)、物理科學(xué)、系統(tǒng)與控制科學(xué)、計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域都對一致性問題從不同層面進(jìn)行了深入分析，研究進(jìn)展主要集中在群體集、蜂涌、聚集、傳感器網(wǎng)絡(luò)估計(jì)等問題。目前，許多學(xué)科的研究人員都開展了多智能體系統(tǒng)的一致性問題的研究，比如多智能體分布式一致性協(xié)議、多智能體協(xié)作、蜂涌問題、聚集問題等等。下面，主要對現(xiàn)有文獻(xiàn)中多智能體一致性協(xié)議進(jìn)行了總結(jié)，并對相關(guān)應(yīng)用進(jìn)行簡單的介紹。1.1圖論基礎(chǔ)多智能體系統(tǒng)是指由多個(gè)具有獨(dú)立自主能力的智能體通過一定的信息傳遞方式相互作用形成的系統(tǒng)；如果把系統(tǒng)中的每一個(gè)智能體看成是一個(gè)節(jié)點(diǎn)，任意兩個(gè)節(jié)點(diǎn)傳遞的智能體之間用有向邊來連接的話，智能體的拓?fù)浣Y(jié)構(gòu)就可以用相應(yīng)的有向圖來表示。用G=（V,E,A）來表示一個(gè)有向加權(quán)圖，其中V={v,v，…,v}代表圖的n個(gè)頂12n

點(diǎn)；EqVxV是邊集合，如果存在從第i個(gè)頂點(diǎn)到第j個(gè)頂點(diǎn)的信息流，則有e=(v,v)eE；A是非負(fù)加權(quán)鄰接矩陣eeEoa>0；節(jié)點(diǎn)v的鄰居集定義為ijij ij ij iN={vI(v,v)eE}。如果對所有的eeE意識著eeE，則稱G是無向圖。ijij ij ji2個(gè)不同的節(jié)點(diǎn)v和v之間有有向路徑是指存在1個(gè)有序節(jié)點(diǎn)序列ij(v,v)，(v,v"?，(v,v)；如果圖G中任意兩個(gè)不同的結(jié)點(diǎn)間都存1僚有向路1k1k1k2 klj徑，則稱G是強(qiáng)連通圖；如果G是無向的，則稱G是連通圖。圖G有有向生成樹指的是圖G存在1個(gè)包含所有定點(diǎn)的子圖，除了唯一的根節(jié)點(diǎn)以外，其余節(jié)點(diǎn)有且僅有1個(gè)父節(jié)點(diǎn)。二．主要研究內(nèi)容多智能體系統(tǒng)一致性問題描述令％eRq表示圖中第i個(gè)頂點(diǎn)v的狀態(tài)且滿足文=f(x,u)，這樣可利用二元組i i iiX=F(x,u)。如果對于所有的i,j，則稱多智能體系統(tǒng)實(shí)(G,x)來表示動態(tài)多智能體網(wǎng)絡(luò)系統(tǒng)，其中x=(xt,xt,…，xX=F(x,u)。如果對于所有的i,j，則稱多智能體系統(tǒng)實(shí)都有l(wèi)imx(t)-x(t)||=0，

t.(? ， j現(xiàn)一致性。一致性協(xié)議一階一致性在早期關(guān)于一致性問題的研究中，絕大多數(shù)研究工作針對智能體為一階智能體的情形，分析不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下實(shí)現(xiàn)一致性需要滿足的條件和一致性實(shí)現(xiàn)時(shí)的收斂值。(1)連續(xù)時(shí)間情形 當(dāng)網(wǎng)絡(luò)中的智能體均具有形如：x=u(xeR) (1)iii的狀態(tài)方程時(shí)，經(jīng)常采用一致性協(xié)議為：u=Za(x-x) (2)iijjiieN因此，在上述一致性協(xié)議下的閉環(huán)系統(tǒng)為x=-Lx，系統(tǒng)(1)的解為x(t)=eLtx(0)，可以利用線性系統(tǒng)理論來分析系統(tǒng)的一致性問題。在固定拓?fù)浣Y(jié)構(gòu)下，一致性的相關(guān)結(jié)論為：定理1假定G有一個(gè)有向生成樹，L為其拉普拉斯矩陣且有L1=0，YtL=0，Yt1=1，則在協(xié)議(2)作用下，多智能體系統(tǒng)可實(shí)現(xiàn)一致性，且limx(t)=ytx(0)。特別地，當(dāng)G為無向連通圖或強(qiáng)連通平衡圖時(shí)，多智能體系統(tǒng)it-8

可實(shí)現(xiàn)平均一致性，即/加x(t)-Zx(0)。iitT8 i-1許多場合下，由于節(jié)點(diǎn)間連接的建立或失敗，多智能體系統(tǒng)的拓?fù)浣Y(jié)構(gòu)往往是動態(tài)發(fā)生變化的。擁有動態(tài)網(wǎng)絡(luò)的系統(tǒng)一般稱之為切換網(wǎng)絡(luò)，切換網(wǎng)絡(luò)可以用G(t)來表示，其中o(t)：RTJ-｛1,2,…,m｝為切換信號，｛G,G,…,G｝為所有可12m能的拓?fù)浣Y(jié)構(gòu)組成的集合。在協(xié)議(2)的作用下，且有切換拓?fù)浣Y(jié)構(gòu)的閉環(huán)系統(tǒng)為：(3)x--L(G(3)k…,T(0<T…,T(0<T<T<…T<t)處切換，則系統(tǒng)(3)的n12n12解為：x(t)-e-L(Go(h?-th))e-L(Go(h-i))(th-h-1)…e-L(G心乂]2，)?-L(G川/1x(0)系統(tǒng)一致性分析轉(zhuǎn)化為多個(gè)具有非負(fù)對角的隨機(jī)矩陣乘積的極限問題的分析。在切換拓?fù)浣Y(jié)構(gòu)下，一致性的相關(guān)結(jié)論為：定理2假定切換網(wǎng)絡(luò)在任意長度有上界的時(shí)間間隔內(nèi)均有一個(gè)有向生成樹，則在協(xié)議(2)作用下，切換多智能體系統(tǒng)可漸進(jìn)實(shí)現(xiàn)一致性。(2)離散時(shí)間情形 當(dāng)網(wǎng)絡(luò)中的智能體均具有形如：x(k+1)-x(k)+u(k)ii的狀態(tài)方程時(shí)，采用一致性協(xié)議：u=￡Za(x(k)-x(k))i ijji莊Ni因此，在上述一致性協(xié)議下形成的閉環(huán)系統(tǒng)為：x(k+1)-Px(k)式中，P-1-sL,0<8<1A，A是網(wǎng)絡(luò)節(jié)點(diǎn)的最大出度。在固定拓?fù)浜颓袚Q拓?fù)浣Y(jié)構(gòu)下，多智能體系統(tǒng)有類似定理1和定理2相應(yīng)的結(jié)論。(3)其他研究熱點(diǎn)除了上述關(guān)于一致性的經(jīng)典結(jié)論外，還有學(xué)者分別考慮帶時(shí)滯的一致性、有一個(gè)動態(tài)領(lǐng)導(dǎo)者、多個(gè)靜態(tài)或者動態(tài)領(lǐng)導(dǎo)者的一致性問題。2.2.2二階一致性多智能體系統(tǒng)二階一致性的研究中假設(shè)智能體具有下列形式的狀態(tài)方程：(i-1,2，…,ni-1,2，…,nii(Ix-uii采用一致性協(xié)議：u=kv+Za(x-x)ii ijji莊N則閉環(huán)系統(tǒng)的矩陣形式為：^=\l?（A+BK）-L?BF1=①己n其中，A=oo,B=i,K=b,k],F=1,0],^=\x,x,^,x,v1,v2,--v}以Jordan標(biāo)準(zhǔn)型理論為基礎(chǔ)分析閉環(huán)線性系統(tǒng)的一致性，相應(yīng)結(jié)論為：定理3當(dāng)系統(tǒng)具有固定無向連通拓?fù)浣Y(jié)構(gòu)時(shí)，協(xié)議（8）可實(shí)現(xiàn)平均一致性，即當(dāng)tfg時(shí)，x（t）-1Zx（0）,v（t）-0。當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)在無向連通圖之間切換時(shí)，i niii=1協(xié)議（8）可解決平均一致性。在上述結(jié)論的基礎(chǔ)上，有學(xué)者進(jìn)一步拓展了上述一致性算法，考慮了有界控制輸入，無相對速度測量時(shí)的各種二階一致性問題。2.2.3高階一致性近來，許多研究人員對多智能體系統(tǒng)一致性問題的研究轉(zhuǎn)移到了智能體為n階智能體的情況，并以線性矩陣不等式給出系統(tǒng)一致性需要滿足的條件，在一定假設(shè)分析給出線性矩陣不等式的可解性，并通過實(shí)例驗(yàn)證了算法的有效性?？紤]智能體具有狀態(tài)方程：TOC\o"1-5"\h\zx=Ax+Bu （9）iii或：x=Ax+Bu y=Cx （10）iii ii對方程（9）用狀態(tài)反饋：u=Kbx+ZKbxiii ijjN對方程（10）靜態(tài)輸出反饋：u=Kby+ZKbyiii ijjeN.或動態(tài)輸出反饋：x=Ax+By u=Cx+D+LcyDD DD其中，L=L二Icn2.3一致性的應(yīng)用一致性在協(xié)作控制中的應(yīng)用一致性是多智能體實(shí)現(xiàn)協(xié)同合作、完成共同制定任務(wù)的基礎(chǔ)。目前，有許多學(xué)者開展了關(guān)于一致性應(yīng)用問題的研究，如聚集問題、蜂涌問題、編隊(duì)控制問題等。聚集問題要求對每一個(gè)智能體同時(shí)達(dá)到指定的位置，文獻(xiàn)[9]采用一致性搜索思想討論了同步情形和異步情形下的聚集問題；文獻(xiàn)[10]分別就固定拓?fù)浣Y(jié)構(gòu)和切換拓?fù)浣Y(jié)構(gòu)下，分別討論了一類速度恒定，通過局部反饋校正方向的智能體系統(tǒng)的峰擁問題。同步問題同步問題主要是在假定信息交換拓?fù)浣Y(jié)構(gòu)在完全圖的情況下，通過智能體之間的信息交換，修正智能體的動力學(xué)，最終實(shí)現(xiàn)同步性。筆者所研究的隨機(jī)連接的多智能體系統(tǒng)，和以往確定性的框架不同的是多智能體系統(tǒng)中的多智能體是具有馬爾科夫性質(zhì)，行為是隨機(jī)的。每個(gè)多智能體的狀態(tài)隨時(shí)間變化建模成一個(gè)有限維的連續(xù)馬爾科夫鏈。在這種情形下，一致性是當(dāng)所有多智能體的概率向量達(dá)到一個(gè)共同的穩(wěn)定的概率向量，因此在完全隨機(jī)的背景下，討論概率一致性才是有意義的。三．結(jié)束語對現(xiàn)有文獻(xiàn)中的一致性協(xié)議進(jìn)行了比較詳細(xì)的總結(jié)和分析，由于多智能體一致性相關(guān)研究問題的多樣性，本文僅對具有代表性的一部分智能體相關(guān)的一致性協(xié)議進(jìn)行了綜述。此外，關(guān)于多智能體系統(tǒng)一致性問題，還有許多的研究方向和研究熱點(diǎn)如隨機(jī)一致性，非線性一致性協(xié)議等。關(guān)于多智能體一致性問題，還有許多的問題亟待研究和解決。四．參考文獻(xiàn)[1]CvetkovicD,RowlinsonP,SimicS,etal.AlgebraicGraphTheory[M]//Algebraicgraphtheory.CambridgeUniversityPress,1974:xvi+298[2]RenW,BeardRW,AtkinsEM.Asurveyofconsensusproblemsinmulti-agentcoordination?//AmericanControlConference,2005.Proceedingsofthe.IEEE,2005:1859-1864vol.3[3]Olfati-SaberR,FaxJA,MurrayRM.ConsensusandCooperationinNetworkedMulti-AgentSystems[J].ProceedingsoftheIEEE,2007,95(1):215-233[4]XiaoF,WangL.Consensusprotocolsfordiscrete-timemulti-agentsystemswithtime-varyingdelays[J].Automatica,2008,44(10):2577-2582[5]RenW,AtkinsE.Second-orderconsensusprotocolsinmultiplevehiclesystemswithlocalinteractions[C]//AIAAGuidance,Navigation,andControlConferenceandExhibit.2005:6238[6]RenW.Consensusbasedformationcontrolstrategiesformulti-vehiclesystems[C]//AmericanControlConference,2006.IEEE,2006:6pp[7]ZhaiG,OkunoS,ImaeJ,etal.Consensusalgorithmsformulti-agentsystems:Amatrixinequalitybasedapproach[C]//Networking,SensingandControl,2009.ICNSC'09.InternationalConferenceon.IEEE,2009:891-896[8]ZhaiG,OkunoS,ImaeJ,etal.Anewconsensusalgorithmformulti-agentsystemsviadynamicoutputfeedbackcontrol[C]//ControlApplications,(CCA)&IntelligentControl,(ISIC),2009IEEE.IEEE,2009:890-895[9]LinJ,MorseAS,AndersonBDO.The