彭 浩，毛祥薈，谷源濤，王永程，王 玉

1)清華大學(xué)電子工程系，北京 100084；2)盲信號(hào)處理國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，成都 610041

無(wú)人機(jī)(unmanned aerial vehicle, UAV)的一致性(consensus)控制是多智能體系統(tǒng)(multi-agent system, MAS)一致性控制研究中的一個(gè)重要問(wèn)題．MAS指大量分散的自主或半自主的智能體通過(guò)網(wǎng)絡(luò)互連所構(gòu)成的復(fù)雜的大規(guī)模系統(tǒng)．每個(gè)智能體具有簡(jiǎn)單計(jì)算、信息處理與不完全通信的能力，在整個(gè)系統(tǒng)的交互式協(xié)調(diào)與配合下可實(shí)現(xiàn)一些復(fù)雜和智能的任務(wù)．多智能體的一致性控制是計(jì)算機(jī)科學(xué)與控制領(lǐng)域一直關(guān)注的熱點(diǎn)，目前在飛行器的編隊(duì)控制、傳感器網(wǎng)絡(luò)、數(shù)據(jù)融合、多機(jī)械臂協(xié)同裝備與并行計(jì)算等領(lǐng)域被廣泛應(yīng)用[1]．MAS的一致性控制[2]指在沒(méi)有中央控制及全局通信的條件下，系統(tǒng)內(nèi)的多個(gè)智能體通過(guò)信息共享與交互，最終實(shí)現(xiàn)所有智能體的某種狀態(tài)(如姿態(tài)、方向及高度等)趨同．

對(duì)MAS一致性的研究一般從系統(tǒng)動(dòng)力學(xué)及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)兩個(gè)角度進(jìn)行．從動(dòng)力學(xué)角度可將問(wèn)題建模為線性系統(tǒng)或非線性系統(tǒng)進(jìn)行研究．線性系統(tǒng)通常建模為一階、二階及高階系統(tǒng)．通過(guò)分析特征值，已得到了一階與二階線性多智能體系統(tǒng)實(shí)現(xiàn)一致性的充分必要條件．對(duì)于一階積分器，達(dá)到一致性的充分必要條件為當(dāng)且僅當(dāng)網(wǎng)絡(luò)具有生成樹(shù)[3]．而對(duì)于二階系統(tǒng)，除了要求網(wǎng)絡(luò)具有生成樹(shù)外，拉普拉斯矩陣特征值和耦合增益必須滿足其他條件[4]．REN等[5]得出了實(shí)現(xiàn)高階線性積分模型一致性的充分必要條件, 為高階線性系統(tǒng)一致性的研究奠定基礎(chǔ)．從網(wǎng)絡(luò)拓?fù)浣嵌瘸霭l(fā)，通?？紤]通信拓?fù)涞牟淮_定性對(duì)系統(tǒng)穩(wěn)定性與動(dòng)態(tài)性能的影響，包括通信時(shí)滯、隨機(jī)網(wǎng)絡(luò)及切換拓?fù)涞纫蛩兀甖HANG等[6]分析了當(dāng)網(wǎng)絡(luò)是馬爾科夫隨機(jī)切換拓?fù)浣Y(jié)構(gòu)時(shí), 系統(tǒng)達(dá)到均方一致的條件, 并給出基于線性矩陣不等式(linear matrix inequality, LMI)方法的隨機(jī)系統(tǒng)的一致性算法．通過(guò)分析MAS通信拓?fù)洌琖IELAND等[7]分別研究了有領(lǐng)導(dǎo)者和無(wú)領(lǐng)導(dǎo)者情況下，線性MAS的一致性控制問(wèn)題，并給出基于相對(duì)狀態(tài)信息的一致性協(xié)議的設(shè)計(jì)方法．

2016年，明平松等[8]對(duì)隨機(jī)時(shí)滯多智能體一致性研究進(jìn)展進(jìn)行了總結(jié)．DU等[9]將遞歸設(shè)計(jì)方法與加冪積分技術(shù)融合，使用遞歸方式構(gòu)建李雅普諾夫函數(shù)，提出基于鄰居的分布式高階有限時(shí)間一致性協(xié)議，使領(lǐng)導(dǎo)-追隨者系統(tǒng)不需領(lǐng)導(dǎo)者的速度信息就能實(shí)現(xiàn)有限時(shí)間一致．嚴(yán)志強(qiáng)等[10]針對(duì)多智能體一致性算法中的通信問(wèn)題，提出一種近鄰原則，利用部分二階和部分三階鄰居信息，在固定無(wú)向連通拓?fù)鋱D的基礎(chǔ)上，應(yīng)用于三階MAS．朱美玲等[11]在固定與切換拓?fù)淝闆r下分別給出了異構(gòu)系統(tǒng)一致性的控制協(xié)議，得到了異構(gòu)系統(tǒng)有限時(shí)間一致性的充分條件．

MAS的一致性問(wèn)題在編隊(duì)(vehicle formations)、高度對(duì)齊(altitude alignment)及集群(flocking)等場(chǎng)景被廣泛研究[12]．近年來(lái)由于無(wú)人機(jī)技術(shù)的成熟與成本的降低，無(wú)人機(jī)在軍事與民用領(lǐng)域的作用日益重要，無(wú)人機(jī)的一致性控制也成為研究熱點(diǎn)．柳向陽(yáng)等[13]提出基于多無(wú)人機(jī)目標(biāo)估計(jì)的分布式無(wú)跡信息濾波，證明了基于有向圖網(wǎng)絡(luò)的加權(quán)平均一致性算法，構(gòu)建了多無(wú)人機(jī)目標(biāo)跟蹤的模型．張佳龍等[14]基于人工勢(shì)場(chǎng)方法，提出一種雙向網(wǎng)絡(luò)連接結(jié)構(gòu)的多無(wú)人機(jī)一致性避障控制算法．張紅梅等[15]針對(duì)無(wú)人機(jī)編隊(duì)的通信拓?fù)淝袚Q，研究了一種基于聯(lián)合誤差的編隊(duì)控制方法．

本研究提出基于WPG算法的一致性控制算法，利用高效率的分布式優(yōu)化算法解決固定拓?fù)湎碌囊恢滦詥?wèn)題，并通過(guò)在無(wú)人機(jī)的高度對(duì)齊場(chǎng)景下進(jìn)行仿真，驗(yàn)證了算法的收斂性與低通信開(kāi)銷的特性．

1 WPG算法

游走近端梯度(walk proximal gradient, WPG)算法[16]是一種分布式一致性優(yōu)化的一階算法．多智能體系統(tǒng)可看作一個(gè)網(wǎng)絡(luò)G=(V,E)， 其中，V={v1,v2, …,vn}是智能體集合，E為m條邊的集合．WPG算法旨在解決如式(1)的一致性優(yōu)化問(wèn)題．

(1)

(2)

在無(wú)人機(jī)協(xié)同高度對(duì)齊這一場(chǎng)景下，為適應(yīng)無(wú)人機(jī)集群中可能出現(xiàn)的無(wú)路由場(chǎng)景，本研究在WPG算法的啟發(fā)下提出一種基于WPG算法的方法．在該方法中，當(dāng)節(jié)點(diǎn)被激活時(shí)，采用后向梯度對(duì)局部變量進(jìn)行更新，即

zt+1it=proxfi /α(xt)

(3)

對(duì)任意函數(shù)f及優(yōu)化變量x，f的近鄰算子為

(4)

調(diào)整后的方法是WPG算法在無(wú)人機(jī)高度對(duì)齊這一實(shí)例下的變種，標(biāo)準(zhǔn)WPG算法采用如式(2)的前向梯度更新，而這里采用如式(3)的后向梯度更新．調(diào)整后的方法只需在相鄰節(jié)點(diǎn)間傳遞信息，可大幅節(jié)省通信開(kāi)銷．值得一提的是，雖然在此場(chǎng)景的目標(biāo)函數(shù)f下，兩種算法可以互推，但在一般情況的凸函數(shù)f下，兩種算法并不等價(jià)，無(wú)法互推．

輸入:令牌順序I={i1, i2, …, in} 輸出:共識(shí)量 x?1 initialize x0 and z0 so that x0=12∑nj=1z0j2 repeat for t=0, 1, 2, … do3 agent it=modn(t)+1 do4 receive token xt5 update local variable zt+1it by (2)6 update token xt+1=xt+1n(zt+1it-ztit)7 send token xt+1 to agent it+18 agents j≠it do nothing; hence zt+1it=ztit9 end10output x?=xt

圖1 WPG算法(算法1)流程偽代碼

Fig.1 Pseudocode of WPG algorithm (algorithm 1) flow

2 無(wú)人機(jī)協(xié)同高度對(duì)齊模型

高度對(duì)齊本質(zhì)上是一致均值問(wèn)題，在此特定場(chǎng)景下，式(1)所示的WPG算法的優(yōu)化目標(biāo)可寫(xiě)成：

(5)

其中，aj為各無(wú)人機(jī)所處高度；x是待優(yōu)化的無(wú)人機(jī)的高度．

在此特定函數(shù)f下，當(dāng)式(3)中α→0時(shí)，此變種算法可退化為標(biāo)準(zhǔn)WPG算法，即式(2)中α=1的情況．因此，算法在有路由及無(wú)路由情況下均可工作，下面分別介紹這兩種情況．

2.1 有路由模型

定義場(chǎng)景中存在NC個(gè)無(wú)人機(jī)，每個(gè)無(wú)人機(jī)可看做網(wǎng)絡(luò)G=(V,E)中的一個(gè)節(jié)點(diǎn)，V是無(wú)人機(jī)的集合．兩個(gè)無(wú)人機(jī)之間能否直接進(jìn)行通信決定了圖中兩個(gè)節(jié)點(diǎn)是否相連，E為兩節(jié)點(diǎn)間通信鏈路的集合．在已知圖中節(jié)點(diǎn)間路由的情況下，本研究可以設(shè)計(jì)對(duì)應(yīng)的令牌順序，按照算法1的流程進(jìn)行分布式的一致性優(yōu)化．

值得一提的是，WPG算法需要在網(wǎng)絡(luò)G中遍歷所有節(jié)點(diǎn)v∈V． 因此，需要先在網(wǎng)絡(luò)G中確定一個(gè)漢密爾頓圈(存在的話)．假設(shè)網(wǎng)絡(luò)G中存在一個(gè)漢密爾頓圈(1, 2, …,n)， 那么在WPG算法中便按照1→2→…→n→1→2→…的順序進(jìn)行信息傳遞與更新．若網(wǎng)絡(luò)G中不存在漢密爾頓圈，則需確定一個(gè)至少遍歷所有節(jié)點(diǎn)1次的圈(包含重復(fù)訪問(wèn)的節(jié)點(diǎn))．在這種情況下，重復(fù)節(jié)點(diǎn)只在第1次被訪問(wèn)時(shí)激活，后續(xù)的重復(fù)訪問(wèn)將不再激活該節(jié)點(diǎn)．

2.2 無(wú)路由模型

考慮到實(shí)際情況中，路由的獲得相對(duì)困難，一般需要付出高昂的通信代價(jià)，因此本研究對(duì)WPG算法進(jìn)行推廣，把原來(lái)信息傳遞與更新的單位由一個(gè)節(jié)點(diǎn)推廣為一個(gè)簇(由若干節(jié)點(diǎn)組成的集合)．這是因?yàn)?，一般?lái)說(shuō)簇頭間的拓?fù)潢P(guān)系比整個(gè)網(wǎng)絡(luò)要簡(jiǎn)單很多，簇頭間的路由獲取的代價(jià)相對(duì)較?。诖藞?chǎng)景下簇頭間的通信需要路由信息，而簇內(nèi)的通信不需要路由．

模型目標(biāo)是經(jīng)過(guò)協(xié)同處理使所有無(wú)人機(jī)調(diào)整到同一高度x上，這可表示為一個(gè)優(yōu)化問(wèn)題，x為待優(yōu)化的參量．首先，定義簇內(nèi)目標(biāo)函數(shù)為

(6)

其中，fl(x)為第l個(gè)簇的目標(biāo)函數(shù)，表征當(dāng)前待優(yōu)化參量x與簇內(nèi)nl個(gè)無(wú)人機(jī)高度的偏離程度，當(dāng)x取最優(yōu)解時(shí)，目標(biāo)函數(shù)得到最小值．a(chǎn)l, j為第(l,j)個(gè)節(jié)點(diǎn)的原始高度．每個(gè)無(wú)人機(jī)的簇之間只能通過(guò)簇頭進(jìn)行通信，不同簇中除簇頭外的其他節(jié)點(diǎn)無(wú)法直接進(jìn)行通信．因此，整個(gè)無(wú)人機(jī)群的目標(biāo)函數(shù)可寫(xiě)作各個(gè)簇的目標(biāo)函數(shù)累加的形式，即

(7)

將式(6)描述的目標(biāo)函數(shù)代入式(3)，可得到其閉式解為

proxfl/α(xt)=

(8)

Gossip算法利用節(jié)點(diǎn)的本地信息處理能力，通過(guò)同步更新節(jié)點(diǎn)并與鄰居節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換的方式，使網(wǎng)絡(luò)達(dá)到平均共識(shí)狀態(tài)，從而避免了網(wǎng)絡(luò)中路由的開(kāi)銷和瓶頸效應(yīng)．

(9)

其中，i和j分別指第l個(gè)簇中節(jié)點(diǎn)的編號(hào)；di為節(jié)點(diǎn)i的度，k為與第i個(gè)節(jié)點(diǎn)鄰接的節(jié)點(diǎn)編號(hào)．

在得到拓?fù)渚仃嘝后，每次迭代中以待優(yōu)化向量u乘上P， 在經(jīng)過(guò)足夠的迭代后，u會(huì)收斂到初始值的均值．由P的約束關(guān)系可知，P中非鄰接節(jié)點(diǎn)對(duì)應(yīng)位置的值為0，這就保證了在每次迭代中實(shí)際上只需與鄰接的節(jié)點(diǎn)間進(jìn)行信息交換即可，故可減少通信開(kāi)銷．Gossip算法流程的偽代碼如圖2．

(10)

輸入:拓?fù)渚仃?P輸出:共識(shí)向量 u?1 initialize u02 for t=0 to N do3 ut+1= ut·P4 end5 output u?=uN+1

圖2 Gossip算法流程偽代碼

Fig.2 Pseudocode of Gossip algorithm flow

利用基于Gossip的方法，在每個(gè)簇進(jìn)行更新時(shí)，簇內(nèi)每個(gè)節(jié)點(diǎn)只需與其鄰接的節(jié)點(diǎn)之間進(jìn)行信息交換即可．在進(jìn)行N次信息交換后，簇內(nèi)所有節(jié)點(diǎn)均收斂到一致值，也就是均值．

簇頭間路由的策略非本研究的重點(diǎn)，可采用已有算法．例如，若簇頭組成了漢密爾頓網(wǎng)絡(luò)，則可采取基于漢密爾頓圈的通信策略[17-18]．而對(duì)于強(qiáng)連接的網(wǎng)絡(luò)，也有很多路由策略，如采取基于最短路徑的策略[19-20]．

3 實(shí)驗(yàn)仿真與分析

通過(guò)仿真實(shí)驗(yàn)，對(duì)比本研究提出的基于WPG的無(wú)人機(jī)一致性控制算法和不使用WPG的算法，針對(duì)高度對(duì)齊場(chǎng)景的應(yīng)用，驗(yàn)證本算法在通信效率方面的性能．

實(shí)驗(yàn)使用3個(gè)無(wú)人機(jī)群，每個(gè)機(jī)群分別包含4、5和6個(gè)無(wú)人機(jī)，共15個(gè)節(jié)點(diǎn)，每個(gè)簇之間通過(guò)簇頭通信，其拓?fù)潢P(guān)系如圖3．其中，相同灰度的節(jié)點(diǎn)屬于同一個(gè)簇．無(wú)人機(jī)的初始高度滿足[20, 120]內(nèi)均勻分布．計(jì)算機(jī)仿真在Matlab R2017a環(huán)境下進(jìn)行．

圖3 無(wú)人機(jī)群拓?fù)銯ig.3 Topology of UAV clusters

3.1 有路由情況

在使用一些路由算法及付出相應(yīng)的通信開(kāi)銷后，可獲得無(wú)人機(jī)群通信的路由．在有路由的情況下，可直接應(yīng)用以單個(gè)節(jié)點(diǎn)為單位進(jìn)行信息傳遞更新的方法，即信息按照路由每次在各個(gè)無(wú)人機(jī)間進(jìn)行傳遞與更新．初始化設(shè)x0=z0=0， 最大迭代次數(shù)設(shè)為30．

在有路由的情況下，基于WPG的算法收斂速度如圖4．由圖4可見(jiàn)，信息令牌在15次更新后，亦即在所有無(wú)人機(jī)節(jié)點(diǎn)間傳遞一遍后收斂于所有無(wú)人機(jī)初始高度的均值．在已知路由的情況下，本算法在有限步內(nèi)精確收斂到最優(yōu)解．若無(wú)人機(jī)總數(shù)為NC， 則算法在NC次迭代后收斂，且相對(duì)誤差在10-16以下，也就是說(shuō)，完成信息令牌在所有無(wú)人機(jī)間的1次傳遞即可．

圖4 有路由情況下WPG算法的收斂性曲線Fig.4 Convergence of WPG algorithm without routing

3.2 無(wú)路由情況

由于獲取路由的開(kāi)銷往往較大，在缺少簇內(nèi)路由，但可得到簇頭間路由的情況下，應(yīng)用上述以單個(gè)簇為單位進(jìn)行信息傳遞更新的WPG算法．即信息每次在各個(gè)簇的簇頭之間進(jìn)行傳遞與更新，在簇內(nèi)通過(guò)基于Gossip迭代方法收斂到簇內(nèi)的一致值．初始化設(shè)x0=z0j=70,j=1, 2, …,n,α=90， Gossip算法的迭代次數(shù)N=45．

無(wú)路由情況下基于WPG的算法收斂速度如圖5(a)．從圖5(a)可見(jiàn)，本算法收斂性佳，信息令牌x在200次更新后就收斂到無(wú)人機(jī)群的一致值，且相對(duì)誤差在10-3以下，遠(yuǎn)低于無(wú)人機(jī)厘米級(jí)的控制誤差．

由于在通常情況下，相對(duì)于簇間的通信開(kāi)銷，簇內(nèi)的通信開(kāi)銷可以忽略，因此，以簇間的通信次數(shù)作為衡量通信開(kāi)銷的指標(biāo)．從圖5(b)可見(jiàn)，在引入WPG算法后，通信效率得到大幅提升，在同樣的誤差下，引入WPG算法的通信開(kāi)銷要遠(yuǎn)小于改進(jìn)前的算法．原因是改進(jìn)前的算法在每次迭代時(shí)需更新所有的簇頭信息，而改進(jìn)后的算法在每次迭代時(shí)只需更新一個(gè)簇頭信息．同時(shí)觀察到，當(dāng)基于WPG的算法收斂時(shí)，在同樣的通信開(kāi)銷下，基于WPG算法的均方誤差要比改進(jìn)前減小23 dB．

圖5 無(wú)路由情況收斂性及通信開(kāi)銷Fig.5 Convergence and communication overhead without routing

結(jié) 語(yǔ)

本研究將分布式優(yōu)化算法WPG引入到無(wú)人機(jī)的一致性控制問(wèn)題中，并在高度對(duì)齊場(chǎng)景中進(jìn)行建模仿真．在有路由的情況下，算法可在有限步內(nèi)很快收斂，且收斂的精度很高；在無(wú)路由的情況下，將WPG算法進(jìn)行推廣并與Gossip方法結(jié)合．推廣后的算法仍然具有很好的收斂性，并具有很高的通信效率，可大幅節(jié)約通信開(kāi)銷．