陳旿，張鑫，金鑫，李澤宏，洪亮

西北工業(yè)大學 自動化學院，西安 710072

一種多智能體協(xié)同信息一致性算法

陳旿*，張鑫，金鑫，李澤宏，洪亮

西北工業(yè)大學 自動化學院，西安 710072

以無人機(UAVs)/導彈集群為代表的多智能體協(xié)同作戰(zhàn)在未來戰(zhàn)場中占有重要地位。協(xié)同信息的共享和一致性是多智能體系統(tǒng)完成協(xié)同、編隊、集結、同步等協(xié)同任務的關鍵基礎和前提。首先,基于鄰居系統(tǒng)和團勢能建立了信息一致性模型，將多智能體的協(xié)同信息的偏差映射為團勢能。然后，通過以并行能量最小化求解馬爾可夫隨機場最大后驗概率的方法實現(xiàn)了分布式無中心條件下的協(xié)同信息一致性。與傳統(tǒng)的一致性算法相比，所提出的算法引入了虛擬基準的概念。當無外部基準輸入時，基于平均場方法，通過鄰居之間的協(xié)同信息交互建立虛擬基準；當存在領航節(jié)點或虛擬領航節(jié)點時，將領航節(jié)點協(xié)同信息的狀態(tài)及狀態(tài)導數(shù)作為虛擬基準。仿真結果表明:所得出的算法具有對網(wǎng)絡規(guī)模不敏感、快速收斂、高魯棒性的優(yōu)點;對有/無基準輸入的情況可采用相同的算法，體現(xiàn)了算法具有較好的適應性。

多智能體；一致性；馬爾可夫隨機場；平均場；虛擬基準

隨著電子技術、計算機網(wǎng)絡技術的發(fā)展，復雜大系統(tǒng)日益成為控制系統(tǒng)的主要形式。采用集中式控制存在計算量大、故障率高、魯棒性低的缺點。多智能體系統(tǒng)具有靈活性高、易擴展、易維護、低成本的優(yōu)點，所以將集中式復雜大系統(tǒng)的結構形式替換為可分離的簡單智能體小模塊協(xié)作控制的結構形式已經(jīng)逐漸成為控制領域的一個研究熱點[1]。多智能體系統(tǒng)是指局部之間可以相互作用的、由大量簡單個體所組成的復雜網(wǎng)絡系統(tǒng)[2]。多智能體系統(tǒng)的主要控制目標是通過分布式協(xié)議，在沒有組織者和協(xié)調者的情況下，使各個智能體的狀態(tài)達到一致[1-3]。多智能體協(xié)同信息一致性問題的最典型應用是無人航行平臺的集群協(xié)調控制問題。同時，一致性問題也是解決集結問題、編隊問題、同步問題、聚集問題、分布式估計、分布式最優(yōu)化等問題的基礎。近十年來，世界各國學者對一致性算法進行研究并得到大量研究成果。

所謂一致性問題是指所有智能體的狀態(tài)在分布式協(xié)議的作用下，漸近地達到一個相同的協(xié)調值[1]。一致性問題起源于分布式計算、分布式?jīng)Q策和統(tǒng)計物理學。其研究可追溯至20世紀80年代的分布式?jīng)Q策問題(Distributed Decision-Making Problems)[4-5]，1992年，Benediktsson首次將統(tǒng)計一致性方法應用于傳感器網(wǎng)絡的信息融合中[6]。Vicsek在1995年從統(tǒng)計力學的角度出發(fā)，建立了一個一致性動力性模型，仿真結果表明，整個群體中的個體將會在行為上趨向一致[7]。Jadbabaie等在2003年發(fā)表文章，運用圖論和Markov鏈對Vicsek模型進行了嚴格理論證明，結論表明當網(wǎng)絡拓撲在有限時間內為無向連通圖時，所有狀態(tài)將趨于一致[8]。這篇文章引發(fā)了對一致性問題研究的熱潮，此后涌現(xiàn)了大量的關于一致性算法的研究成果。一些知名的國際期刊專門出版了關于一致性問題的特刊[9-13]。較為代表性的研究成果有：Ren的研究結論指出在動態(tài)拓撲網(wǎng)絡中，系統(tǒng)取得一致性的條件是有向通信網(wǎng)絡是強連通的并包含有一簇有向生成樹[14]；Li給出了含有異構子系統(tǒng)的多智能體系統(tǒng)收斂到一致的充分必要條件[15]。文獻[16]研究了有噪聲測量和傳輸延遲條件下的一致性問題。近年來一致性算法已經(jīng)在無人航行器的編隊控制[17]、智能交通[18]、傳感器網(wǎng)絡信息融合[19]、網(wǎng)絡時鐘同步[20]等多個領域得到廣泛應用，成為系統(tǒng)與控制領域的一個重要研究課題。

盡管現(xiàn)有的分布式一致性算法主要應用在編隊、聚集和跟蹤上，但是算法研究的動力學模型已經(jīng)從最開始假設的理想的線性系統(tǒng)轉變成模擬實際環(huán)境的非線性系統(tǒng)，其中線性系統(tǒng)一般分為一階線性系統(tǒng)、二階線性系統(tǒng)和高階線性系統(tǒng)；非線性系統(tǒng)一般分為多拉格朗日系統(tǒng)和剛體姿態(tài)系統(tǒng)等，因而分布式一致性算法需要開始考慮智能體自身的動態(tài)特性以及現(xiàn)實復雜環(huán)境對多智能體系統(tǒng)的影響。

多智能體系統(tǒng)通過鄰居節(jié)點進行信息交換是達成一致性的關鍵，而現(xiàn)實網(wǎng)絡存在的約束條件可以被大致分成兩類，一類是通信信道的約束問題：時延、丟包、通信帶寬、測量噪聲等；另一類是多智能體網(wǎng)絡拓撲結構變化問題。常見的分析方法主要包括：矩陣論方法、李雅普洛夫泛函方法和頻域分析法等。

無人航行體編隊與協(xié)同控制是多智能體一致性算法的一個重要應用領域和發(fā)展方向。無人航行體，如無人機、飛航彈，以一定的數(shù)量規(guī)模編隊實施協(xié)同作戰(zhàn)是“網(wǎng)絡中心戰(zhàn)”的重要模式之一。與單架或無協(xié)同關系的無人航行體相比，多航行體協(xié)同作戰(zhàn)可以提高突防能力、電子對抗能力、對低可探測目標的搜索能力，同時減少戰(zhàn)斗消耗，提高無人航行體的整體作戰(zhàn)能力[21]。無人航行體編隊與協(xié)同控制對信息一致性有其特殊的需求：首先，無人航行平臺協(xié)同作戰(zhàn)需要在一定指定的時間段內完成，這就要求多智能體之間的協(xié)同信息應當在有限時間內達到一致；其次，無人航行體編隊根據(jù)作戰(zhàn)任務的不同，對編隊規(guī)模大小的需求也不同。比如導彈自主編隊的規(guī)?？煞譃楣?jié)數(shù)在2～9個之間的鄰接規(guī)模編隊、節(jié)數(shù)在9～18個之間的小規(guī)模編隊、節(jié)數(shù)在18～36個之間的中等規(guī)模編隊、節(jié)點數(shù)在36～72個之間的大規(guī)模編隊與節(jié)點數(shù)大于72個的超大規(guī)模編隊[21]。這些不同規(guī)模的導彈編隊具有基本相同的作戰(zhàn)周期和制導周期，要求能在基本相同的時間周期內達到信息一致性。再次，無人航行體編隊協(xié)同作戰(zhàn)工作在一定的對抗環(huán)境中，存在節(jié)點損失和新節(jié)點加入的情況，甚至有編隊拆分和合并的情況存在，這造成了高度動態(tài)的通信拓撲結構，且通信時延不確定。這就對信息一致性算法的魯棒性有較高要求，即在動態(tài)網(wǎng)絡拓撲及不完全通信條件下，信息一致性的收斂性能基本保持不變。最后，時空配準是多無人航行平臺執(zhí)行協(xié)同任務的前提，時鐘同步是多無人航行平臺編隊與協(xié)同作戰(zhàn)最基本、最重要的一致性信息。

現(xiàn)有的分布式一致性算法基本是都是漸近算法，在理論上需要無窮長的時間才能達到信息一致性。目前在實際應用中，一般是通過指定一個收斂周期來解決無窮長收斂時間的問題[21]。此外，無人航行平臺協(xié)同作戰(zhàn)編隊具有不同的編隊規(guī)模，現(xiàn)有的一致性算法的收斂時間會隨著編隊規(guī)模的增加快速增加，較難滿足不同編隊規(guī)模條件下收斂時間基本一致的要求。最后，現(xiàn)有的信息一致性算法大部分是通過鄰居節(jié)點之間進行信息交互達到一致的，不依賴于中心節(jié)點，對動態(tài)網(wǎng)絡拓撲具有良好的適應性。

本文針對無人航行體編隊所面對的上述問題，提出了一種基于平均場的分布式協(xié)同一致性算法。該算法在不同網(wǎng)絡規(guī)模下的收斂時間基本保持不變，精度高，且對動態(tài)拓撲及丟包有很好的適應性。該方法也可以應用到其他多智能體的信息一致性場合，如分布式融合估計等[22]。

1 問題描述

一致性是指多個智能體對所關心的協(xié)同變量的取值達成共識。記該協(xié)同變量為信息狀態(tài)x。假設在多智能體編隊中有n個智能體，在本文余下的部分中，將統(tǒng)一以節(jié)點表示智能體編隊中的個體。編隊的通信拓撲可以用有向圖G=(V,E)來表示，其中V={v1,v2,…,vn}表示節(jié)點的集合，E?V×V表示節(jié)點間鏈路的集合。現(xiàn)有的多智能體信息一致性的定義如下：

如果對于一個多智能體編隊中所有節(jié)點的協(xié)同信息狀態(tài)x=[x1,x2,…,xn] 都有式(1)成立：

(1)

則稱多智能體編隊達到一致性。

2 信息一致性模型

為了便于描述信息一致性模型，首先給出鄰域系統(tǒng)的定義。一個鄰域系統(tǒng)N可以定義為

N=Ni|?i∈V

(2)

式中：Ni為節(jié)點i的鄰居節(jié)點集合，其相鄰關系具有如下特性[23]：

1) 任意給定一點i與其自身并不構成鄰居關系：i?Ni。

2) 相鄰關系是相互的。

i∈Nj??j∈Ni

如果式(1)成立，則稱智能體編隊中任意兩個互為鄰居的節(jié)點達成信息狀態(tài)一致。由于智能體編隊中節(jié)點數(shù)目為有限多個，若其中任意互為鄰居界節(jié)點的兩個節(jié)點信息達成一致，則智能體編隊達到一致。因此，可以通過任意節(jié)點和與其有直接通信關系的所有鄰居節(jié)點相互作用，達到節(jié)點之間信息一致，進而實現(xiàn)智能體編隊的協(xié)同信息一致性。這種方法也符合智能體編隊的實際工作場景，可以降低網(wǎng)絡負載，同時降低節(jié)點被無線探測到的機率。故信息一致性模型可以描述為

(3)

式(3)所產(chǎn)生的一致性收斂點取決于編隊節(jié)點初始信息狀態(tài)，是一個動態(tài)變化的值。為了優(yōu)化一致性算法的收斂性能，引入了一個虛擬基準的概念。在引入虛擬基準后，智能體編隊中的節(jié)點不僅要與鄰居節(jié)點實現(xiàn)一致，也要與虛擬基準實現(xiàn)一致。則式(3)應改寫為

i=1,2,…,n;j∈Ni

(4)

式中：〈xR〉i為節(jié)點i的虛擬基準：當系統(tǒng)不存在指定基準，虛擬基準由鄰居節(jié)點的平均作用獲得，參見式(21)；若系統(tǒng)存在外部指定基準時，虛擬基準取值為外部基準值，見本文第3節(jié)。

由以上分析可知，式(3)和式(4)給出的信息一致性算法，只需要相鄰節(jié)點之間的相互作用，即任意一個節(jié)點的信息狀態(tài)僅僅依賴于其鄰居節(jié)點的信息狀態(tài)。因此，信息一致性的過程具有空間馬爾可夫性。本文將基于空間馬爾可夫隨機場建立信息一致性模型。通過引入鄰居系統(tǒng)和團勢能，得到基于伊辛模型的能量函數(shù)，以能量最小化尋優(yōu)的方法實現(xiàn)分布式信息一致性。

在基于空間的馬爾可夫隨機場建立的信息一致性模型中，本文用團來模擬鄰居節(jié)點間關系。與子圖的定義一致，可以定義單節(jié)點團C1、雙鄰居節(jié)點團C2、三鄰居節(jié)點團C3等。本文所使用的單節(jié)點團C1、雙鄰居節(jié)點團C2為

C1=i|i∈V

(5)

C2=i,j|i∈V,j∈Ni

(6)

為每個節(jié)點設置一個初始信息狀態(tài)，即為網(wǎng)絡中的每個節(jié)點分配一個初始的協(xié)同信息，這一事件可視為一個標簽化的過程，分配標簽在隨機領域術語中被稱為配置。所謂的標簽化，就是從標簽集合中分配一個標簽給每個節(jié)點。根據(jù)集合的定義，將系統(tǒng)產(chǎn)生的所有協(xié)同信息稱為一個標簽集合，它可以是連續(xù)或者離散的。在協(xié)同信息一致性系統(tǒng)中，本文采用連續(xù)的標簽集合。故在所建立的空間馬爾可夫隨機場信息一致性模型中，系統(tǒng)中所有節(jié)點應具有相同的標簽集合，與之對應的配置空間為

X=X1,X2,…,Xn∈Rn

(7)

式中：n為網(wǎng)絡中節(jié)點的個數(shù)。標簽化Xi=xi表示為每個節(jié)點i配置一個初始協(xié)同變量值xi這一事件，對應的標簽集合可以表示為{X1=x1,X2=x2,…,Xn=xn}，記為X=x，其中x是X的一個配置。在概率中，x是一個聯(lián)合事件，其概率記為Px；同理，在配置過程中，將節(jié)點i獲得初始協(xié)同變量值xi這一事件的概率記為P(xi)。由聯(lián)合概率的基本性質可知以下兩個條件顯然成立：

P(x)>0, ?x∈X

(8)

Pxi|xV-i=Pxi|xNi

(9)

式(8)和式(9)分別體現(xiàn)了概率事件的正定性和概率事件的馬爾可夫性。對于鄰域系統(tǒng)N而言，X是在G上的馬爾可夫隨機場。

存在這種情況，當系統(tǒng)每個節(jié)點都獲得相同的標簽，即

xi=x,i∈V

(10)

認為整個系統(tǒng)達到了信息一致，實現(xiàn)了全網(wǎng)絡的協(xié)同信息一致性。其中事件xi=x的概率Pxi=x，可以通過調整網(wǎng)絡的配置來使其取得最大值。

在馬爾可夫隨機場中，尋找Pxi=x的最大概率定義為尋找馬爾可夫隨機場的最大后驗概率(Maximum A Posteriori，MAP)配置。文獻[23]指出，馬爾可夫隨機場等同于吉布斯隨機場，故協(xié)同信息配置也應該服從以下形式的吉布斯分布：

(11)

(12)

由式(12)可知，U(x)為所有可能的團C上的團勢能Vcx之和[24]。進一步寫為

(13)

只定義C1團和C2團，故式(13)簡化為

(14)

引入式(11)，易知能量函數(shù)Ux的最小化使Px的概率值最大化。

問題轉化為求最小化能量函數(shù)U(x)，引入平均場理論中的伊辛模型，模型中的總能量可以表示為[25]

(15)

式中：H為強度系數(shù)；J為耦合矩陣；xi對應于節(jié)點i的本地協(xié)同信息集合。耦合矩陣J的每個格點都代表一對鄰居節(jié)點之間的相互作用關系，若節(jié)點i和j之間可以進行協(xié)同信息交互，則矩陣中Jij不為0。式(15)能量函數(shù)U(x)最小化等價于P(x)的概率值最大。

以上分析表明，在式(11)的作用下，基于式(4)的一致性問題與平均場問題是等價的?？梢酝ㄟ^求平均場能量最小化來求解一致性的解，同時也給出了一個思路，可以通過平均場給出虛擬信息基準。

2.1 能量函數(shù)定義

作為一致性算法的目標函數(shù)，能量函數(shù)是可以被最小化的，它主要有以下兩個任務：

1) 定義協(xié)同信息變量達成一致的最佳求解方案。

2) 通過能量最小化尋找最佳的虛擬協(xié)同信息基準。

從式(14)中可知，團的勢能函數(shù)求和可得勢能函數(shù)。參考文獻[24]，本文將雙鄰居節(jié)點團C2的勢能函數(shù)定義為

V2xi,xj=gxi-xj

(16)

式中：gxi-xj為節(jié)點i和j之間的狀態(tài)偏差的單調遞減懲罰函數(shù)。在懲罰函數(shù)中最常用的是二次函數(shù)，因此式(16)可改寫為

gxi-xj=xi-xj2

(17)

在高對抗的實際工作環(huán)境中，節(jié)點的狀態(tài)是不斷變化的，隨時都有可能發(fā)生某一個節(jié)點故障重啟或加入一個新節(jié)點，此時故障重啟和新加入的節(jié)點將重新獲取初始協(xié)同信息變量，這與其他節(jié)點同一時刻的信息變量存在較大的狀態(tài)偏差，因此會產(chǎn)生一個較大的修復因子，使一致性集結點產(chǎn)生較大的波動，進而影響能量最小化的時間，降低算法效率。為此，引入一個截斷變量σ，用來表示節(jié)點與其鄰居節(jié)點之間的狀態(tài)偏差的方差。式(17)可以重寫為

g(xi-xj)=min{σ2,(xi-xj)2}

(18)

對式(18)求導可得

g′(xi-xj)=2×min{σ,(xi-xj)}

(19)

而單節(jié)點團C1的勢能函數(shù)僅僅依賴節(jié)點當前信息狀態(tài)與系統(tǒng)參考基準狀態(tài)的偏差，故其二次方程描述為

V1xi=xi-xR2

(20)

式中：xR為基準信息,取值取決于多智能體系統(tǒng)的工作模式。多智能體系統(tǒng)的工作模式基本可以分為兩類，一類是智能體系統(tǒng)不存在外部基準信息，由各智能體在一致性協(xié)議的作用下，協(xié)同變量收斂于某個值，該值由各智能體協(xié)同變量的初值決定。在這種情況下，xR的取值由式(21)給出平均場算法計算得到；另一種是存在基準信息，不僅要求智能體協(xié)作變量收斂，而且要收斂于給定的基準信息，例如存在領航節(jié)點的無人航行體編隊飛行。在這種情況下，xR的取值取為外部給定的基準信息。

根據(jù)平均場理論，其他所有節(jié)點對某一個給定節(jié)點的影響可由一個平均作用近似獲取[26]，進一步計算可得領域系統(tǒng)的基準信息狀態(tài)。在平均場中，節(jié)點i鄰域系統(tǒng)的虛擬基準狀態(tài)可以定義為

(21)

式中：P(xj)為配置過程中節(jié)點j獲得初始協(xié)同變量值xj的概率，將式(18)、式(20)代入式(14)可得完整的能量函數(shù)表達式為

(22)

由第2節(jié)分析有：當U(x)取得最小值Umin(x)時就得到了全局系統(tǒng)信息一致的最優(yōu)點。上述問題就轉化為求式(22)的最小值點問題。式(22)的含義為： 通過對系統(tǒng)中每個節(jié)點的團勢能求和，將能量函數(shù)U(x) 轉化為一個全局的變量并尋找最小化的能量函數(shù)Umin(x)，這是一個簡單的二次函數(shù)求最值問題。但在分布式多跳網(wǎng)絡中，獲取每個節(jié)點的團勢能并求和會產(chǎn)生很大的網(wǎng)絡負載，增加網(wǎng)絡中信息交互的時間，這可能會導致節(jié)點所獲取的一致信息過時。解決這一問題，應該尋找一種分布式并行運行算法，減少信息在網(wǎng)絡中的傳輸時間，降低網(wǎng)絡負載，更加快速準確地獲取能量函數(shù)最小化值。

2.2 能量函數(shù)的并行最小化

為了解決一致性過程中新入節(jié)點或重啟節(jié)點與鄰居節(jié)點之間協(xié)同變量偏差過大問題，在式(18)中引入了截斷因子σ，這使得能量函數(shù)不再是一個線性函數(shù)，為簡化分析，考慮公式：

(23)

式(23)可以看作是對兩個二次函數(shù)的求和。由二次函數(shù)的基本性質可知當U(x)取最小值時，x為函數(shù)的一個駐點，該點處的導數(shù)(梯度向量)值必為0，即

(24)

式(24)與式(22)具有較高的一致性。在求和的過程中依舊要獲取系統(tǒng)中每個節(jié)點的協(xié)同變量信息，會增加系統(tǒng)的計算量，增大網(wǎng)絡負載，增加網(wǎng)絡延遲。故對式(24)進行整理寫為

(25)

令

(26)

從而有

(27)

式(27)表明，全局能量函數(shù)最小化問題等價于借助式(27)求各個節(jié)點能量最小化問題。同時并行的對各個節(jié)點進行團勢能更新，以期取得最小的能量函數(shù)值，最終實現(xiàn)全局能量函數(shù)最小化。采用式(27)全分布式能量最小化算法，能較好地解決網(wǎng)絡節(jié)點多、跳數(shù)多產(chǎn)生的網(wǎng)絡負載過重問題。

為達到協(xié)同變量一致性，使全局能量函數(shù)最小化，式(25)取得了一個局部最小值點x。式(17)所定義的能量函數(shù)是一個二次函數(shù)，其基本性質決定了式(25)在定義域內是一個嚴格的凸函數(shù)。進一步由凸函數(shù)的性質有：嚴格的凸函數(shù)在全局中最多只有一個全局最小值點[27]。故式(25)取得的局部最小值點x即全局最小值點，在這點處可以取得馬爾可夫隨機場的最大后驗概率MAP。

在實際應用中，能量最小化函數(shù)的算法采用下面規(guī)則進行迭代求解：

(28)

式中：μ為一個較小的常數(shù),μ的取值參考具體實驗精度要求和數(shù)值積分步長要求。由于式(28)僅涉及簡單的算術運算和初等函數(shù)運算，因此本文的分布式信息一致性算法復雜度低，適用于CPU能力和功率都十分有限的無線自組織網(wǎng)絡節(jié)點。

2.3 一致性算法收斂性分析

定理1多智能體編隊在式(28)的作用下，將達到信息一致性。

證明：

式(28)可改寫為

(29)

式中：μ為一個較小的常數(shù)可視為微分項中的步長，步長越小，其佩亞諾余項越小，從而擾動變小，當μ趨近于無窮小時，差分算子可視為微分算子?，F(xiàn)實中計算機系統(tǒng)往往是非線性的離散系統(tǒng)，可以將式(28)的離散系統(tǒng)抽象成連續(xù)微分方程，從而達到用線性系統(tǒng)逼近非線性系統(tǒng)的目的。

平均場方法的更新方程可寫為

(30)

引入式(21)，式(30)可改寫為

(31)

引入鄰接矩陣，將式(31)改寫為

(32)

式中：aij為鄰接矩陣的元素。

合并同類項，可得

(33)

矩陣方式為

(34)

式中：

(35)

顯然，-L為對角占優(yōu)矩陣，零為其簡單特征根[14]，故系統(tǒng)收斂?；騆具有正實部特征根，則-L具有負實部特征根，所以系統(tǒng)收斂[14]。

定理2收斂速度一致性

下面對有向通信拓撲下本算法的收斂速度進行分析，由文獻[28]可知，分布式多智能體系統(tǒng)一致性算法的收斂速度由其通信拓撲圖的代數(shù)連通度決定，即矩陣L的第二小特征值，或矩陣L的譜半徑ρ(L)。本文一致性算法可寫為

(36)

系統(tǒng)狀態(tài)方程為

(37)

對式(37)進行拉普拉斯變換可以得到

sx(s)=-Lx(s)

(38)

x(s)的特征方程為

det(sIn+L)=0

(39)

由于有向通信拓撲圖Gn含有一個生成樹，且L為拉普拉斯矩陣，從而由文獻[29]可知L的特征值應為

0=λ1(G)<λ2(G)≤…≤λn(G)

(40)

式中：λn(G)為圖Gn的譜半徑，通常認為拉普拉斯矩陣：

(41)

為圖的Gn代數(shù)連通度，恒大于零。此時除了一個特征根為0外，其他特征根均有負實部，即均位于左半平面上，因而系統(tǒng)可以收斂到一個穩(wěn)定狀態(tài)。

再次，由文獻[27,30-31]可知

(42)

式中：Δ、δ為圖Gn的最大度和最小度；m、n分別為邊數(shù)和頂點數(shù)。等號成立當且僅當圖為正則偶圖。

λ2(G)≤v(G)≤e(G)

(43)

式中：v(G)為點連通度；e(G)為邊連通度。

進而在圖為固定直徑d的n階連通圖中有

(44)

綜上，當多智能體收斂到穩(wěn)定狀態(tài)時，由于隊形和節(jié)點間為了避免碰撞引入的間距已經(jīng)被設定好，其第二小特征值的上界的增長速率由于冪函數(shù)特性也趨于穩(wěn)定，特征根最后應分布在一個相對固定區(qū)間中，所以整個系統(tǒng)的收斂速度變化也集中在一個浮動不明顯區(qū)間內，因而即使算法應用規(guī)模擴大即節(jié)點個數(shù)增加，算法收斂速度依舊無明顯增大。

3 擴展到有基準狀態(tài)的一致性信息一致性模型

和現(xiàn)有的大部分一致性算法一樣，式(29)所給出的信息一致性算法適用于完全沒有中心節(jié)點，或沒有指定基準值的場合。如沒有指定集結位置的編隊協(xié)同、多導彈同時擊中目標的飽和攻擊中對于協(xié)同末制導中的時間一致性等。但很多實際應用還是存在一個基準(期望)信息狀態(tài)，這時，不僅要求編隊收斂于一個共同值，而且該共同值要收斂于一個指定的基準狀態(tài)。因此需要建立一種一致性算法，使得編隊中的每一個智能體的協(xié)同信息狀態(tài)一致于一個時變的或時不變的基準狀態(tài)[32]。一種合理的應用場景是，在智能體編隊中有一個智能體作為領航節(jié)點，通過特殊鏈路受控于指揮中心，獲得基準信息狀態(tài)。編隊中的其他智能體通過與領航節(jié)點實現(xiàn)信息一致達到與基準信息狀態(tài)的一致。即通常所說的領航-跟隨模型。不失一般性，設節(jié)點1為領航節(jié)點，xr為基準信息狀態(tài)，xr關于時間t是有界且分段連續(xù)的。在此條件下，一致性問題可以描述為

(45)

(46)

定理3在有基準信息狀態(tài)條件下，式(29)收斂到基準值的必要條件是有向圖Gn含有一簇生成樹。

證明：

假設有向圖Gn不含有一簇有向生成樹，則存在一個航行體將整個航行體編隊分成兩個互不交換信息的子編隊，或至少存在兩個不接受信息的子編隊。

情況1假設第1個子編隊有x個節(jié)點，第2個子編隊有y個節(jié)點，x+y=n-1。節(jié)點1到x在編隊1，節(jié)點x+2到y(tǒng)在編隊2，中間節(jié)點為x+1，矩陣L可改寫為

(47)

式中：Lx∈Rx×x，Ly∈Ry×y，lx=[lx+1,1,lx+1,2…,lx+1,x]，ly=lx+1,x+2,lx+1,x+3,…,lx+1,n。

由定理1中轉化得到

(48)

故Lx、Ly矩陣行和為0；因而至少有一個零特征值。且Rank(Lx)≤x-1，Rank(Ly)≤y-1。可得Rank(L)≤n-2，即矩陣L至少有兩個零特征值。

情況2矩陣L至少有兩行元素均為零，即矩陣L至少有兩個零特征值。

兩種情況均與拉普拉斯矩陣含有一簇有向生成樹后有且僅有一個零特征值矛盾。

4 仿真驗證

為了驗證本文所提出算法的有效性，將在MATLAB 2009b的環(huán)境下建立分別具有3×3通信拓撲9個節(jié)點的鄰接規(guī)模編隊、7×7通信拓撲49個節(jié)點的大規(guī)模編隊，形成標準2D網(wǎng)格結構，仿真結果中不同顏色曲線分別表示各節(jié)點的狀態(tài)。為簡單起見，假設每一節(jié)點僅與其水平或鄰居節(jié)點進行交互，即采用標準的4-鄰居系統(tǒng)。各節(jié)點與鄰居節(jié)點交換協(xié)同變量并更新自己的變量信息狀態(tài)。本節(jié)分別針對多智能體在無基準信息狀態(tài)下的信息一致性、存在靜態(tài)基準信息狀態(tài)的信息一致性、存在動態(tài)基準信息狀態(tài)的信息一致性等問題，對本文算法的性能進行仿真驗證，并與極大一致性算法進行對比分析。極大一致性算法可以表示為

ui(t)=αi[(1-μ)(xmax(t)-xi(t))+

(49)

(50)

4.1 無基準信息狀態(tài)下的分布式算法仿真分析

圖1(a)和圖1(b)分別展示了本文算法在3×3、7×7通信拓撲條件下，全局各節(jié)點之間協(xié)同信息的變化情況。在沒有外部基準信息，設定丟包率小于30%的情況下，所有節(jié)點的協(xié)同信息差值收斂于0值，且與理想實驗環(huán)境下無明顯差別，這表明鄰居節(jié)點之間關于協(xié)同信息的誤差已達到可接受范圍之內。隨著節(jié)點數(shù)目的增加，全網(wǎng)節(jié)點對協(xié)同變量達成共識的時間并未發(fā)生明顯變化，這體現(xiàn)了該算法良好的魯棒性。圖1(c)和圖1(d)分別展示了極大一致性算法在3×3、7×7通信拓撲條件下，全局各節(jié)點之間協(xié)同信息的變化情況。通過對比分析，本文算法在網(wǎng)絡規(guī)模較小情況下與極大一致性算法收斂情況相似，但是隨著網(wǎng)絡規(guī)模的增大，本文算法在收斂時間方面具有明顯優(yōu)勢。

4.2 外部靜態(tài)基準信息狀態(tài)下的分布式算法仿真分析

圖2(a)和圖2(b)分別展示了本文算法在不同編隊規(guī)模下，各節(jié)點在有外部靜態(tài)基準信息且設定丟包率小于30%時對協(xié)同變量達成共識：所有節(jié)點協(xié)同信息收斂于外部靜態(tài)基準，或稱為與外部基準信息之間的差值小于誤差期望值(10-6)，可認為全局節(jié)點就收斂信息達成共識，即實現(xiàn)全網(wǎng)的協(xié)同信息一致性。與圖1(a)和圖1(b)比較易知，在有外部基準信息情況下，協(xié)同變量最終取值為外部基準，各節(jié)點的協(xié)同信息狀態(tài)與外部基準信息誤差小于所允許的最大誤差。在收斂時間方面，隨著節(jié)點數(shù)目的增加，全局節(jié)點達成信息共識的時間無明顯增加。圖2(c)和圖2(d)分別展示了極大一致性算法在3×3、7×7通信拓撲條件下，全局各節(jié)點在有外部靜態(tài)基準信息時協(xié)同信息的變化情況。與圖2(a)和圖2(b)比較分析，隨著節(jié)點規(guī)模擴大，極大一致性算法的效率明顯下降。

4.3 外部動態(tài)基準信息狀態(tài)下的分布式算法仿真分析

圖3的外部動態(tài)基準信息取值為幅值為1的正弦函數(shù)，丟包率設定為小于30%。代表本文算法的圖3(a)和圖3(b)與靜態(tài)基準信息相比，節(jié)點初始信息狀態(tài)與基準信息有較大的差值，當各節(jié)點與鄰居節(jié)點相互交換自身協(xié)同信息并更新自己的信息狀態(tài)以后，對局部協(xié)同變量的共識趨于虛擬基準，而虛擬基準趨于外部基準，與外部基準差值不斷減少，最終所有節(jié)點跟隨外部基準運動，實現(xiàn)全局協(xié)同信息一致性。圖3(c)和圖3(d)分別展示了極大一致性算法在3×3、7×7的網(wǎng)格拓撲條件下，存在外部動態(tài)基準信息時的仿真結果，可以看出，極大一致性算法收斂性能并不理想，偏差很大。

圖3 有動態(tài)外部基準信息
Fig.3 With dynamic external reference information

4.4 QualNet平臺下的信息一致性仿真

多智能體生存環(huán)境的對抗性決定了多智能體必須具有高度的協(xié)同能力。在實際使用環(huán)境中，時空配準是多無人機航行平臺執(zhí)行協(xié)同任務的前提，對協(xié)同信息達成共識是多無人機航行平臺編隊與協(xié)同作戰(zhàn)最基本、最重要的一致性信息；無人航行體編隊協(xié)同作戰(zhàn)工作在一定的對抗環(huán)境中，存在節(jié)點損失和新節(jié)點加入的情況，甚至會有編隊拆分與合并的情況，造成高度動態(tài)通信拓撲結構，且時延不確定，丟包率高，這就要求算法應該具有較強的魯棒性。

本文用QualNet模擬多智能的實際生存環(huán)境，采用本文所提出的分布式協(xié)同一致性算法，在存在網(wǎng)絡丟包的情況下，各節(jié)點通過本文提出的算法能夠達到時鐘同步。為更好的體現(xiàn)算法性能，在同等環(huán)境下對ATS (Average Time Synchronization)、GTSP (Gradient Time Synchronization Protocol)和本文算法MFTS (Mean Field based Time Synchronization)進行比較，結果如圖4和圖5所示。

首先給出判斷達到信息一致性的標準：當全局系統(tǒng)中所有有效節(jié)點與鄰居節(jié)點對協(xié)同信息的共識值之間的差值小于10-6時，就認為達到了全局信息的一致性。在圖4中，分別對鄰接規(guī)模(9個節(jié)點)編隊、中等規(guī)模(25個節(jié)點)編隊、大規(guī)模(64個節(jié)點)編隊、超大規(guī)模(100個節(jié)點)編隊進行對比。由圖可知，GTSP算法僅僅在通信拓撲鄰接規(guī)模能在指定的時間內實現(xiàn)全局信息信息一致性，隨著節(jié)點數(shù)目的增多，算法的性能急劇下降；ATS算法雖然能夠較好地完成多智能體信息一致性，但隨著節(jié)點數(shù)目的增多，所需要一致性的時間不斷地增大。圖5為對不同節(jié)點數(shù)目，當采取3種不同算法時所需時間的直觀表示。本文提出的MFTS能更好地適應動態(tài)拓撲，具有較高的魯棒性。

圖4 不同算法的性能比較
Fig.4 Comparison of performance of different algorithm

圖5 不同節(jié)點數(shù)目時間比較
Fig.5 Comparison of time of different number of nodes

5 結 論

本文提出了一種多智能體協(xié)同信息一致性算法。

1) 該算法對網(wǎng)絡規(guī)模不敏感，在不同的網(wǎng)絡規(guī)模下，收斂時間基本保持不變。

2) 該算法對不完全通信網(wǎng)絡有一定的適應性，仿真驗證表明在網(wǎng)絡丟包達到30%時，依然可以收斂。

3) 該算法實現(xiàn)簡單，對于有基準、無基準、靜態(tài)基準、動態(tài)基準均可采用同樣的算法結構，具有很好的適應性。

[1] CAO Y, YU W, REN W, et al. An overview of recent progress in the study of distributed multi-agent coordination[J]. IEEE Transactions on Industrial Informatics, 2012, 9(1): 427-438.

[2] 王寅秋. 非線性多智能體系統(tǒng)一致性分布式控制[D]. 北京: 北京理工大學, 2015: 12-21.

WANG Y Q. Distributed consensus for non-linear multi-agent systems[D]. Beijing: Beijing Institute of Technology, 2015: 12-21 (in Chinese).

[3] 張慶杰. 基于一致性理論的多UAV分布式協(xié)同控制與狀態(tài)估計方法[D]. 長沙: 國防科學技術大學,2011: 10-31.

ZHANG Q J. Distributed cooperative control and statement estimation for networked multiple UAVs based on consensus theory[D]. Changsha: National University of Defense Technology, 2011: 10-31 (in Chinese).

[4] TSITSIKLIS J N. Problems in decentralized decision making and computation[J]. Problems in Decentralized Decision Making & Computation, 1984, 43(9): 134-139.

[5] TSITSIKLIS J, BERTSEKAS D, ATHANS M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms[J]. IEEE Transactions on Automatic Control, 1984, 31(9): 803-812.

[6] BENEDIKTSSON J A, SWAIN P H. Consensus theoretic classification methods[J]. IEEE Transactions on Systems Man & Cybernetics, 1992, 22(4): 688-704.

[7] VICSEK T, CZIRK A, BEN-JACOB E, et al. Novel type of phase transition in a system of self-driven particles[J]. Physical Review Letters, 1995, 75(6): 1226.

[8] JADBABAIE A, LIN J, MORSE A S. Coordination of groups of mobile autonomous agents using nearest neighbor rules[J]. IEEE Transactions on Automatic Control, 2003, 48(6): 988-1001.

[9] HUSSEIN I I, STIPANOVIC D M. Effective coverage control for mobile sensor networks with guaranteed collision avoidance[J]. IEEE Transactions on Control Systems Technology, 2007, 15(4): 642-657.

[10] LEONARD N E, PALEY D A, LEKIEN F, et al. Collective motion, sensor networks, and ocean sampling[J]. Proceedings of the IEEE, 2007, 95(1): 48-74.

[11] MURRAY R M. Recent research in cooperative control of multivehicle systems[J]. Journal of Dynamic Systems, Measurement, and Control, 2007, 129(5): 571-583.

[12] OLSHEVSKY A, TSITSIKLIS J N. Convergence speed in distributed consensus and averaging[J]. SIAM Journal on Control and Optimization, 2009, 48(1): 33-55.

[13] HOLSAPPLE R W, KINGSTON D B. Cooperative control of autonomous systems[J]. International Journal of Robust and Nonlinear Control, 2011, 21(12): 1355-1357.

[14] REN W, BEARD R W. Consensus seeking in multiagent systems under dynamically changing interaction topologies[J]. IEEE Transactions on Automatic Control, 2005, 50(5): 655-661.

[15] LI S, WANG J, LUO X, et al. A new framework of consensus protocol design for complex multi-agent systems[J]. Systems & Control Letters, 2011, 60(1): 19-26.

[16] LI T, ZHANG J F. Consensus conditions of multi-agent systems with time-varying topologies and stochastic communication noises[J]. IEEE Transactions on Automatic Control, 2010, 55(9): 2043-2057.

[17] BRAGINSKY B, BARUCH A, GUTERMAN H. Tracking of autonomous underwater vehicles using an autonomous surface vehicle with ranger interrogator system[C]∥OCEANS 2016 MTS/IEEE Monterey. Piscataway, NJ: IEEE Press, 2016: 1-5.

[18] THUSEETHAN S, VASANTHAPRIYAN S. Multi-agent based ocean-transport and traffic controlling system: A simulation[C]∥2015 5th National Symposium on Information Technology: Towards New Smart World (NSITNSW). Piscataway, NJ :IEEE Press, 2015: 1-5.

[19] VAZQUEZ-OLGUIN M, SHMALIY Y S, IBARRA-MANZANO O. Design of blind distributed UFIR filter based on average consensus for WSNs[C]∥ 2016 13th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE). Piscataway, NJ :IEEE Press, 2016: 1-6.

[20] BOLOGNANI S, CARLI R, LOVISARI E, et al. A randomized linear algorithm for clock synchronization in multi-agent systems[C]∥2012 IEEE 51st IEEE Conference on Decision and Control (CDC). Piscataway, NJ :IEEE Press, 2012: 20-25.

[21] 吳森堂. 導彈自主編隊協(xié)同制導控制技術[M]. 北京: 國防工業(yè)出版社, 2015: 13-150.

WU S T.Cooperative guidance & control of missiles autonomous formation[M]. Beijing: National Defence Industry Press, 2015: 13-150(in Chinese).

[22] 曾斌, 姚路, 魏軍. 基于平均場模型的傳感器網(wǎng)絡信息共享算法研究[J]. 傳感技術學報, 2009 (10): 1486-1491.

ZENG B, YAO L, WEI J. A mean field model based information sharing algorithm for wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2009 (10): 1486-1491 (in Chinese).

[23] LI S Z. Markov random field modeling in image analysis[M]. Berlin: Springer, 2009: 357.

[24] KOPETZ H, OCHSENREITER W. Clock synchronization in distributed real-time systems[J]. IEEE Transactions on Computers, 1987, 100(8): 933-940.

[26] GAST M. 802.11 無線網(wǎng)絡權威指南[M]. 南京: 東南大學出版社, 2007: 52-53.

GAST M. 802.11 wireless networks: The definitive guide[M]. Nanjing: Southeast University Press, 2007: 52-53 (in Chinese).

[27] 丁尚文. 圖的最大和次小拉普拉斯特征值[D].成都: 電子科技大學, 2008.

DING S W. The largest and the second smallest eigenvalue of graphs[D]. Chengdu: University of Electronic Science and Technology of China, 2008(in Chinese).

[28] OLFATI-SABER R, MURRAY R M. Consensus problems in networks of agents with switching topology and time-delays[J]. IEEE Transactions on Automatic Control, 2004, 49(9): 1520-1533.

[29] AYSAL T C, ORESHKIN B N, COATES M J. Accelerated distributed average consensus via localized node state prediction[J]. IEEE Transactions on Signal Processing, 2009, 57(4): 1563-1576.

[30] 劉瑞芳. 圖的最小特征根和拉普拉斯譜半徑[D]. 上海: 華東師范大學,2010.

LIU R F. The least eigenvalue and the laplacian spectral radius of graphs[D]. Shanghai: East China Normal University, 2010 (in Chinese).

[31] 汪天飛, 李彬. 圖的最大拉普拉斯特征值的上界[J]. 四川師范大學學報(自然科學版), 2007, 30(2): 191-193.

WANG T F, LI B. New upper bounds for the laplacian spectral radius of graphs[J]. Journal of Sichuan Normal University (Natural Science), 2007, 30(2): 191-193(in Chinese).

[32] WEI R, RANDAL W D. 多智能體協(xié)同控制中的分布式一致性——理論與應用[M].北京：電子工業(yè)出版社，2014： 57-58.

WEI R, RANDAL W D. Distributed consensus in multi-vehicle cooperative control—Theory and applications[M]. Beijing: Publishing House of Electronics Industry, 2014:57-58(in Chinese).

Acooperativeinformationconsensusalgorithmformulti-agentsystem

CHENWu*,ZHANGXin,JINXin,LIZehong,HONGLiang

SchoolofAutomation,NorthwesternPolytechnicalUniversity,Xi’an710072,China

Multi-agentcooperativeoperationplaysanimportantroleinthecyberspacewar,andthemainapplicationliesinthefieldofmultipleUnmannedAerialVehicles(UAVs)/multi-missilecollaborativecluster.Sharingcollaborativeinformationandconsistencyarethefoundationandprerequisiteforthemulti-agenttocompletecollaborativetaskssuchascoordination,formation,flockingandsynchronization.Aconsensusinformationmodelisestablishedbasedontheneighborsystemandtheclusterpotential,andthebiasofthecooperativeinformationismappedtotheclusterpotentialenergy.ByusingtheminimizationofparallelenergytosolvethemaximumaposterioriprobabilityoftheMarkovrandomfield,cooperativeinformationreachesaconsensuswithdistributedandnoncentercondition.Differentfromthetraditionalconsensusalgorithm,thealgorithmproposedintroducestheconceptofvirtualreference.Avirtualreferenceisestablishedbycooperativeinformationinteractionamongtheneighborsbyusingthemeanfieldtheorywithnoexternalreferenceinput.Whenthepilotnodeorthevirtualpilotnodeexists,thestateanditsderivativeofthepilotnodecooperativeinformationareusedasthevirtualreference.Simulationresultsshowthattheproposedalgorithmhastheadvantagesofinsensitivitytonetworkscale,fastconvergenceandhighrobustness.Thealgorithmcanbealsousedinthepresence/absenceofreferenceinput,meaningthatthealgorithmhasgreatadaptability.

multi-agent;consensus;Markovrandomfield;meanfield;virtualreference

2017-03-07；

2017-04-13；

2017-04-26；Publishedonline2017-05-121839

URL：http://hkxb.buaa.edu.cn/CN/html/20171220.html

MajorResearchProjectofShaanxiProvince(2017GY-069)

.E-mailchenwu@nwpu.edu.cn

http://hkxb.buaa.edu.cnhkxb@buaa.edu.cn

10.7527/S1000-6893.2017.321222

2017-03-07；退修日期2017-04-13；錄用日期2017-04-26；網(wǎng)絡出版時間2017-05-121839

http://hkxb.buaa.edu.cn/CN/html/20171220.html

陜西省重點研發(fā)計劃(2017GY-069)

.E-mailchenwu@nwpu.edu.cn

陳旿，張鑫，金鑫，等．一種多智能體協(xié)同信息一致性算法J．航空學報,2017,38(12):321222.CHENW,ZHANGX,JINX,etal.Acooperativeinformationconsensusalgorithmformulti-agentsystemJ.ActaAeronauticaetAstronauticaSinica,2017,38(12):321222.

TP273

A

1000-6893(2017)12-321222-13

蘇磊)