組合連通拓撲下基于事件觸發的多智能體快速一致性算法

陳世明 管俊杰 高彥麗 裴惠琴 邱昀

近年來,群系統的分布式協同控制因其極強的實際應用背景已成為控制工程、生物學、物理學等學科廣泛關注的一個重要問題.例如多航體集結[1?2]、編隊控制[3?4]、蜂擁[5?6]、姿態校整[7?8]等. 這些協同控制任務都可以統一到多智能體系統的信息一致性這一理論框架內.一致性理論的基本思想是每一個智能體基于自己和其鄰居的信息狀態更新自身信息,從而使得所有個體的最終信息收斂到一個共同的值,即達到一致.

一致性問題的研究可追溯到1995年Vicsek等[9]基于數學方程的描述方式,用網絡建立個體之間的信息交互,提出了一個簡單的離散多智能體系統模型(Vicsek模型).2003年Jadbabaie等[10]針對Vicsek模型進行了更深入的研究,利用圖論和矩陣論給出Vicsek模型的理論解釋,從本質上揭示了多智能體系統的群集現象.Olfati-Saber等[11]在此基礎上建立多智能體系統的理論框架并提出了經典的一致性協議.之后,Ren等[12]研究了一階連續和離散多智能體系統的一致性問題,提出在通信拓撲具有生成樹的情況下,所有節點的狀態能達成一致.

為改善一致性收斂速度,文獻[13]闡述了預測控制在多智能體系統中的應用,提出分布式模型預測控制策略,有效解決了存在有界控制輸入的多智能體系統一致性問題.文獻[14]研究了多智能體系統一致性的收斂速度問題,提出一種具有狀態預測器的一致性控制協議,在該控制協議下多智能體系統能以更快的速度達到一致.文獻[15]研究了二階多智能體系統一致性的收斂速度問題,提出一種快速分布式平均一致性算法,在每次控制輸入都加入基于鄰居狀態信息的線性預測量,加快了多智能體系統狀態值收斂到平均值的速度.

在實際應用中,智能體自身的能量和通信信道的帶寬都是有限的,一般而言,控制任務中的測量、通信和控制協議更新都是周期性執行的,即周期采樣控制方法[16?17].為了保證所有執行點的性能,采樣時間常數通常取一個保守值,這通常會造成通信和計算資源的浪費.隨著研究的深入及解決實際應用中控制器周期性執行任務導致的計算資源和通信資源浪費問題,基于事件觸發的多智能體控制策略研究得以開展和應用.在事件觸發控制策略下,控制任務只按需執行,從而達到節約系統的資源包括智能體的計算能力、通信能力、能源儲備等目的.目前,基于事件觸發控制的多智能體系統一致性已取得不少有意義的研究成果.在固定拓撲下,文獻[18]提出了一階系統的事件觸發控制協議,并針對其設計了一種與智能體系統狀態有關的事件觸發條件,證明不存在Zeno行為,結果表明事件觸發控制在具有期待性能的同時減少了采樣次數.文獻[19]提出了一個與時間有關的觸發函數.文獻[20]研究了二階多智能體系統的事件觸發控制.

在時變拓撲下,文獻[21]研究了切換拓撲下的事件觸發控制一致性問題,假設每個切換區間里的多智能體通信拓撲是強連通的,設計了一個事件觸發控制策略并解決了切換拓撲下的一致性問題.文獻[22]研究了領導跟隨系統在切換拓撲結構下的事件觸發一致性問題,基于鄰居個體的狀態估計值設計了一個反饋控制器,在該反饋控制器和事件條件共同作用下,系統能在有效節約通信資源的同時很好地實現切換拓撲下的領導跟隨一致性.文獻[23]研究了切換拓撲下線性異質多智能體系統的協同輸出調節問題,設計了一個基于事件觸發的觀測器,并在此基礎上提出基于輸出反饋的輸出調節控制策略,使得異質多智能體系統能在抑制干擾的同時實現對外部系統信號的漸近跟蹤一致.

以上時變拓撲研究需要保證時變拓撲是連通的或是強連通的.但實際中,由于系統通信帶寬有限,環境干擾等因素,時變拓撲并不能保證一直連通.文獻[24]研究了組合連通拓撲結構下的一致性問題,設計了一個靜態事件觸發函數使得分歧向量漸近趨于狀態平均值附近的有界區域.文獻[25]提出一個與觸發時刻狀態相關的觸發函數使得組合連通拓撲下的多智能體系統達成一致性.

考慮當前組合連通拓撲下多智能體系統基于事件觸發一致性控制研究成果,大都集中于控制協議設計或觸發條件的選取,沒有兼顧系統的收斂速度,而系統的收斂速度是一致性問題研究的一項重要性能指標.本文圍繞組合連通拓撲下多智能體系統基于事件觸發的一致性問題展開研究,提出一種新的具有狀態預測器的事件觸發一致性控制協議,并為智能個體給出了基于系統狀態信息的事件觸發條件.在每個事件觸發時刻,每個智能體都對其鄰居智能體的未來狀態作出預測,再通過通信將預測的狀態和觸發時刻的狀態傳遞給它的鄰居個體,經所提一致性協議計算使系統快速達成一致性.基于Lyapunov穩定性理論和代數圖論證明了所提事件觸發控制策略能有效實現組合連通拓撲下的平均一致性,并且不存在Zeno行為.最后通過仿真實驗驗證了所提控制策略在節約通信資源和收斂速度方面的優越性.

1 問題描述

1.1 代數圖論

代數圖論是多智能體系統建模和分析過程中非常重要的數學工具,智能體之間的通信關系可用圖G=(V,E) 來表示. 其中V={V1,V2,···,VN}表示系統中智能個體節點的集合,E={eij=(Vi,Vj):Vi,Vj∈V}表示智能個體之間相互通信的邊集.用一個非空序列J=ViEikVk···Vj表示圖G中Vi到Vj的一條路徑,如果在圖G中任意頂點對Vi和Vj之間存在一條途徑[Vi,Vj],則稱Vi和Vj是連通的.如果圖G中任意頂點對之間存在一條路徑,則稱圖G為連通圖.用鄰接矩陣A=[aij]∈RN×N表示網絡中節點之間的連接關系,若節點i能夠收到節點j的信息,則aij=1,否則aij=0.如果aij=aji則稱圖G為無向圖.在多智能體網絡中用Ni={Vj∈V:(Vi,Vj)∈E}表示節點i的鄰居節點集合.在無向圖中圖G的度矩陣D=diag{di}表示節點i的度所構成的對角矩陣,有向圖中D=diag{di}表示節點i的入度所構成的對角矩陣.圖G的Laplacian矩陣L表示為L=D?A.對無向圖而言Laplacian矩陣L是一個半正定的對稱矩陣,有一個零特征值,其對應的特征向量為1n=(1,1,···,1)T,其他所有非零特征值都是正實數.Laplacian矩陣L的特征值表示為λ1,λ2,···,λn,并且 0=λ1≤λ2≤···≤λn,第 2 個特征值λ2稱為圖G的代數連通度.

1.2 組合連通拓撲

實際應用中,往往由于系統通信帶寬有限、外界環境存在干擾等因素導致通信拓撲時變且不連通,對組合連通定義如下.

定義1.設圖G1,G2,···,Gm具有相同的頂點集V,記它們的并集為G1?m,它的節點集也為V,邊集是所有圖G1,G2,···,Gm的邊的并集.如果并圖G1?m是連通的則稱圖G1,G2,···,Gm是組合連通的.

當多智能體系統通信拓撲隨時間變化時,用函數σ(t):[0,∞)→{1,2,···,m}表示切換信號來決定通信拓撲.Gσ(t)表示t時刻智能體的通信拓撲圖,Lσ(t)為對應的Laplacian矩陣,Niσ(t)為智能體i的鄰居節點集.

考慮一組非零、不重疊、無限嚴格遞增的連續時間區間[tk,tk+1),k=0,1,2,···且tk+1?tk=T常數T>0.在時間區間[tk,tk+1)中存在有限個非重疊時間子區間,其中且滿足.

引理1[26].對于一個Laplacian矩陣為L的無向圖G且有非零向量x滿足1Tx=0則有.

1.3 系統模型

考慮有N個智能體的一階多智能體系統,智能體的動力學方程表示為

其中,xi(t)∈Rn是智能體i的狀態變量,ui(t)∈Rn表示控制輸入.

常用一致性控制協議如下:

系統的閉環動力學方程可表示為

其中,x(t)=[x1(t),x2(t),···,xN(t)]T為智能體的狀態向量,L為通信拓撲圖的拉普拉斯矩陣,相應的u(t)=[u1(t),u2(t),···,uN(t)]T為智能體控制輸入向量.

引理2[11].對于類似于式(1)的多智能體系統,收斂速度與Laplacian矩陣的最小非零特征值λ2相關,一般λ2越大,多智能體收斂到平衡狀態的速度越快.

2 組合連通拓撲下基于事件觸發的多智能體快速一致性算法

假設1.由智能體組成的通信拓撲圖的集合在時間區間[tk,tk+1),k=0,1,2,···是組合連通的.

通常事件條件可用一個數學不等式來表示.因此,當不滿足不等式時事件觸發即執行通信任務.用表示第i個智能體的第k次觸發瞬間,表示第k次觸發間隔.用rk表示多智能體系統的事件觸發時刻,易知時間序列{rk}包括智能體i的所有事件觸發時刻.

為了解決切換拓撲下基于事件觸發控制協議的收斂速度問題,本文提出在每個事件觸發時刻,每個智能體都能對其鄰居智能體的未來狀態作出預測,并用這個預測的狀態構造控制協議,從而使得多智能體系統可以更快地收斂到平衡狀態.

將誤差向量e(t)=[e1(t),e2(t),···,eN(t)]T和狀態向量x(t)=[x1(t),x2(t),···,xN(t)]T寫成矩陣形式:

注1.式(5)中x(rk)不是x(t)在t=rk時的值,而是向量. 其中為智能體i最近的觸發時刻.

由于在拓撲圖中孤立的點沒有控制輸入,本文只關注有鄰居節點的頂點.根據拓撲圖中連通部分對頂點進行分類,對任意一個圖Gp,定義為圖中包含至少兩個節點的部分,S0=為圖中只有一個節點的部分,即孤立頂點,其中1≤q≤Q≤N.令為的頂點集,.經過重新排列所有智能體的順序,圖Gp的Laplacian矩陣Lp可以寫成Lp,其中是連通部分的Laplacian矩陣.易知當l=1,···,p時,有簡單零特征值;l=q+1,···,Q時,=0.

注2.每個在的節點都沒有控制輸入,因此只要完善屬于Sc中的節點的事件觸發控制策略即可.為便于分析,定義屬于的節點的狀態向量,對應.令,可得的分歧向量另外一個分歧向量,易知是一個不變量,并且.定義el(t),有.

注3.類似于x(rk)的定義,,,其中為智能體i最近的觸發時刻,具有相同性質.

對每個智能體設計事件觸發條件,給出組合連通拓撲結構下的事件觸發條件如下:

定理1.考慮多智能體系統(1)在假設1下,r0=0對每個分支,事件觸發條件為

證明.考慮閉環系統(6),選擇Lyapunov函數V(t)=(1/2)δT(t)δ(t). 易知V(t) 為連續函數,除在切換拓撲瞬間和事件觸發瞬間rk外連續可微,定義V(t)在和rk瞬間的導數為正.

若多智能體系統在t時刻的通信拓撲為Gp,重新排列所有智能體的順序,可得新的Laplacian矩陣,這里是連通部分的Laplacian矩陣.因此系統(6)的Lyapunov函數V(t)關于時間t的導數為

對任意y,z∈Rn考慮不等式.

易知

由引理1,有

回顧之前定義的ti,有無窮序列V(ti),i=0,1,···.根據柯西收斂準則可知,對于任意的ε>0,總存在正整數Kε,使得當k≥Kε時,有.即當k≥Kε時,.

因為切換拓撲后的q不同,用qj表示在時間區間內q的值.

可推得

下面分析系統是否存在觸發間隔的下界,即是否不存在Zeno行為.事件觸發控制策略中,在每個觸發時刻,系統將會依據各狀態的實際值更新控制輸入,并且在下一觸發時刻前保持該控制輸入不變.一旦到達下一觸發時刻,系統用于控制輸入的狀態值將被更新,這時.根據以上穩定性方面作出的分析,只要滿足式(7),系統都將是穩定的,可以不用更新控制輸入.從而在不更新控制輸入的情況下,|eli(t)|將不斷增大,直到不滿足該不等式.如此,消除了Zeno行為.(t)始終負定,系統的穩定性將得到保證,如果系統在該控制協議下存在Zeno行為,那么系統將不可能滿足式(7)且達到漸近穩定.在接下來的定理中將證明所提控制策略中不存在Zeno行為,也就是說時間rk和rk+1之間的間隔應嚴格大于零.

定理2.對于多智能體系統(1),在假設1的前提下,通過控制協議(4)和事件觸發條件(7)可以使系統達成一致并且不存在Zeno行為.

證明.使用反證法,如注1所述,只考慮屬于集合Sc的頂點.假設存在Zeno行為,即在有限的時間內會觸發無數次的事件.分兩種情況.

情況1.智能體li在第k次觸發間隔內通信,其中c為與狀態預測量相關的常數,則拓撲圖固定的,并且它的鄰居個體也沒有觸發事件.則以及觸發條件式(7)的右側都是常數.定義eli(t)在時刻的導數是右導數.由于,且.由式(7)可知,第k+1次觸發時有

情況2.與情況1相反,在時刻發生切換拓撲或智能體i的鄰居個體有事件觸發,從而使得.由于按情況1有,所以, 其中.

兩種情況下事件觸發間隔都存在正下界,然而觸發無數次具有觸發間隔下界的事件只會發生在無限長時間間隔內,這與假設相悖.所以不存在Zeno行為.□

3 仿真實例

考慮多智能體系統由6個智能體節點組成,假設可能的通信拓撲圖{G1,G2,G3,G4}如圖1所示.由圖1可知,每個拓撲圖都是不連通的,但拓撲圖的并圖G1∪G2∪G3∪G4是連通的.此外還假設拓撲圖的切換順序為G1→G2→G3→G4→G1···.

將第2節所提具有狀態預測器的多智能體事件觸發一致性控制策略與文獻[24?25]中的事件觸發策略進行比較,以驗證本文所提控制策略的性能.文獻[24?25]中的控制協議相同,都為

文獻[24]中的靜態事件條件為

文獻[25]中關于觸發時刻狀態的事件條件為

圖1 拓撲圖Fig.1 Topological graph

假設初始狀態為x(0)=[?2?1 0 2 3 1]設置拓撲切換時間間隔τ=0.5s,由通信拓撲易知圖中所有的連通部分,并且將它們歸類到集合Sc和S0中,對于控制策略(7),取ρ=0.95,γ=0.3.對控制策略(9)和(10),仍按原文中取ρ=0.95,a=1,c0=0.03.

圖2是τ=0.5s時,狀態xi,i=1,2,3,4,5,6在控制策略(9)(圖2(a))、控制策略(10)(圖2(b))和控制策略(7)(圖2(c))下的運動軌跡.由圖可知,三種事件觸發控制策略都能達成一致性,且在控制策略(7)下系統更快地收斂到了平衡狀態.

圖2τ=0.5s時,三種控制策略下的狀態軌跡Fig.2 The state trajectory under three kinds of control scheme whenτ=0.5s

圖3τ=0.5s時三種控制策略下的分歧向量范數Fig.3 The Euclidean norm of disagreement vectorunder three kinds of control scheme whenτ=0.5s

圖4對比了加狀態預測器的控制策略(圖4(a))在τ=0.5s時,狀態xi(i=1,2,3,4,5,6)的軌跡.未加狀態預測時系統收斂到平衡狀態需要21.16s,文中所提策略下僅需10.89s,表明設計的狀態預測器能有效地提升系統收斂速度.

圖4 有無狀態預測控制策略下狀態軌跡對比圖Fig.4 The comparison diagram between predictive control scheme and common control scheme

圖5是每個智能體在相應控制策略下的觸發間隔圖.系統在控制策略(7),(9)和(10)下的平均觸發時間間隔分別為1.1474s,0.9461s和0.7209s.顯然多智能體系統在控制策略(7)下比在控制策略(9)和(10)下有更長的平均觸發時間間隔,因此本文所提的事件觸發條件在節約通信和計算資源方面具有更好的性能.

進一步研究拓撲切換時間間隔τ對平均觸發時間間隔的影響.保持參數ρ,a,c0,γ的取值不變,分別設置拓撲切換間隔τ為0.4s,0.5s和0.6s.表1給出了系統在各事件條件,不同切換拓撲時間τ下的平均觸發間隔時間.由表1可知,平均觸發時間間隔隨著拓撲切換周期變長而增加,并且在控制策略(7)下系統始終具有較長的平均觸發時間間隔.這進一步表明本文所提的事件觸發控制策略在節約通信和計算資源方面的性能.

4 結論

本文研究了在組合連通拓撲下基于事件觸發的多智能體系統平均一致性問題.提出一種新的具有狀態預測器的事件觸發一致性控制協議,通過分析拓撲圖中的連通部分,為每個智能體給出了基于系統狀態信息的觸發條件.在每個事件觸發時刻,每個智能體都對其鄰居智能體的未來狀態作出預測,再通過通信將預測的狀態和觸發時刻的狀態傳遞給它的鄰居個體,經所提一致性控制協議使系統達成一致性.在該控制策略下多智能體系統可在節約通信和計算資源的同時具有更快的收斂速度.基于Lyapunov穩定性理論和代數圖論,證明所提事件觸發控制策略能夠有效實現組合連通拓撲結構下的平均一致性,并且不存在Zeno行為.最后通過與已有文獻中基于事件觸發的一致性控制策略比較,仿真驗證了所提控制策略在節約通信資源和收斂速度方面的優越性.

圖5τ=0.5s每個智能體在控制策略(7)下觸發間隔Fig.5 The triggered interval of each agent under control scheme(7)

表1 事件條件(7),(9)和(10)下平均觸發間隔Table 1 The average triggered interval under event conditions(7),(9)and(10)