基于WPG的無人機一致性控制算法

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

1)清華大學電子工程系，北京 100084；2)盲信號處理國家級重點實驗室，成都 610041

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

對MAS一致性的研究一般從系統(tǒng)動力學及網絡拓撲結構兩個角度進行．從動力學角度可將問題建模為線性系統(tǒng)或非線性系統(tǒng)進行研究．線性系統(tǒng)通常建模為一階、二階及高階系統(tǒng)．通過分析特征值，已得到了一階與二階線性多智能體系統(tǒng)實現(xiàn)一致性的充分必要條件．對于一階積分器，達到一致性的充分必要條件為當且僅當網絡具有生成樹[3]．而對于二階系統(tǒng)，除了要求網絡具有生成樹外，拉普拉斯矩陣特征值和耦合增益必須滿足其他條件[4]．REN等[5]得出了實現(xiàn)高階線性積分模型一致性的充分必要條件, 為高階線性系統(tǒng)一致性的研究奠定基礎．從網絡拓撲角度出發(fā)，通?？紤]通信拓撲的不確定性對系統(tǒng)穩(wěn)定性與動態(tài)性能的影響，包括通信時滯、隨機網絡及切換拓撲等因素．ZHANG等[6]分析了當網絡是馬爾科夫隨機切換拓撲結構時, 系統(tǒng)達到均方一致的條件, 并給出基于線性矩陣不等式(linear matrix inequality, LMI)方法的隨機系統(tǒng)的一致性算法．通過分析MAS通信拓撲，WIELAND等[7]分別研究了有領導者和無領導者情況下，線性MAS的一致性控制問題，并給出基于相對狀態(tài)信息的一致性協(xié)議的設計方法．

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

MAS的一致性問題在編隊(vehicle formations)、高度對齊(altitude alignment)及集群(flocking)等場景被廣泛研究[12]．近年來由于無人機技術的成熟與成本的降低，無人機在軍事與民用領域的作用日益重要，無人機的一致性控制也成為研究熱點．柳向陽等[13]提出基于多無人機目標估計的分布式無跡信息濾波，證明了基于有向圖網絡的加權平均一致性算法，構建了多無人機目標跟蹤的模型．張佳龍等[14]基于人工勢場方法，提出一種雙向網絡連接結構的多無人機一致性避障控制算法．張紅梅等[15]針對無人機編隊的通信拓撲切換，研究了一種基于聯(lián)合誤差的編隊控制方法．

本研究提出基于WPG算法的一致性控制算法，利用高效率的分布式優(yōu)化算法解決固定拓撲下的一致性問題，并通過在無人機的高度對齊場景下進行仿真，驗證了算法的收斂性與低通信開銷的特性．

1 WPG算法

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

(1)

(2)

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

zt+1it=proxfi /α(xt)

(3)

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

(4)

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

輸入:令牌順序I={i1, i2, …, in} 輸出:共識量 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 無人機協(xié)同高度對齊模型

高度對齊本質上是一致均值問題，在此特定場景下，式(1)所示的WPG算法的優(yōu)化目標可寫成：

(5)

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

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

2.1 有路由模型

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

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

2.2 無路由模型

考慮到實際情況中，路由的獲得相對困難，一般需要付出高昂的通信代價，因此本研究對WPG算法進行推廣，把原來信息傳遞與更新的單位由一個節(jié)點推廣為一個簇(由若干節(jié)點組成的集合)．這是因為，一般來說簇頭間的拓撲關系比整個網絡要簡單很多，簇頭間的路由獲取的代價相對較?。诖藞鼍跋麓仡^間的通信需要路由信息，而簇內的通信不需要路由．

模型目標是經過協(xié)同處理使所有無人機調整到同一高度x上，這可表示為一個優(yōu)化問題，x為待優(yōu)化的參量．首先，定義簇內目標函數(shù)為

(6)

其中，fl(x)為第l個簇的目標函數(shù)，表征當前待優(yōu)化參量x與簇內nl個無人機高度的偏離程度，當x取最優(yōu)解時，目標函數(shù)得到最小值．al, j為第(l,j)個節(jié)點的原始高度．每個無人機的簇之間只能通過簇頭進行通信，不同簇中除簇頭外的其他節(jié)點無法直接進行通信．因此，整個無人機群的目標函數(shù)可寫作各個簇的目標函數(shù)累加的形式，即

(7)

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

proxfl/α(xt)=

(8)

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

(9)

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

在得到拓撲矩陣P后，每次迭代中以待優(yōu)化向量u乘上P， 在經過足夠的迭代后，u會收斂到初始值的均值．由P的約束關系可知，P中非鄰接節(jié)點對應位置的值為0，這就保證了在每次迭代中實際上只需與鄰接的節(jié)點間進行信息交換即可，故可減少通信開銷．Gossip算法流程的偽代碼如圖2．

(10)

輸入:拓撲矩陣 P輸出:共識向量 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的方法，在每個簇進行更新時，簇內每個節(jié)點只需與其鄰接的節(jié)點之間進行信息交換即可．在進行N次信息交換后，簇內所有節(jié)點均收斂到一致值，也就是均值．

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

3 實驗仿真與分析

通過仿真實驗，對比本研究提出的基于WPG的無人機一致性控制算法和不使用WPG的算法，針對高度對齊場景的應用，驗證本算法在通信效率方面的性能．

實驗使用3個無人機群，每個機群分別包含4、5和6個無人機，共15個節(jié)點，每個簇之間通過簇頭通信，其拓撲關系如圖3．其中，相同灰度的節(jié)點屬于同一個簇．無人機的初始高度滿足[20, 120]內均勻分布．計算機仿真在Matlab R2017a環(huán)境下進行．

圖3 無人機群拓撲Fig.3 Topology of UAV clusters

3.1 有路由情況

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

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

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

3.2 無路由情況

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

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

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

圖5 無路由情況收斂性及通信開銷Fig.5 Convergence and communication overhead without routing

結 語

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