基于部分三階鄰居信息的一致性算法

嚴志強 葛磊 張躍躍 竇磊

1.南京理工大學瞬態物理國家重點實驗室南京210094

多智能體系統控制在近些年發展迅速,廣泛應用于無人機編隊、傳感器網絡、機械臂裝配、多導彈的聯合攻擊等領域[1-2].因此,一致性問題成為多智能體系統研究中的核心問題.一致性[3]的定義為:隨著時間的演變,多智能體系統中的所有個體的某一個或者幾個狀態趨于一致.一致性協議是人為規定的智能體之間的通信原則,它描述了各個智能體與其他智能體的通信規則和通信過程.

本文研究的三階多智能體系統具有一定的工程意義.對加速度求導得到急動度,也稱為力變率,用以描述加速度變化率.特別地,在交通運輸設計上往往需要急動度來解決問題.例如:汽車工程師可用急動度作為衡量乘客舒適度的指數[4];Lorens 通過特殊的變形后,即用具有一個獨立變量的三階微分方程描述問題,可以把蝴蝶效應變成一個類似的一維突變運動;JW2-3D 型加加速度計主要用于強地震觀測等等.此外,三階系統在日常生活和工程中又是常見的,其性能指數比較復雜,因此,三階多智能體系統的研究有著十分重要的意義.

學者們最早研究的是一階多智能體系統,結果頗多，理論相對完善,其中具有代表性的是2004年Olfati-Saber 等[5]研究的一階多智能體系統在切換網絡拓撲下的一致性問題,該文獻在一致性問題研究上具有開創性意義,為多智能體一致性問題研究奠定了基礎.在二階多智能體一致性問題研究上,目前也取得了大量研究成果.例如,2007年,Sun 等[6]研究了二階多智能體系統在拓撲分別為固定和切換的條件下的均勻一致性問題;2009年,Lin 等[7]探究了帶有不均勻時滯的離散時間二階系統在動態交換拓撲條件下的一致性問題;2010年,Yu 等[8]探究了在有向圖的假設條件下帶時滯和不帶時滯的二階系統一致性問題等.

對于三階多智能體系統,許格升等[9]研究了在有向圖中,利用分段連續可微的向量表示理想時變編隊,將編隊問題轉化為一致性問題,再通過使用復系數的Hurwitz 多項式證明了三階系統設計編隊的充要條件;董滔等[10]研究了基于事件觸發控制的三階離散多智能體系統,利用位置、速度和加速度的測量誤差,設計了具有創新意義的事件觸發控制機制,然后通過不等式運算給出了多智能體系統達到一致的充分條件;文獻[11] 針對三階多智能體系統提出了一種計算控制輸入中的加權系數的算法,并通過Hurwitz 多項式證明該系統的一致性;文獻[12-13] 研究了三階時延多智能體系統,通過矩陣理論和Nyquist 準則,著重建立了最大可容忍通信延遲與非零特征值和圖拉普拉斯矩陣之間的對應關系.

對于高階多智能體系統,2006年,Ren 等[14]研究了在有向圖中多車輛系統的協同控制一致性問題;2014年,Zhu等[15]探究了高階系統在切換拓撲前提下的一致性問題等.

目前對于特定三階多智能體系統的研究還相對較少,并且隨著智能體的增加,系統達到一致的時間和通訊線路數量也大大增加,針對這個問題,通過新規定的近鄰原則,合理地減少通訊線路,優化系統收斂速度,提出了基于部分鄰居信息的一致性算法.

本文安排如下:第1 節對相關圖論和矩陣理論作了初步的介紹;第2 節給出并證明了典型三階一致性算法,并且提出近鄰規則,進而得到兩種不同的算法,新算法能夠加快系統收斂速度,減少通信負擔;第3 節為了驗證理論結果,進行了三種算法的仿真并給出數值比較;最后,第4 節對全文進行了總結.

1 基礎知識

圖論是一致性算法研究的基礎知識.一個加權的有向或無向圖G定義為G=(V,E,A),其中,V={v1,···,vn}是節點集,E ?V ×V是一組邊,用來描述多智能體之間的聯絡關系.此外,n是節點數目,屬于邊集合E的eij,定義為eij=(vi,vj)∈E,其中,vi表示邊E的起始端,vj表示邊E的末端,圖可以分為兩類,有向圖和無向圖.如果圖的邊是有向的,則圖是有向的.那么(vi,vj)∈E ／=(vj,vi)∈E,則eij=(vi,vj)表示第i個智能體向第j個智能體傳輸信息;如果拓撲圖的邊是無向的,那么圖是無向的,那么(vi,vj)∈E=(vj,vi)∈E,則eij=(vi,vj)表示第i個智能體與第j個智能體之間互相傳輸信息.

2 一致性協議與分析

2.1 一致性協議

2.2 一致性分析

2.2.1 TNI 分析

圖1 與圖2 是TNI 算法所對應的無向通信拓撲,圖1 中實線連接的兩個節點互為一階鄰居節點,虛線連接的兩個節點互為二階鄰居節點,圖2 實線連接的兩個節點互為三階鄰居節點.其對應的拉普拉斯矩陣為

圖1 TNI 一階與二階通信拓撲Fig.1 TNI first-order and second-order communication topology

圖2 TNI 三階通信拓撲Fig.2 TNI third-order communication topology

2.2.2 PTNI 分析

具有控制輸入(7)的系統(4)可以寫為

對于系統(20),在TNI 通信拓撲圖的基礎上,不改變一階與二階通信拓撲,通過近鄰規則去除了部分三階通信線路,去除方法如下.

圖1 和圖2 給出了一階、二階和三階通信拓撲圖,圖3是對應的PTNI 算法,我們通過近鄰原則去除了部分三階鄰居通信線路.

圖3 PTNI 部分三階通信拓撲Fig.3 PTNI part of third-order communication topology

三階近鄰原則為:越位于上層的智能體就越重要,每個智能體都會與智能體1 進行通訊,在其他智能體與1 通信時會優先選擇復雜度最低的路線.在圖3 中,智能體7 的三階鄰居為1 和5,7 在與1 進行通訊的時候,就不會通過5 再與1 進行通訊,智能體10 同理;再例如,8 的三階鄰居為1,4,6,首先8 會優先選擇直接與1 通信,舍棄與4,6 之間的通信,智能體9 同理.

其對應的拉普拉斯矩陣為

2.2.3 PPTNI 分析

具有控制輸入(8)的系統(4)可以寫為

對于系統(21),在PTNI 通信拓撲圖的基礎上,不改變部分三階通信拓撲,通過近鄰規則去除了部分二階通信線路,去除方法如下.

圖3 和圖4 是PPTNI 算法所對應的無向通信拓撲,我們通過近鄰原則去除了部分二階與三階鄰居通信線.

圖4 PTNI 部分二階通信拓撲Fig.4 PTNI part of second-order communication topology

二階近鄰原則為:越位于上層的智能體就越重要,每個智能體都會與智能體1 進行通訊,在其他智能體與1 通信時會優先選擇復雜度最低的路線,當某一智能體與另一智能體進行通訊,并且存在多條復雜度相同的通訊線時,只會選擇其中一條進行通信.在圖4 中,智能體4 的二階鄰居為1 和5,4 在與1 進行通訊的時候,就不會通過5 再與1 進行通訊，智能體6 同理；再例如，8 的二階鄰居為2,3,9，首先8 只會優先選擇上層鄰居進行通信而舍棄同層鄰居9，在與上層鄰居2,3 通訊的時候,8 會優先選擇2 進行通信,然后通過2與1 進行通信l,而不會選擇越過5 與3 通信再與1 通信,智能體9 同理.

其對應的拉普拉斯矩陣為

3 一致性仿真

在這部分,我們將根據上述通信拓撲給出數值例子,通過仿真檢驗所提算法的性能.通過推論1 給出可調參數k1=0.3,k2=1 和k3=1,模擬的初始位置、速度和加速度如下:

使用給出的數據,分別得到TNI、PTNI 和PPTNI 仿真圖，如圖5～7所示.

圖5 TNI 仿真圖Fig.5 Simulated diagrams of TNI

圖6 PTNI 仿真圖Fig.6 Simulated diagrams of PTNI

圖7 PPTNI 仿真圖Fig.7 Simulated diagrams of PPTNI

由仿真結果可知,三種算法均能夠使系統(4)在有限時間內快速達到一致性并且性能穩定,驗證了算法的可行性和有效性.上述仿真數據列如表1所示.

表1 收斂速度達到一致的時間(取值誤差為1%)Table 1 Times that the convergence speed achieves consensus

在表1 中,分別列出了應用三種算法的多智能體系統達到一致的最小時間,最大時間和平均時間.通過表中數據可以明顯看出,使用部分三階鄰居信息算法(PTNI)的系統的一致收斂速度比使用典型三階鄰居信息算法(TNI)的系統的一致收斂速度要快,前者的通訊線路數量從35 減少到29,減少率為17.14%,當通信拓撲圖更為復雜時,后者達到一致的平均時間將明顯比前者小的多;此外,使用部分二階與三階鄰居信息算法(PPTNI)的系統的收斂速度比典型三階鄰居信息算法(TNI)和部分三階鄰居信息算法(PTNI)的系統的收斂速度都要快,并且其通信邊緣數量從35 減少到24,減少率為31.43%.當系統更為復雜時,PTNI 算法和PPTNI算法達到一致性的時間將減少得更為明顯.

由此可見,在實現多智能體系統一致性的前提下,部分三階鄰居信息算法(PTNI)和部分二階與三階鄰居信息算法(PPTNI)加快了三階系統一致性達成速度,提高了系統的效率,并且優化了通信線數量,降低了實際成本.

4 結束語

在連通但不相關的通信拓撲圖設定下，本文考慮了多智能體一致性算法中的通信問題.基于典型三階鄰居信息一致性算法(TNI),我們提出了二階和三階近鄰原則，進而設計了部分三階鄰居信息算法(PTNI)和部分二階與三階鄰居算法(PPTNI).實驗結果表明:TNI 算法可實現多智能體系統的一致性,解決了一致性問題;在此基礎上,PTNI 和PPTNI收斂速度均快于TNI,并且通訊代價也大大減少.這說明PTNI 和PPTNI 算法能夠發揮優化作用,在提高系統的響應速度的同時,也降低了實際成本.