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

1、多智能體系統(tǒng)一致性綜述多智能體系統(tǒng)在20世紀(jì)80年代后期成為分布式人工智能研究中的主要研究 對(duì)象。研 究多智能體系統(tǒng)的主要目的就是期望功能相對(duì)簡(jiǎn)單的智能體系統(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)、交通控制、社會(huì)仿真、虛擬現(xiàn)實(shí)、計(jì) 算機(jī)游戲、軍事等方面廣泛應(yīng)用。多智能體的分布式協(xié)調(diào)合作能力是多智能體系統(tǒng)的基 礎(chǔ)，是發(fā)揮多智能體系統(tǒng)優(yōu)勢(shì)的關(guān)鍵，也是整個(gè)系統(tǒng)智能性的體現(xiàn)。在多智能體分布式協(xié)調(diào)合作控制問(wèn)題中，一致性問(wèn)題作為智能體之間合作協(xié)調(diào)控制的 基礎(chǔ)，具有重要的現(xiàn)實(shí)意義和理論價(jià)值。所謂一致

2、性是指隨著時(shí)間的演化，一個(gè)多智能 體系統(tǒng)中所有智能體的某一個(gè)狀態(tài)趨于一致。一致性協(xié)議是智能體之間相互作用、傳遞 信息的規(guī)則，它描述了每個(gè)智能體和其相鄰的智能體的信息交互過(guò)程。當(dāng)一組智能體要 合作共同去完成一項(xiàng)任務(wù)，合作控制策略的有效性表現(xiàn)在多智能體必須能夠應(yīng)對(duì)各種不可 預(yù)知的形式和突然變化的環(huán)境，必須對(duì)任務(wù)達(dá)成一致意見(jiàn)，這就要求智能體系統(tǒng)隨著環(huán) 境的變化能夠達(dá)到一致。因此，智能體之間協(xié)調(diào)合作控制的一個(gè)首要條件是多智能體達(dá)到 致。近年來(lái)，一致性問(wèn)題的研究發(fā)展迅速，包括生物科學(xué)、物理科學(xué)、系統(tǒng)與控制科學(xué)、 計(jì)算機(jī)科學(xué)等各個(gè)領(lǐng)域都對(duì)一致性問(wèn)題從不同層面進(jìn)行了深入分析，研究進(jìn)展主要集中在 群體集、蜂涌

3、、聚集、傳感器網(wǎng)絡(luò)估計(jì)等問(wèn)題。目前，許多學(xué)科的研究人員都開(kāi)展了多智能體系統(tǒng)的一致性問(wèn)題的研究，比如多智能 體分布式一致性協(xié)議、多智能體協(xié)作、蜂涌問(wèn)題、聚集問(wèn)題等等。下面，主要對(duì)現(xiàn)有文 獻(xiàn)中多智能體一致性協(xié)議進(jìn)行了總結(jié)，并對(duì)相關(guān)應(yīng)用進(jìn)行簡(jiǎn)單的介紹。1.1圖論基礎(chǔ)多智能體系統(tǒng)是指由多個(gè)具有獨(dú)立自主能力的智能體通過(guò)一定的信息傳遞方式相互作 用形成的系統(tǒng)；如果把系統(tǒng)中的每一個(gè)智能體看成是一個(gè)節(jié)點(diǎn)，任意兩個(gè)節(jié)點(diǎn)傳遞的智 能體之間用有向邊來(lái)連接的話，智能體的拓?fù)浣Y(jié)構(gòu)就可以用相應(yīng)的有向圖來(lái)表示。用G (V, E, A)來(lái)表示一個(gè)有向加權(quán)圖，其中V vbV2, ,vn代表圖的n個(gè)頂點(diǎn)；E V V是邊集合，如果

4、存在從第i個(gè)頂點(diǎn)到第j個(gè)頂點(diǎn)的信息流，則有eij (Vi, vj) E； A 是非負(fù)加權(quán)鄰接矩陣eijE aijO；節(jié)點(diǎn)Vi的鄰居集定義為Ni Vj| (v, Vj) E。如果對(duì)所 有的eijE意識(shí)著ejiE,則稱G是無(wú)向圖。2個(gè)不同的節(jié)點(diǎn)Vi和v j之間有有向路徑是指存在1個(gè)有序節(jié)點(diǎn)序列 (vi , vk ), (vk , Vk ), , (v% vj ；如果圖G中任意兩個(gè)不同的結(jié)點(diǎn)間都存在1條有向路 徑，則稱G是強(qiáng)連通圖；如果G是無(wú)向的，則稱G是連通圖。圖G有有向生成樹(shù)指的 是圖G存在1個(gè)包含所有定點(diǎn)的子圖，除了唯一的根節(jié)點(diǎn)以外，其余節(jié)點(diǎn) 有且僅有1個(gè) 父節(jié)點(diǎn)。二.主要研究?jī)?nèi)容2.1多智能

5、體系統(tǒng)一致性問(wèn)題描述令Xi 表示圖中第i個(gè)頂點(diǎn)Vi的狀態(tài)且滿足x f (xi ,ui ),這樣可利用二元組(G,x)來(lái)表示動(dòng)態(tài)多智能體網(wǎng)絡(luò)系統(tǒng)，其中x (xr,x2-, ,xnOs系統(tǒng)狀態(tài)方程為xF (x, u) o如果對(duì)于所有的i, j ,都有I im Xi (t) xj (t) 0,則稱多智能體系統(tǒng)實(shí) 現(xiàn)一致 性。2.2 一致性協(xié)議2. 2. 1 一階一致性在早期關(guān)于一致性問(wèn)題的研究中，絕大多數(shù)研究工作針對(duì)智能體為一階智能體的情 形，分析不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下實(shí)現(xiàn)一致性需要滿足的條件和一致性實(shí)現(xiàn)時(shí)的收斂值。(1)連續(xù)時(shí)間情形當(dāng)網(wǎng)絡(luò)中的智能體均具有形如：Xi Ui ( Xi R)(1)的狀態(tài)方程

6、時(shí)，經(jīng)常采用一致性協(xié)議為：Uiaij (xj Xi ) (2)iN因此，在上述一致性協(xié)議下的閉環(huán)系統(tǒng)為X Lx ,系統(tǒng)(1)的解為x(t) e“x(0),可以利 用線性系統(tǒng)理論來(lái)分析系統(tǒng)的一致性問(wèn)題。在固定拓?fù)浣Y(jié)構(gòu)下，一致性的相關(guān)結(jié)論為：定理1假定G有一個(gè)有向生成樹(shù)，L為其拉普拉斯矩陣且有L 1 0 , L 0 ,*11 ,則在協(xié)議(2)作用下，多智能體系統(tǒng)可實(shí)現(xiàn)一致性，且limxi(t) Ylx(0) o特別地，當(dāng)G為無(wú)向連通圖或強(qiáng)連通平衡圖時(shí)，多智能體系統(tǒng)Xi ViXiUii 1,2, ,n7)n可實(shí)現(xiàn)平均一致性，即I imxi (t) Xi (0) o午多場(chǎng)合下，由于節(jié)點(diǎn)間連接的建立或失

7、敗，多智能體系統(tǒng)的拓?fù)浣Y(jié)構(gòu)往往是動(dòng)態(tài)發(fā)生變化的。擁有動(dòng)態(tài)網(wǎng)絡(luò)的系統(tǒng)一般稱之為切換網(wǎng)絡(luò)，切換網(wǎng) 絡(luò)可以用Go (t )來(lái)表示，其中(t):R J 1,2, ,m)為切換信號(hào)，GI,G2, ,G4為所有可 能的拓?fù)浣Y(jié)構(gòu)組成的集合。在協(xié)議(2)的作用下，且有切換拓?fù)浣Y(jié)構(gòu)的閉環(huán)系統(tǒng)為：x L (GO x(3)如果上述系統(tǒng)僅在離散時(shí)刻1, 2, , n(0 12nt)處切換，則系統(tǒng)(3)的解為：.( (t Th L( (G0( h 1) ( ( h-1： . Le 02 皿0仁0) )x(t) e e e e x (0)系統(tǒng)一致性分析轉(zhuǎn)化為多個(gè)具有非負(fù)對(duì)角的隨機(jī)矩陣乘積的極限問(wèn)題 的分析。在切換拓?fù)浣Y(jié)構(gòu)

8、下，一致性的相關(guān)結(jié)論為：定理2假定切換網(wǎng)絡(luò)在任意長(zhǎng)度有上界的時(shí)間間隔內(nèi)均有一個(gè)有向生成樹(shù)，則在協(xié)議(2) 作用下，切換多智能體系統(tǒng)可漸進(jìn)實(shí)現(xiàn)一致性。(2)離散時(shí)間情形當(dāng)網(wǎng)絡(luò)中的智能體均具有形如：Xi (k 1) Xi (k) us (k)(4)的狀態(tài)方程時(shí)，采用一致性協(xié)議：Ui a.j (xj (k) 一 Xi ( k)(5)J N i因此，在上述一致性協(xié)議下形成的閉環(huán)系統(tǒng)為：x(k 1) Px(k)(6)式中，PI E L0,1 ,是網(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é)者分別考慮

9、帶時(shí)滯的一致性、有一個(gè)動(dòng)態(tài)領(lǐng)導(dǎo)者、多個(gè)靜態(tài)或者動(dòng)態(tài)領(lǐng)導(dǎo)者的一致性問(wèn)題。2. 2. 2二階一致性多智能體系統(tǒng)二階一致性的研究中假設(shè)智能體具有下列形式的狀態(tài)方程:采用一致性協(xié)議:Ui kvi a.j (xj Xi )則閉環(huán)系統(tǒng)的矩陣形式為:In (A BK)-L BF中 A g 3,L !1以Jordan標(biāo)準(zhǔn)型理論為基礎(chǔ)分析閉環(huán)線性系統(tǒng)的一致性，相應(yīng)結(jié)論為：定理3當(dāng)系統(tǒng)具有固定無(wú)向連通拓?fù)浣Y(jié)構(gòu)時(shí)，協(xié)議(8)可實(shí)現(xiàn)平均一致性，即當(dāng)t 時(shí)，Xi(t) 1 Xi(0),Vi(t) 0 o當(dāng)網(wǎng)也結(jié)構(gòu)在無(wú)向連通圖之間切換時(shí)，ni1協(xié)議(8)可解決平均一致性。在上述結(jié)論的基礎(chǔ)上，有學(xué)者進(jìn)一步拓展了上述一致性算

10、法，考慮了有界控制輸入，無(wú)相對(duì)速度測(cè)量時(shí)的各種二階一致性問(wèn)題。2. 2. 3高階一致性近來(lái)，許多研究人員對(duì)多智能體系統(tǒng)一致性問(wèn)題的研究轉(zhuǎn)移到了智能體為n階智能體的 情況，并以線性矩陣不等式給出系統(tǒng)一致性需要滿足的條件，在一定 假設(shè)分析給出線性矩 陣不等式的可解性，并通過(guò)實(shí)例驗(yàn)證了算法的有效性?？紤]智能體具有狀態(tài)方程：Xi Ax. Bui9)i/.Xi Axi Bui yi Cxi)對(duì)方程(9)用狀態(tài)反饋:ui KrxiKrxjjHi對(duì)方程(10)靜態(tài)輸出反饋:Ui Kryi Kr yj或動(dòng)態(tài)輸出反饋：x AD x BD y u CD x DD Ley其中，LcL In2.3 一致性的應(yīng)用2.3

11、.1 一致性在協(xié)作控制中的應(yīng)用一致性是多智能體實(shí)現(xiàn)協(xié)同合作、完 成共同制定任務(wù)的基礎(chǔ)。目前，有許多學(xué)者開(kāi)展了關(guān)于一致性應(yīng)用問(wèn)題的研究，如聚集問(wèn) 題、蜂涌問(wèn)題、編隊(duì)控制問(wèn)題等。聚集問(wèn)題要求對(duì)每一個(gè)智能體同時(shí)達(dá)到指定的位置，文 獻(xiàn)9采用一致性搜索思想討論了同步情形和異步情形下的聚集問(wèn)題；文獻(xiàn)10分別就 固定拓?fù)浣Y(jié)構(gòu)和切換拓?fù)浣Y(jié)構(gòu)下，分別討論了一類速度恒定，通過(guò)局部反饋校正方向的智 能體系統(tǒng)的峰擁問(wèn)題。2.3.2同步問(wèn)題同步問(wèn)題主要是在假定信息交換拓?fù)浣Y(jié)構(gòu)在完全圖的情況下，通過(guò)智能體 之間的信息交換，修正智能體的動(dòng)力學(xué)，最終實(shí)現(xiàn)同步性。筆者所研究的隨機(jī)連接的多智能體系統(tǒng)，和以往確定性的框架不同的是多

12、智能體系統(tǒng) 中的多智能體是具有馬爾科夫性質(zhì)，行為是隨機(jī)的。每個(gè)多智能體的狀態(tài)隨時(shí)間變化建模 成一個(gè)有限維的連續(xù)馬爾科夫鏈。在這種情形下，一致性是當(dāng)所有多智能體的概率向量達(dá) 到一個(gè)共同的穩(wěn)定的概率向量，因此在完全隨機(jī)的背景下，討論概率一致性才是有意義 的。三.結(jié)束語(yǔ)三. 結(jié)束語(yǔ)對(duì)現(xiàn)有文獻(xiàn)中的一致性協(xié)議進(jìn)行了比較詳細(xì)的總結(jié)和分析，由于多智能體一致性相關(guān)研究問(wèn)題的多樣性，本文僅對(duì)具有代表性的一部分智能體相關(guān)的一致性協(xié)議進(jìn)行 了綜述。此外，關(guān)于多智能體系統(tǒng)一致性問(wèn)題，還有許多的研究方向和研究熱點(diǎn)如隨機(jī)一 致性，非線性一致性協(xié)議等。關(guān)于多智能體一致性問(wèn)題，還有 許多的問(wèn)題亟待研究和解 決。四. 參考文獻(xiàn)

13、1 Cvetkovic D, Row I i nson P, S imi c S, et a I. Algebra i c Graph TheoryM/ Algebraic graph theory. Cambr idge University Press, 1974:xvi+2982 Ren W, Beard R W, Atk i ns E M. A survey of consensus prob Iems i n multi- agent coord i nationC/ Amer ican ControI Conferenee, 2005. Proceed ings of the. I

14、EEE, 2005:1859-1864 vol. 33 01 fat i-Saber R, Fax J A, Murray R M. Consensus and Cooperat i on i n Networked Multi-Agent SystemsJ. Proceed i ngs of the I EEE, 2007, 95(1):215- 2334 X i ao F, Wang L. Consensus protoco Is for d i serete-time multi-agent systemswith time-varying de I aysJ. Automat ica,

15、 2008, 44(10) : 2577-25825 Ren W, Atkins E. Second-order consensusp rotocols in multiple vehicIe systems with I oca I interactions C/AIAA Gu i danee, Navigation, and ControlConference and Exhibit. 2005: 62386 Ren W. Consensus based formation controI strategies for multi-vehicle syst- ems C/Amer ican

16、 ControI Conference, 2006. I EEE, 2006: 6 pp7 Zha i G, Okuno S, Imae J, et al. Consensus a Igor ithms for multi-agent systems: A matr ix inequaI ity based approachC/Networking, Sensing andControl, 2009. ICNSC09. Internat i onaI Conference on. I EEE, 2009: 891-8968 Zha i G, Okuno S, Imae J, et a I. A new consensus a Igor ithm for multi-agent systems via dynamic output feedback control C/ControlApplications, (CCA) & Intel Iigent Control, (ISIC), 2009 IEEE. IEEE, 2009: 890-8959 Lin J, Morse A S, Anderson B D 0. The multi-ag