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

馮元珍

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

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

馮元珍

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

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

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

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

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

1 圖論基礎

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

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

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

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一階一致性

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

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

(1)

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

(2)

在固定拓撲結構下，一致性的相關結論為：

許多場合下，由于結點間連接的建立或失敗，多智能體系統(tǒng)的拓撲結構往往是動態(tài)發(fā)生變化的。擁有動態(tài)變換網(wǎng)絡的系統(tǒng)一般稱之為切換網(wǎng)絡，切換網(wǎng)絡可以用Gσ(t)來表示，其中σ(t):R→J={1,2,…,m}為切換信號，{G1,G2,…,Gm}為所有可能的拓撲結構組成的集合。在協(xié)議(2)的作用下，具有切換拓撲結構的閉環(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)一致性分析轉化為多個具有非負對角元的隨機矩陣乘積的極限問題的分析。

在切換拓撲結構下，一致性的相關結論為：

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

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

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

(4)

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

(5)

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

x(k+1)=Px(k)

(6)

在固定拓撲和切換拓撲結構下，多智能體系統(tǒng)有類似定理1和定理2相應的結論。

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

3.2二階一致性

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

(7)

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

(8)

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

以Jordan標準形理論為基礎分析閉環(huán)線性系統(tǒng)的一致性，相應結論為：

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

3.3高階一致性

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

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

(9)

或:

(10)

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

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

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

其中,LC=L?In。

4 一致性的應用

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

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

4.2同步問題

同步問題主要是在假定信息交換拓撲結構在完全圖的情況下，通過智能體之間的信息交換，修正智能體的動力學，最終實現(xiàn)同步性。

5 結 語

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