嚴(yán)志強(qiáng) 葛磊 張躍躍 竇磊

1.南京理工大學(xué)瞬態(tài)物理國(guó)家重點(diǎn)實(shí)驗(yàn)室南京210094

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

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

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

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

對(duì)于高階多智能體系統(tǒng),2006年,Ren 等[14]研究了在有向圖中多車輛系統(tǒng)的協(xié)同控制一致性問題;2014年,Zhu等[15]探究了高階系統(tǒng)在切換拓?fù)淝疤嵯碌囊恢滦詥栴}等.

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

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

1 基礎(chǔ)知識(shí)

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

2 一致性協(xié)議與分析

2.1 一致性協(xié)議

2.2 一致性分析

2.2.1 TNI 分析

圖1 與圖2 是TNI 算法所對(duì)應(yīng)的無向通信拓?fù)?圖1 中實(shí)線連接的兩個(gè)節(jié)點(diǎn)互為一階鄰居節(jié)點(diǎn),虛線連接的兩個(gè)節(jié)點(diǎn)互為二階鄰居節(jié)點(diǎn),圖2 實(shí)線連接的兩個(gè)節(jié)點(diǎn)互為三階鄰居節(jié)點(diǎn).其對(duì)應(yīng)的拉普拉斯矩陣為

圖1 TNI 一階與二階通信拓?fù)銯ig.1 TNI first-order and second-order communication topology

圖2 TNI 三階通信拓?fù)銯ig.2 TNI third-order communication topology

2.2.2 PTNI 分析

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

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

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

圖3 PTNI 部分三階通信拓?fù)銯ig.3 PTNI part of third-order communication topology

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

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

2.2.3 PPTNI 分析

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

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

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

圖4 PTNI 部分二階通信拓?fù)銯ig.4 PTNI part of second-order communication topology

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

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

3 一致性仿真

在這部分,我們將根據(jù)上述通信拓?fù)浣o出數(shù)值例子,通過仿真檢驗(yàn)所提算法的性能.通過推論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)在有限時(shí)間內(nèi)快速達(dá)到一致性并且性能穩(wěn)定,驗(yàn)證了算法的可行性和有效性.上述仿真數(shù)據(jù)列如表1所示.

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

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

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

4 結(jié)束語

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