一種多智能體協同信息一致性算法

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

西北工業大學 自動化學院，西安 710072

一種多智能體協同信息一致性算法

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

西北工業大學 自動化學院，西安 710072

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

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

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

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

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

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

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

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

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

1 問題描述

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

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

(1)

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

2 信息一致性模型

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

N=Ni|?i∈V

(2)

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

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

2) 相鄰關系是相互的。

i∈Nj??j∈Ni

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

(3)

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

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

(4)

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

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

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

C1=i|i∈V

(5)

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

(6)

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

X=X1,X2,…,Xn∈Rn

(7)

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

P(x)>0, ?x∈X

(8)

Pxi|xV-i=Pxi|xNi

(9)

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

存在這種情況，當系統每個節點都獲得相同的標簽，即

xi=x,i∈V

(10)

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

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

(11)

(12)

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

(13)

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

(14)

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

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

(15)

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

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

2.1 能量函數定義

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

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

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

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

V2xi,xj=gxi-xj

(16)

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

gxi-xj=xi-xj2

(17)

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

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

(18)

對式(18)求導可得

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

(19)

而單節點團C1的勢能函數僅僅依賴節點當前信息狀態與系統參考基準狀態的偏差，故其二次方程描述為

V1xi=xi-xR2

(20)

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

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

(21)

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

(22)

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

2.2 能量函數的并行最小化

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

(23)

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

(24)

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

(25)

令

(26)

從而有

(27)

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

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

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

(28)

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

2.3 一致性算法收斂性分析

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

證明：

式(28)可改寫為

(29)

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

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

(30)

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

(31)

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

(32)

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

合并同類項，可得

(33)

矩陣方式為

(34)

式中：

(35)

顯然，-L為對角占優矩陣，零為其簡單特征根[14]，故系統收斂。或L具有正實部特征根，則-L具有負實部特征根，所以系統收斂[14]。

定理2收斂速度一致性

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

(36)

系統狀態方程為

(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代數連通度，恒大于零。此時除了一個特征根為0外，其他特征根均有負實部，即均位于左半平面上，因而系統可以收斂到一個穩定狀態。

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

(42)

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

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

(43)

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

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

(44)

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

3 擴展到有基準狀態的一致性信息一致性模型

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

(45)

(46)

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

證明：

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

情況1假設第1個子編隊有x個節點，第2個子編隊有y個節點，x+y=n-1。節點1到x在編隊1，節點x+2到y在編隊2，中間節點為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的環境下建立分別具有3×3通信拓撲9個節點的鄰接規模編隊、7×7通信拓撲49個節點的大規模編隊，形成標準2D網格結構，仿真結果中不同顏色曲線分別表示各節點的狀態。為簡單起見，假設每一節點僅與其水平或鄰居節點進行交互，即采用標準的4-鄰居系統。各節點與鄰居節點交換協同變量并更新自己的變量信息狀態。本節分別針對多智能體在無基準信息狀態下的信息一致性、存在靜態基準信息狀態的信息一致性、存在動態基準信息狀態的信息一致性等問題，對本文算法的性能進行仿真驗證，并與極大一致性算法進行對比分析。極大一致性算法可以表示為

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

(49)

(50)

4.1 無基準信息狀態下的分布式算法仿真分析

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

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

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

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

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

圖3 有動態外部基準信息
Fig.3 With dynamic external reference information

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

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

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

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

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

圖5 不同節點數目時間比較
Fig.5 Comparison of time of different number of nodes

5 結 論

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

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

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

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

[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] 王寅秋. 非線性多智能體系統一致性分布式控制[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分布式協同控制與狀態估計方法[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] 吳森堂. 導彈自主編隊協同制導控制技術[M]. 北京: 國防工業出版社, 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] 曾斌, 姚路, 魏軍. 基于平均場模型的傳感器網絡信息共享算法研究[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 無線網絡權威指南[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. 多智能體協同控制中的分布式一致性——理論與應用[M].北京：電子工業出版社，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；網絡出版時間2017-05-121839

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

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

.E-mailchenwu@nwpu.edu.cn

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

TP273

A

1000-6893(2017)12-321222-13

蘇磊)