嚴志強 葛磊 張躍躍 竇磊

1.南京理工大學(xué)瞬態(tài)物理國家重點實驗室南京210094

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

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

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

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

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

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

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

1 基礎(chǔ)知識

圖論是一致性算法研究的基礎(chǔ)知識.一個加權(quán)的有向或無向圖G定義為G=(V,E,A),其中,V={v1,···,vn}是節(jié)點集,E ?V ×V是一組邊,用來描述多智能體之間的聯(lián)絡(luò)關(guān)系.此外,n是節(jié)點數(shù)目,屬于邊集合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 一致性協(xié)議與分析

2.1 一致性協(xié)議

2.2 一致性分析

2.2.1 TNI 分析

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

圖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)的系統(tǒng)(4)可以寫為

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

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

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

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

其對應(yīng)的拉普拉斯矩陣為

2.2.3 PPTNI 分析

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

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

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

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

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

其對應(yīng)的拉普拉斯矩陣為

3 一致性仿真

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

使用給出的數(shù)據(jù),分別得到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

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

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

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

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

4 結(jié)束語

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