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

多智能體系統(tǒng)一致性綜述引言多智能體系統(tǒng)在20世紀80年代后期成為分布式人工智能研究中的主要研究對象。研究多智能體系統(tǒng)的主要目的就是期望功能相對簡單的智能體系統(tǒng)之間進行分布式合作協(xié)調控制，最終完成復雜任務。多智能體系統(tǒng)由于其強健、可靠、高效、可擴展等特性，在科學計算、計算機網(wǎng)絡、機器人、制造業(yè)、電力系統(tǒng)、交通控制、社會仿真、虛擬現(xiàn)實、計算機游戲、軍事等方面廣泛應用。多智能體的分布式協(xié)調合作能力是多智能體系統(tǒng)的基礎，是發(fā)揮多智能體系統(tǒng)優(yōu)勢的關鍵，也是整個系統(tǒng)智能性的體現(xiàn)。在多智能體分布式協(xié)調合作控制問題中，一致性問題作為智能體之間合作協(xié)調控制的基礎，具有重要的現(xiàn)實意義和理論價值。所謂一致性是指隨著時間的演化，一個多智能體系統(tǒng)中所有智能體的某一個狀態(tài)趨于一致。一致性協(xié)議是智能體之間相互作用、傳遞信息的規(guī)則，它描述了每個智能體和其相鄰的智能體的信息交互過程。當一組智能體要合作共同去完成一項任務，合作控制策略的有效性表現(xiàn)在多智能體必須能夠應對各種不可預知的形式和突然變化的環(huán)境，必須對任務達成一致意見，這就要求智能體系統(tǒng)隨著環(huán)境的變化能夠達到一致。因此，智能體之間協(xié)調合作控制的一個首要條件是多智能體達到一致。近年來，一致性問題的研究發(fā)展迅速，包括生物科學、物理科學、系統(tǒng)與控

制科學、計算機科學等各個領域都對一致性問題從不同層面進行了深入分析，研究進展主要集中在群體集、蜂涌、聚集、傳感器網(wǎng)絡估計等問題。目前，許多學科的研究人員都開展了多智能體系統(tǒng)的一致性問題的研究，比如多智能體分布式一致性協(xié)議、多智能體協(xié)作、蜂涌問題、聚集問題等等。下面，主要對現(xiàn)有文獻中多智能體一致性協(xié)議進行了總結，并對相關應用進行簡單的介紹。1.1圖論基礎多智能體系統(tǒng)是指由多個具有獨立自主能力的智能體通過一定的信息傳遞方式相互作用形成的系統(tǒng)；如果把系統(tǒng)中的每一個智能體看成是一個節(jié)點，任意兩個節(jié)點傳遞的智能體之間用有向邊來連接的話，智能體的拓撲結構就可以用相應的有向圖來表示。用G=(V,E,A)來表示一個有向加權圖，其中V二｛wm，…M｝代表圖的n個頂點；EVV是邊集合，如果存在從第i個頂點到第j個頂點的信息流，則有eq=(V.5V.)E；A是非負加權鄰接矩陣e廠am0；節(jié)點w的鄰居集定義為N二｛Vj|(Vi5Vj)E｝。如果對所有的jE意識著jE，則稱G是無向圖。2個不同的節(jié)點V,和*之間有有向路徑是指存在1個有序節(jié)點序列(Vi；vk),(Vk「Vk2),，(vk，VJ；如果圖G中任意兩個不同的結點間都存在1條有向路徑，則稱G是強連通圖；如果G是無向的，則稱G是連通圖。圖G有有向生成樹指的是圖G存在1個包含所有定點的子圖，除了唯一的根節(jié)點以外，其余節(jié)點有且僅有1個父節(jié)點。二主要研究內(nèi)容2.1多智能體系統(tǒng)一致性問題描述令xrRq表示圖中第i個頂點V的狀態(tài)且滿足x=f(x,u)，這樣可利用二元組(G,x)來表示動態(tài)多智能體網(wǎng)絡系統(tǒng)，其中X=(xT,x：;?…Xt)T，系統(tǒng)狀態(tài)方程為x=F(x,u)o如果對于所有的耳，都有問U又⑴-Xj(t)=0，貝U稱多智能體系統(tǒng)實現(xiàn)一致性。2.2—致性協(xié)議2.2.1一階一致性在早期關于一致性問題的研究中，絕大多數(shù)研究工作針對智能體為一階智能體的情形，分析不同網(wǎng)絡拓撲結構下實現(xiàn)一致性需要滿足的條件和一致性實現(xiàn)時的收斂值。連續(xù)時間情形當網(wǎng)絡中的智能體均具有形如：為7(為R)(1)的狀態(tài)方程時，經(jīng)常采用一致性協(xié)議為：5八aq(X「xj(2)iN因此，在上述一致性協(xié)議下的閉環(huán)系統(tǒng)為x=-Lx，系統(tǒng)(1)的解為x(t)二eLtx(0)，可以利用線性系統(tǒng)理論來分析系統(tǒng)的一致性問題。在固定拓撲結構下，一致性的相關結論為：定理1假定G有一個有向生成樹，L為其拉普拉斯矩陣且有L1=0，tL=0，丁1=1，則在協(xié)議(2)作用下，多智能體系統(tǒng)可實現(xiàn)一致性，且limxi(t)二Yx(0)o特別地，當G為無向連通圖或強連通平衡圖時，多智能體系統(tǒng)可實現(xiàn)平均一致性，即limxj(t)rx(0)on許多場合下，由于節(jié)點間連接的建立或失敗，多智能體系統(tǒng)的拓撲結構往往是動態(tài)發(fā)生變化的。擁有動態(tài)網(wǎng)絡的系統(tǒng)一般稱之為切換網(wǎng)絡，切換網(wǎng)絡可以用G°(t)來表示，其中c(t):R》J=｛1,2，…，m｝為切換信號，｛G,,G2-,Gm｝為所有可能的拓撲結構組成的集合。在協(xié)議(2)的作用下，且有切換拓撲結構的閉環(huán)系統(tǒng)為：x—L(Gk)x(3)如果上述系統(tǒng)僅在離散時刻1「2,…，n(0:::1:::2:::...n口左t)處切換，則系統(tǒng)(3)的解為：(t)—L(GtI(G衛(wèi))(t-A)—L(G)(T-屯)—L(G屯(O)x(t)二e0(h))(—))e(0(，衛(wèi))(T-1)..■e"Tex(。)))系統(tǒng)一致性分析轉化為多個具有非負對角的隨機矩陣乘積的極限問題的分析。在切換拓撲結構下，一致性的相關結論為：定理2假定切換網(wǎng)絡在任意長度有上界的時間間隔內(nèi)均有一個有向生成樹，則在協(xié)議(2)作用下，切換多智能體系統(tǒng)可漸進實現(xiàn)一致性。離散時間情形當網(wǎng)絡中的智能體均具有形如：的狀態(tài)方程時，采用一致性協(xié)議：U二八ai.(x.(k)-x.(k))(5)jNi因此，在上述一致性協(xié)議下形成的閉環(huán)系統(tǒng)為：x(k1)=Px(k)(6)式中，P=1-0「：；:::1A，A是網(wǎng)絡節(jié)點的最大出度。在固定拓撲和切換拓撲結構下，多智能體系統(tǒng)有類似定理1和定理2相應的結論。其他研究熱點除了上述關于一致性的經(jīng)典結論外，還有學者分別考慮帶時滯的一致性、有一個動態(tài)領導者、多個靜態(tài)或者動態(tài)領導者的一致性問題。2.2.2二階一致性多智能體系統(tǒng)二階一致性的研究中假設智能體具有下列形式的狀態(tài)方程：i=12,n(7)采用一致性協(xié)議：*=kv+送aj(Xj_xj(8)jAi則閉環(huán)系統(tǒng)的矩陣形式為:-〔ln:(ABK)-L：BFI其中A-0°-10B-^]-bk■■F-Q蘆=lxX2J.,xF2以Jordan標準型理論為基礎分析閉環(huán)線性系統(tǒng)的一致性，相應結論為：定理3當系統(tǒng)具有固定無向連通拓撲結構時，協(xié)議(8)可實現(xiàn)平均一致性，1n即當t》：：時，Xj(t)>上、Xi(0),Vi(t)>0O當網(wǎng)絡結構在無向連通圖之間切換時，ny協(xié)議⑻可解決平均一致性。在上述結論的基礎上，有學者進一步拓展了上述一致性算法，考慮了有界控制輸入，無相對速度測量時的各種二階一致性問題。2.2.3高階一致性近來，許多研究人員對多智能體系統(tǒng)一致性問題的研究轉移到了智能體為n階智能體的情況，并以線性矩陣不等式給出系統(tǒng)一致性需要滿足的條件，在一定假設分析給出線性矩陣不等式的可解性，并通過實例驗證了算法的有效性。考慮智能體具有狀態(tài)方程：xAxBu.(9)i=i或：片二Bu.y.二C片(10)對方程(9)用狀態(tài)反饋：U-二Kp*問1對方程(10)靜態(tài)輸出反饋：U.AKby'Ky.1祠或動態(tài)輸出反饋：x=ADxBDyu二CDxDdLcy其中，L=aIn2.3—致性的應用2.3.1—致性在協(xié)作控制中的應用一致性是多智能體實現(xiàn)協(xié)同合作、完成共同制定任務的基礎。目前，有許多學者開展了關于一致性應用問題的研究，如聚集問題、蜂涌問題、編隊控制問題等。聚集問題要求對每一個智能體同時達到指定的位置，文獻[9]采用一致性搜索思想討論了同步情形和異步情形下的聚集問題；文獻[10]分別就固定拓撲結構和切換拓撲結構下，分別討論了一類速度恒定，通過局部反饋校正方向的智能體系統(tǒng)的峰擁問題。232同步問題同步問題主要是在假定信息交換拓撲結構在完全圖的情況下，通過智能體之間的信息交換，修正智能體的動力學，最終實現(xiàn)同步性。筆者所研究的隨機連接的多智能體系統(tǒng)，和以往確定性的框架不同的是多智能體系統(tǒng)中的多智能體是具有馬爾科夫性質，行為是隨機的。每個多智能體的狀態(tài)隨時間變化建模成一個有限維的連續(xù)馬爾科夫鏈。在這種情形下，一致性是當所有多智能體的概率向量達到一個共同的穩(wěn)定的概率向量，因此在完全隨機的背景下，討論概率一致性才是有意義的。三結束語一結束語對現(xiàn)有文獻中的一致性協(xié)議進行了比較詳細的總結和分析，由于多智能體一致性相關研究問題的多樣性，本文僅對具有代表性的一部分智能體相關的一致性協(xié)議進行了綜述。此外，關于多智能體系統(tǒng)一致性問題，還有許多的研究方向和研究熱點如隨機一致性，非線性一致性協(xié)議等。關于多智能體一致性問題，還有許多的問題亟待研究和解決。四參考文獻…一..C〃CvetkovicD,RowlinsonP,SimicS,etal.AlgebraicGraphTheory[M]Algebraicgraphtheory.CambridgeUniversityPress,1974:xvi+298RenW,BeardRW,AtkinsEM.Asurveyofconsensusproblemsinmulti-agentcoordination[C]AmericanControlConference,2005.Proceedingsofthe.IEEE,2005:1859-1864vol.3Olfati-SaberR,FaxJA,MurrayRM.ConsensusandCooperationinNetworkedMulti-AgentSystems[J].ProceedingsoftheIEEE,2007,95⑴:215-233XiaoF,WangL.Consensusprotocolsfordiscrete-timemulti-agentsystemswithtime-varyingdelays[J].Automatica,2008,44(10):2577-2582RenW,AtkinsE.Second-orderconsensusprotocolsinmultiplevehiclesystemswithlocalinteractions[C]//AIAAGuidanee,Navigation,andControlConferenceandExhibit.2005:6238RenW.Consensusbasedformationcontrolstrategiesformulti-vehiclesyst-ems[C]//AmericanControlConference,2006.IEEE,2006:6ppZhaiG,OkunoS,ImaeJ,etal.Consensusalgorithmsformulti-agentsystems:Amatrixinequalitybasedapproach[C]//Networking,SensingandControl,2009.ICNSC'09.InternationalConferenceon.IEEE,2009:891-896ZhaiG,OkunoS,ImaeJ,etal.Anewconsensusalgorithmformulti-agentsystemsviadynamicoutputfeedbackcontrol[C]//ControlApplications,(CCA)&IntelligentControl,(ISIC),2009IEEE.IEEE,2009:890-895LinJ,MorseAS,AndersonBDO.