馮元珍

(南京理工大學(xué)自動化學(xué)院,江蘇 南京 210019；南京人口管理干部學(xué)院基礎(chǔ)部,江蘇 南京 210042)

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

馮元珍

(南京理工大學(xué)自動化學(xué)院,江蘇 南京 210019；南京人口管理干部學(xué)院基礎(chǔ)部,江蘇 南京 210042)

系統(tǒng)地論述了多智能體系統(tǒng)一致性問題，重點對不同階動力學(xué)智能體系統(tǒng)的一致性協(xié)議進(jìn)行了總結(jié)。最后對一致性問題的相關(guān)應(yīng)用進(jìn)行了簡單總結(jié)，并探討了未來的研究方向。

多智能體系統(tǒng);一致性；協(xié)議

近年來，多智能體系統(tǒng)由于在無人駕駛飛機協(xié)作控制、編隊控制、分布式傳感器網(wǎng)絡(luò)等多個領(lǐng)域的廣泛應(yīng)用，引起了許多研究學(xué)者的關(guān)注。

一致性問題的相關(guān)研究在計算機科學(xué)領(lǐng)域特別是分布式計算方面已經(jīng)有比較長的歷史。1962年，Dr DeGroot 首次將統(tǒng)計學(xué)中的一致性理論應(yīng)用于多個傳感器不確定性問題的融合。在與多智能體系統(tǒng)相關(guān)的許多應(yīng)用中都要求網(wǎng)絡(luò)中每個智能體對一定的量達(dá)成一致，這些量可能與智能體本身的運動軌跡是沒有關(guān)系的。因此，以系統(tǒng)的理論框架對一致性問題的研究具有重要的理論意義和實際意義。目前，許多學(xué)科的研究人員都開展了多智能體系統(tǒng)一致性相關(guān)問題的研究，如多智能體分布式一致性協(xié)議、多智能體協(xié)作、蜂擁問題、聚集問題等等。下面，筆者主要對現(xiàn)有文獻(xiàn)中多智能體一致性協(xié)議進(jìn)行了總結(jié)，并對相關(guān)應(yīng)用進(jìn)行了簡單介紹?。

1 圖論基礎(chǔ)

多智能體系統(tǒng)是指由多個具有獨立自主能力的智能體通過一定的信息傳遞方式相互作用形成的系統(tǒng)；如果把系統(tǒng)中的每一個智能體看成一個結(jié)點，任意2個有信息傳遞的智能體之間用有向邊來連接的話，智能體的拓?fù)浣Y(jié)構(gòu)就可以用相應(yīng)的有向圖來表示[1]。

用G=(V,E,A)來表示一個有向加權(quán)圖，其中V={v1,v2,…,vn}代表圖的n個頂點；E?V×V是邊集合，如果存在從第i個頂點到第j個頂點的信息流，則有eij=(vi,vj)∈E；A是非負(fù)加權(quán)鄰接矩陣eij∈E?aij>0；結(jié)點vi的鄰居集定義為Ni={vj|(vi,vj)∈E}，Ni的勢稱為結(jié)點vi的出度，記作deg(vi)，D=diag{deg(v1),deg(v2),…,deg(vn)}稱為G的度矩陣。如果對所有的eij∈E意味著eji∈E，則稱G是無向圖。

2個不同的結(jié)點vi和vj之間有有向路徑是指存在1個有序結(jié)點序列(vi,vk1),(vk1,vk2),…,(vkl,vj)；如果圖G中任意2個不同的結(jié)點間都存在1條有向路徑，則稱G是強連通圖；如果G是無向的，則稱G是連通圖。圖G有有向生成樹指的是圖G中存在1個包含所有頂點的子圖，除了唯一的根結(jié)點外，其余結(jié)點有且僅有1個父結(jié)點。

2 多智能體系統(tǒng)一致性問題描述

分布式一致性協(xié)議就是指采用狀態(tài)反饋ui=ki(xj1,xj2,…,xjl)或輸出反饋ui=ki(yj1,yj2,…,yjl)，使(G,x)實現(xiàn)一致性，其中{vj1,vj2,…,vjl}?{i}∪Ni(l

3 一致性協(xié)議

3.1一階一致性

在早期關(guān)于一致性問題的研究中，絕大多數(shù)研究工作針對智能體為一階智能體的情形，分析不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下實現(xiàn)一致性需要滿足的條件和一致性實現(xiàn)時的收斂值[3]。

1)連續(xù)時間情形 當(dāng)網(wǎng)絡(luò)中的智能體均具有形如：

(1)

的狀態(tài)方程時，經(jīng)常采用一致性協(xié)議為：

(2)

在固定拓?fù)浣Y(jié)構(gòu)下，一致性的相關(guān)結(jié)論為：

許多場合下，由于結(jié)點間連接的建立或失敗，多智能體系統(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)來表示，其中σ(t):R→J={1,2,…,m}為切換信號，{G1,G2,…,Gm}為所有可能的拓?fù)浣Y(jié)構(gòu)組成的集合。在協(xié)議(2)的作用下，具有切換拓?fù)浣Y(jié)構(gòu)的閉環(huán)系統(tǒng)為：

(3)

如果上述系統(tǒng)僅在離散時刻τ1,τ2,…,τn(0<τ1<τ2<…τn≤t)處切換，則系統(tǒng)(3)的解為：

x(t)=e-L(Gσ(h))(t-τh)e-L(Gσ(h-1))(τh-τh-1)…e-L(Gσ(2))(τ2-τ1)e-L(Gσ(1))τ1x(0)

系統(tǒng)一致性分析轉(zhuǎn)化為多個具有非負(fù)對角元的隨機矩陣乘積的極限問題的分析。

在切換拓?fù)浣Y(jié)構(gòu)下，一致性的相關(guān)結(jié)論為：

定理2假定切換網(wǎng)絡(luò)在任意長度有上界的時間間隔內(nèi)均有一個有向生成樹，則在協(xié)議(2)作用下，切換多智能體系統(tǒng)可漸近實現(xiàn)一致性。

2)離散時間情形 當(dāng)網(wǎng)絡(luò)中的智能體均具有形如:

xi(k+1)=xi(k)+ui(k)

(4)

的狀態(tài)方程時，采用一致性協(xié)議:

(5)

因此，在上述一致性協(xié)議下形成的閉環(huán)系統(tǒng)為：

x(k+1)=Px(k)

(6)

在固定拓?fù)浜颓袚Q拓?fù)浣Y(jié)構(gòu)下，多智能體系統(tǒng)有類似定理1和定理2相應(yīng)的結(jié)論。

3)其他研究熱點 除了上述關(guān)于一致性的經(jīng)典結(jié)論外，還有學(xué)者分別考慮帶時滯的一致性、有一個動態(tài)領(lǐng)導(dǎo)者、多個靜態(tài)或者動態(tài)領(lǐng)導(dǎo)者的一致性問題。還有一些研究工作針對實現(xiàn)一致性時不同的一致性值來分析網(wǎng)絡(luò)應(yīng)當(dāng)具備的結(jié)構(gòu)。具體結(jié)論不再詳述，感興趣的讀者可以參閱相關(guān)文獻(xiàn)[4]。

3.2二階一致性

多智能體系統(tǒng)二階一致性[5]的研究中假設(shè)智能體具有下列形式的狀態(tài)方程：

(7)

采用一致性協(xié)議：

(8)

則閉環(huán)系統(tǒng)的矩陣形式為：

以Jordan標(biāo)準(zhǔn)形理論為基礎(chǔ)分析閉環(huán)線性系統(tǒng)的一致性，相應(yīng)結(jié)論為：

在上述結(jié)論的基礎(chǔ)上，有學(xué)者進(jìn)一步拓展了上述一致性算法，考慮了有界控制輸入，無相對速度測量時的各種二階一致性問題[6]。

3.3高階一致性

近來，許多研究人員對多智能體系統(tǒng)一致性問題的研究轉(zhuǎn)移到了智能體為n階智能體[7,8]的情況，并以線性矩陣不等式形式給出系統(tǒng)一致性需要滿足的條件，在一定假設(shè)下分析給出線性矩陣不等式的可解性，并通過實例驗證了算法的有效性。

考慮智能體具有狀態(tài)方程：

(9)

或:

(10)

對方程(9)用狀態(tài)反饋：

對方程(10)靜態(tài)輸出反饋：

或動態(tài)輸出反饋：

其中,LC=L?In。

4 一致性的應(yīng)用

4.1一致性在協(xié)作控制中的應(yīng)用

一致性是多智能體實現(xiàn)協(xié)同合作、完成共同制定任務(wù)的基礎(chǔ)。目前，有許多學(xué)者開展了關(guān)于一致性應(yīng)用問題的研究，如聚集問題、蜂擁問題、編隊控制問題等。聚集問題要求每一個智能體同時到達(dá)指定的位置，文獻(xiàn)[9]采用一致性搜索思想討論了同步情形和異步情形下的聚集問題;文獻(xiàn)[10]分別就固定拓?fù)浣Y(jié)構(gòu)和切換拓?fù)浣Y(jié)構(gòu)下，分別討論了一類速度恒定，通過局部反饋校正移動方向的智能體系統(tǒng)蜂擁問題。

4.2同步問題

同步問題主要是在假定信息交換拓?fù)浣Y(jié)構(gòu)在完全圖的情況下，通過智能體之間的信息交換，修正智能體的動力學(xué)，最終實現(xiàn)同步性。

5 結(jié) 語

對現(xiàn)有文獻(xiàn)中的一致性協(xié)議進(jìn)行了比較詳細(xì)的總結(jié)和分析，由于多智能體一致性相關(guān)研究問題的多樣性，筆者僅是對具有代表性的單積分器智能體，二階智能體以及高階智能體相關(guān)的一致性協(xié)議進(jìn)行了綜述。此外，關(guān)于多智能體系統(tǒng)一致性還有許多的研究方向和研究熱點如隨機一致性，非線性一致性協(xié)議等，感興趣的讀者可以查閱相關(guān)的文獻(xiàn)。關(guān)于多智能體一致性問題，還有許多的問題亟待研究和解決，比如在噪聲擾動下和考慮模型不確定性時對不同系統(tǒng)的一致性問題等值得研究的探討。

[1]Royle G, Godsil C. Algebraic Graph Theory[M]. New York:Springer, 2001.

[2] Ren W, Beard R W, Atkins E. A survey of consensus problems in multi-agent coordination[J]. Proceedings of the 2005 American Control Conference, 2005:1859-1864.

[3] Saber R O, Fax J A, Murray R M. Consensus and cooperation in networked multi-agent systems[J]. Proceedings of the IEEE, 2007, 95(1):215-233.

[4] Xiao F, Wang L. Consensus protocols for discrete-time multi-agent systems with time-varying delays[J]. Automatica, 2008, 44:2577-2582.

[5] Ren W, Atkins E. Second-order consensus protocols in multiple vehicle systems with local interactions[J]. Proceedings of AIAA Guidance, Navigation, and Control Conference and Exhibit, 2005, AIAA 2005-6238.

[6] Ren W. Consensus based formation control strategies for multiple-vehicle systems[J]. Proceedings of the 2006 American Control Conference, 2006:4237-4242.

[7] Zhai G, Okuno S, Imae J, Kobayashi T. Consensus algorithms for multi-agent systems: a matrix inequality based approach[J]. Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control, 2009: 891-896.

[8] Zhai G, Okuno S, Imae J, Kobayashi T. A new consensus algorithm for multi-agent systems via dynamic output feedback control[J].2009 IEEE International Symposium on Intelligent Control, 2009:890-895.

[9] Lin J, Morse A S, Anderson B D O. The multi-agent rendezvous problem[J]. Proceedings of the 42nd IEEE Conference on Decision and Control, 2003:1508-1513.

[10] Saber R O. Flocking for multi-agent dynamic systems: algorithms and theory[J]. IEEE Transaction on Automatic Control, 2006, 51(3):401-419.

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2011.03.029

TP18

1673-1409(2011)03-0084-04