陶忠良 蒲志強 王樂樂 付清旭 耿虎軍

1.中國科學(xué)院大學(xué)人工智能學(xué)院 北京 100049 2.中國科學(xué)院自動化研究所 北京 100190 3.中國電子科技集團公司第五十四研究所 河北石家莊 050080

多無人機具有分布性、靈活性、簡單性等優(yōu)勢,可以完成單架無人機無法完成的復(fù)雜任務(wù),在軍事作戰(zhàn)[1]、搜索救援[2]、編隊表演[3]等領(lǐng)域具有廣泛的應(yīng)用前景.特別是在現(xiàn)代化的軍事作戰(zhàn)場景中[4-5],指揮中心與作戰(zhàn)單元、作戰(zhàn)單元與作戰(zhàn)單元之間的通信交流是影響勝負的重要因素,一個經(jīng)典應(yīng)用場景是利用多無人機快速形成區(qū)域通信覆蓋,對覆蓋范圍內(nèi)我方特定目標(biāo)群體提供通信支援以增強通信質(zhì)量,對敵方特定目標(biāo)群體進行通信干擾以阻礙敵方通信交互.其中,多無人機與目標(biāo)的合理匹配是提高目標(biāo)覆蓋率的重要影響因素,因此,目標(biāo)的覆蓋問題可歸結(jié)為目標(biāo)的優(yōu)化分配問題.然而,當(dāng)無人機的覆蓋能力有限、目標(biāo)類型多樣、目標(biāo)價值各異時,多目標(biāo)優(yōu)化分配是一個較為困難的求解問題.同時,由于無人機自身的通信距離有限,為了滿足無人機之間的信息傳遞需求,無人機需要時刻保持通信連通.但在無人機規(guī)模較大時,同時實現(xiàn)協(xié)同覆蓋并保持通信實時連通更是一個復(fù)雜的多任務(wù)組合優(yōu)化問題.此外,為滿足實際應(yīng)用需求,需考慮無人機僅已知自身與鄰居的局部信息條件下的分布式求解框架.綜上所述,在局部信息條件和受限的通信距離、覆蓋能力等約束條件下,大規(guī)模無人機同時實現(xiàn)多類目標(biāo)的協(xié)同覆蓋和通信連通保持,是一個極具挑戰(zhàn)的理論和應(yīng)用問題.

針對協(xié)同覆蓋問題,相關(guān)研究者提出了一系列啟發(fā)式的優(yōu)化算法.其中,文獻[6-7]采用貪婪策略來尋找多目標(biāo)優(yōu)化分配覆蓋問題的次優(yōu)解.Zhang 等提出了分布式自適應(yīng)反演控制方法來實現(xiàn)動態(tài)多目標(biāo)跟蹤覆蓋[8].Lyu 等提出了一種螺旋算法,實現(xiàn)分配盡可能少的無人機去覆蓋所有地面目標(biāo)[9].以上研究在目標(biāo)覆蓋問題上提供了較優(yōu)的解決方案,但與許多研究[10-12]類似,均假設(shè)無人機的通信范圍足夠大,從而在默認通信連通的情況下重點研究目標(biāo)的分配覆蓋問題.

為了保證連通性,Reily 等人通過設(shè)計多個領(lǐng)導(dǎo)者之間相互保持通信來實現(xiàn)整個全局的連通[13],但在這種控制方式下,跟隨者被束縛在領(lǐng)導(dǎo)者通信范圍內(nèi),降低了群體的靈活性.受生態(tài)學(xué)啟發(fā),Egerstedt 等設(shè)計了控制屏障函數(shù)（control barrier functions,CBF）對連通性與覆蓋率進行優(yōu)化[14],隨后文獻[15]基于CBF采用集中式優(yōu)化的方式來保證通信連通.文獻[16]提出了一種連通約束下的感知覆蓋策略并獲得了較好的覆蓋效果,為通信連通保持約束下的目標(biāo)覆蓋問題提供了有效的解決方案.但由于以上集中式控制方法存在中央處理器單點故障問題以及可擴展性差等缺點,在多無人機的多目標(biāo)覆蓋中,分布式控制方法提供了另一種更實用的解決方案,因此,一些研究者提出了分布式控制方案.基于梯度下降法,文獻[17-19]實現(xiàn)了一種具有區(qū)域覆蓋目標(biāo)的魯棒分布式連通保持方法,在應(yīng)用于多目標(biāo)覆蓋場景時,雖然可以通過適當(dāng)?shù)膮?shù)調(diào)整來保證連通性,但由于采取梯度下降法對智能體的移動產(chǎn)生較大約束,降低了目標(biāo)的覆蓋性能,因此,很難在保持連通性的同時盡可能覆蓋更多的目標(biāo).

針對上述文獻的不足,同時考慮無人機通信連通性要求、對目標(biāo)覆蓋能力有限、不同目標(biāo)類型以及目標(biāo)價值各異等因素,本文提出了一種基于分布式協(xié)商的多無人機目標(biāo)覆蓋與連通保持算法.由于Choi 等提出的基于分布式共識的拍賣算法（consensus-based auction algorithm,CBAA）可以有效解決多目標(biāo)無沖突分配問題[20],因此,本文以CBAA 為基礎(chǔ)構(gòu)建分布式協(xié)商機制.設(shè)計了基于無人機覆蓋能力的目標(biāo)分組方法來對目標(biāo)進行分組,將單架無人機所能覆蓋的目標(biāo)數(shù)量上限打包為單個目標(biāo),從而將單無人機-多目標(biāo)的覆蓋問題轉(zhuǎn)化為單無人機-單目標(biāo)的覆蓋問題；設(shè)計目標(biāo)拍賣規(guī)則來對目標(biāo)進行拍賣,以獲得比當(dāng)前覆蓋目標(biāo)收益更大的目標(biāo)列表；通過設(shè)計協(xié)商一致及連通保持機制,來指導(dǎo)多無人機在目標(biāo)優(yōu)化分配的同時考慮通信連通保持行為；分別設(shè)計了在不同目標(biāo)數(shù)量、不同目標(biāo)類型,以及不同目標(biāo)價值等參數(shù)下的仿真實驗,從而驗證算法的有效性.

本文主要貢獻歸納：1）提出了基于無人機覆蓋能力的目標(biāo)分組方法.將目標(biāo)進行按類分組并限制每組的目標(biāo)數(shù)量在無人機的覆蓋能力內(nèi),將得到的每個組視為無人機覆蓋的新目標(biāo),從而同時解決了無人機覆蓋能力有限以及目標(biāo)不同類型的問題.2）基于CBAA 設(shè)計了協(xié)商一致與連通保持機制.通過分布式協(xié)商的方式實現(xiàn)無沖突的目標(biāo)優(yōu)化分配,同時保持通信連通性.3）設(shè)計了連通支援機制來提高無人機的協(xié)同性能.當(dāng)無人機前往覆蓋某個目標(biāo)會對通信連通帶來破壞時,通過向鄰居發(fā)出連通支援請求,從而在保證連通性的同時實現(xiàn)分布式架構(gòu)下的良好協(xié)同性.

1 問題描述及基礎(chǔ)知識

1.1 問題描述

假如初始時刻已通過某種方式實現(xiàn)全局連通（如基于全局信息的覆蓋方法）,無人機的任務(wù)是在接下來的時間內(nèi),僅在獲取局部信息的條件下,通過分布式協(xié)商方式來對目標(biāo)進行協(xié)商分配,同時考慮通信連通性來實現(xiàn)目標(biāo)優(yōu)化覆蓋和連通保持.假定目標(biāo)進入無人機的覆蓋范圍即可對目標(biāo)進行通信支援或通信干擾,因此,本文將無人機對地面多目標(biāo)的通信支援與干擾歸結(jié)為一類通信連通保持與動態(tài)多目標(biāo)的優(yōu)化覆蓋問題,并建模為：

其中,式（1）中xij和xik為決策變量,如xij=1 表示無人機i 前往覆蓋我方目標(biāo)j,反之xij=0；式（2）中是無人機的通信約束項,具體將在2.2 節(jié)中作出說明；式（3）與式（4）為無人機最大目標(biāo)覆蓋能力約束項,即無人機i 最多只能覆蓋c 個目標(biāo)；式（5）中xi為無人機覆蓋目標(biāo)類型約束條件,即無人機i 只能同時覆蓋一類目標(biāo),其中,xi=xij+xik.

上述問題場景及建模方式除適用于多無人機通信覆蓋外,同樣適用于多無人機協(xié)同態(tài)勢感知、協(xié)同災(zāi)害救援、協(xié)同目標(biāo)跟蹤等場景.因此,本文所針對的是一類典型的實際應(yīng)用場景.

1.2 基礎(chǔ)知識

1.2.1 網(wǎng)絡(luò)的連通性判定

其中,Rc為無人機的通信半徑,dij為無人機i 與無人機j 之間的距離大小,當(dāng)時表示可進行通信并設(shè)置aij=1,反之a(chǎn)ij=0.文中無人機只能與通信范圍內(nèi)的其他無人機進行通信,這些無人機可以用一個鄰居集表示.

圖的連通性與拉普拉斯矩陣密切相關(guān),任意一個拓撲圖G 的結(jié)構(gòu)特性都可以用拉普拉斯矩陣L=D-A等價表示,其中,D 為度矩陣,也是一個對角矩陣,其對角線上的元素為節(jié)點的鄰居數(shù)；A 為上文中所提到的鄰接矩陣,用于表示節(jié)點之間的連接關(guān)系.由文獻[21-22]知,圖G 的連通性可由拉普拉斯矩陣的第二小特征值進行判定：當(dāng)＞0 時,可判定圖G 是連通的,且該值越大,圖的連通度越強；當(dāng)=0 時,可得知圖G 不連通.如圖1判斷圖G 的連通性為例,首先由圖的度矩陣D 和鄰接矩陣A 計算得到圖的拉普拉斯矩陣L；其次再計算拉普拉斯矩陣的第二小特征值；最后由＞0 可進一步判斷得到圖G 為一個連通圖.

圖1 判斷圖的連通性Fig.1 Connectivity of graphs judges by

1.2.2 地圖柵格化

考慮到正六邊形可以實現(xiàn)無重疊和無縫隙排布,文中采用六邊形柵格化的方式來實現(xiàn)地圖離散化表達,并設(shè)置正六邊形的邊長等于無人機的覆蓋半徑Rr.如圖2所示,無人機的覆蓋范圍正好為正六邊形的外接圓范圍,因此,當(dāng)無人機處于正六邊形柵格中心時,正好可以實現(xiàn)對該正六邊形柵格區(qū)域中目標(biāo)的完全覆蓋,同時無人機的運動轉(zhuǎn)化為不同柵格中心點的跳動,由此簡化了問題求解.

圖2 柵格化地圖中目標(biāo)覆蓋示意圖Fig.2 Schematic representation of targets coverage in a rasterized map

為了聚焦研究問題,本文作出如下假設(shè)：1）無人機具有自主避障功能,因此,不考慮無人機間及與環(huán)境障礙物間的碰撞.2）在每一步長中,無人機可以從某個柵格單元位置移動到相鄰的6 個柵格單元之一.3）無人機性能良好,不考慮燃料耗盡或無人機自身故障等因素.

2 算法設(shè)計

對于給定的目標(biāo)列表和無人機列表,算法的最終目的是找到一個無沖突的目標(biāo)與無人機匹配方案,使得無人機群所獲收益最大化.如果每個目標(biāo)分配給不超過一架無人機,則可稱為一個沒有沖突的目標(biāo)分配方案.本文所研究的問題是一個較為復(fù)雜的目標(biāo)優(yōu)化分配與連通保持問題,由于建模不確定性、問題大規(guī)模性等因素,模型（1）～模型（5）在實際中很難求解.大部分研究者通過集中式組合優(yōu)化方法或啟發(fā)式優(yōu)化方法來求解,但集中式控制本身存在可擴展性差、抗毀性差等問題.而分布式協(xié)商是一種以個體分布式而非某個中心節(jié)點集中控制的方法并行計算以提高效率,且有較強的魯棒性、容錯性和可擴展性,通過多輪迭代的方式進行資源優(yōu)化分配,最終通過協(xié)商實現(xiàn)資源一致性分配.因此,本文以分布式協(xié)商的方式來求解上述問題.

2.1 CBAA 算法簡介

CBAA 算法是一種去中心化的拍賣方法,即不需要拍賣師即可解決沖突.算法由兩階段組成,第1 階段是拍賣過程,每架無人機以異步方式對目標(biāo)進行投標(biāo)并得到中標(biāo)列表,該過程是為了獲取有效的目標(biāo)列表；第2 階段是協(xié)商一致過程,無人機利用協(xié)商一致的策略來對中標(biāo)列表中的目標(biāo)進行無沖突分配.

2.2 局部劃分定義

考慮到無人機只能與其通信范圍內(nèi)的無人機通信,本文將無人機i 及其鄰居Ni視為一個局部,并表示為,這種局部的劃分方式使得各個局部之間互有交集.假如初始時刻全局通信連通,如果所有局部通信在任意相鄰時刻均連通,那么全局通信在任意時刻也將實現(xiàn)連通[23].因此,在本文的分布式控制下,多無人機的通信連通將由各個局部的通信連通保持來共同實現(xiàn).

2.3 分布式協(xié)商目標(biāo)分配方案架構(gòu)設(shè)計

在多無人機系統(tǒng)中,由于每架無人機的鄰居數(shù)量以及通信距離有限,在分布式控制下,讓無人機群實現(xiàn)某種行為或資源分配的一致性尤為困難[24-26].結(jié)合本文研究問題的任務(wù)需求,設(shè)計一個合理有效的分布式控制架構(gòu),并基于此架構(gòu)進一步設(shè)計分布式協(xié)商目標(biāo)分配與連通保持算法.

圖3展示了多無人機分布式協(xié)商目標(biāo)分配方案整體構(gòu)架,算法將通過底層分布式局部協(xié)商的方式,來獲取無沖突的全局目標(biāo)優(yōu)化分配方案.然而無沖突的全局目標(biāo)分配方案要求各局部內(nèi)以及各局部間都不存在目標(biāo)分配沖突,因此,需要局部內(nèi)和局部間均進行協(xié)商以實現(xiàn)無沖突的目標(biāo)優(yōu)化分配.

由于本文的局部劃分方式使得局部之間互有交集,故局部間協(xié)商問題可隱含于局部之間的信息交集中,因此,僅考慮局部內(nèi)協(xié)商即可.以圖3中虛線所圈出的無人機子群為例,其中,包含7 個局部{l1,l2,l3,l4,l5,l6,l7,l8},當(dāng)7 個局部均實現(xiàn)無沖突目標(biāo)分配時,虛線中的所有無人機將得到一個無沖突的目標(biāo)分配方案.例如,局部l2={v1,v2,v3,v4,v5}和l5={v2,v4,v5,v7,v8}擁有共同的無人機{v2,v4,v5},當(dāng)局部l2和l5分別實現(xiàn)無沖突目標(biāo)分配時,無人機{v2,v4,v5}的目標(biāo)分配在局部l2和l5中均無沖突,從而使得局部l2和l5之間的目標(biāo)分配無沖突.當(dāng)所有局部內(nèi)均實現(xiàn)無沖突的目標(biāo)分配時,即可得到全局無沖突的目標(biāo)分配方案.

圖3 分布式協(xié)商目標(biāo)分配方案架構(gòu)Fig.3 Target allocation framework under distributed negotiation

因此,本文主要針對局部li內(nèi)無人機之間的分布式協(xié)商目標(biāo)分配算法進行設(shè)計,以保證通信連通性的同時實現(xiàn)目標(biāo)優(yōu)化分配覆蓋,具體算法設(shè)計將在下一節(jié)中詳細介紹.

2.4 分布式協(xié)商目標(biāo)分配與連通保持算法設(shè)計

如圖4所示,算法以無人機對地面目標(biāo)的探測信息作為輸入.為了解決目標(biāo)類型不同以及無人機覆蓋能力有限問題,基于無人機的覆蓋能力對原始目標(biāo)M進行分組并得到新目標(biāo).接著在拍賣階段對新目標(biāo)進行收益評估,并得到目標(biāo)中標(biāo)列表Mi.在目標(biāo)協(xié)商一致及連通保持階段,無人機分別選取中標(biāo)列表中對自身收益最大的目標(biāo),并對產(chǎn)生沖突的目標(biāo)進行協(xié)商分配,接著對目標(biāo)所在位置進行通信連通性判斷,以確定無人機前往覆蓋目標(biāo)的可行性.當(dāng)局部li中無人機i 分別與其他無人機完成協(xié)商后,局部li即可得到無沖突的目標(biāo)優(yōu)化分配方案.

圖4 分布式局部協(xié)商目標(biāo)分配與連通保持算法流程Fig.4 Algorithm flow of target allocation and connectivity preservation for distributed local negotiation

2.4.1 目標(biāo)分組

由于無人機同時只能覆蓋一類目標(biāo)且覆蓋數(shù)量有限,當(dāng)同一柵格中存在較多目標(biāo)且類型不同時,無人機對柵格中的目標(biāo)收益評估將成為一個較為復(fù)雜的過程.為了簡化這一過程,定義無人機i 在探測并更新目標(biāo)信息過程中需維護的目標(biāo)集合,其中,為無人機對目標(biāo)分類并分組處理得到的新目標(biāo)子集,同時目標(biāo)子集hk中僅包含一類目標(biāo),且每個子集所包含目標(biāo)數(shù)量不超過無人機的覆蓋能力c.由于無人機的位置坐標(biāo)為六邊形柵格中心,且無人機正好可以完全覆蓋所在六邊形柵格區(qū)域,因此,將目標(biāo)子集hk所在的六邊形柵格中心位置坐標(biāo)視為目標(biāo)子集hk的位置坐標(biāo),以降低無人機對目標(biāo)收益估計的復(fù)雜度.

以圖5為例對目標(biāo)分組過程作進一步說明.圖中正六邊形內(nèi)的目標(biāo)集合為,假設(shè)無人機的覆蓋能力c=3,通過以下規(guī)則對目標(biāo)進行分類并分組：

圖5 目標(biāo)分組示意圖Fig.5 Schematic representation of grouping targets

2）在同一類型目標(biāo)集合中,依次選取距離柵格中心最近的目標(biāo),每c 個目標(biāo)分組為一個目標(biāo)子集hk（剩余不足c 個的分為一組）,得到新的目標(biāo)集合,其中我方目標(biāo)子集、,敵方目標(biāo)子集.

根據(jù)以上分組規(guī)則,每架無人機對探測到柵格中的目標(biāo)進行分組得到目標(biāo)集合,各目標(biāo)價值向量為,其中,對應(yīng)目標(biāo)子集hk的價值,根據(jù)目標(biāo)類型權(quán)重以及hk所含有目標(biāo)數(shù)量wk的不同,得到sk的值為：

通過對目標(biāo)的分組,將多個目標(biāo)分配給一架無人機的問題轉(zhuǎn)化為單個目標(biāo)子集分配給一架無人機的問題,簡化了無人機分布式協(xié)商目標(biāo)分配的復(fù)雜度.為了方便,文中所提到的目標(biāo)均表示分組后的目標(biāo)子集hk,即以目標(biāo)子集hk視為目標(biāo)進行分配.

2.4.2 目標(biāo)分組如圖4中,在目標(biāo)拍賣階段,無人機i 與局部li內(nèi)的其余無人機j 共享目標(biāo)并得到目標(biāo)集合.無人機在獲得目標(biāo)信息后,分別對目標(biāo)進行收益評估并投標(biāo),將無人機i 與目標(biāo)hk的距離dik以及目標(biāo)hk的價值sk作為無人機當(dāng)前的收益評估因子,并定義收益函數(shù)為：

式中,yik為目標(biāo)hk對無人機i 的收益大小,并以收益大小作為對目標(biāo)的出價進行投標(biāo).其中,1/Dik表示目標(biāo)k 對無人機i 的距離優(yōu)勢,當(dāng)目標(biāo)與無人機同時存在于一個六邊形柵格中時,目標(biāo)已被覆蓋,此時距離優(yōu)勢將保持最大值；當(dāng)目標(biāo)存在于其他六邊形柵格時,無人機距離目標(biāo)越近則距離優(yōu)勢越大,對應(yīng)收益也隨之增大.定義每架無人機在整個分配過程中儲存和更新的兩個列表為zi和wi,其中,是無人機i 的覆蓋目標(biāo)列表,表示無人機i 分配到覆蓋目標(biāo)hk,否則zik=0；是無人機i 維護的目標(biāo)中標(biāo)列表,假設(shè)無人機當(dāng)前執(zhí)行任務(wù)的收益為,當(dāng)覆蓋目標(biāo)hk帶來的收益yik大于時,視目標(biāo)hk中標(biāo)并設(shè)置wik=1,反之wik=0.注意,中標(biāo)的目標(biāo)被放入中標(biāo)列表時,列表將以收益從大到小進行排列更新,以便在協(xié)商過程中快速分配目標(biāo).

2.4.3 協(xié)商一致及連通保持

在這一階段,無人機首先從自身中標(biāo)列表中選擇收益最大的目標(biāo),再進行下一步的協(xié)商以及連通性判定,無人機僅當(dāng)分配到不破壞連通性的目標(biāo)時,才可執(zhí)行覆蓋目標(biāo)任務(wù).

1）協(xié)商一致

各無人機首先采用貪婪策略選擇自身中標(biāo)列表中收益最大的目標(biāo),將其定義為自身的優(yōu)勢目標(biāo),如圖4中,算法在協(xié)商一致階段的迭代中,無人機i 從鄰居通信信息中獲取到所有鄰居的優(yōu)勢目標(biāo),若與自身的優(yōu)勢目標(biāo)不相同,則目標(biāo)分配無沖突,無人機i可獲得自身的優(yōu)勢目標(biāo),即zik=1；相反,若與鄰居優(yōu)勢目標(biāo)相同,則目標(biāo)分配發(fā)生沖突,此時,若其他無人機有更高的收益,無人機i 將選擇放棄當(dāng)前優(yōu)勢目標(biāo)并將該目標(biāo)從中標(biāo)列表中清除,再從中標(biāo)列表中選擇一個收益最大的目標(biāo)作為優(yōu)勢目標(biāo).確定優(yōu)勢目標(biāo)后,無人機針對優(yōu)勢目標(biāo)所在位置進行下一步的連通性判定工作.

2）通信連通保持

文中無人機i 已知局部li中其余無人機的位置信息,這為無人機i 提供了所使用的局部網(wǎng)絡(luò)結(jié)構(gòu).無人機i 通過對局部圖的連通性判斷,進而對連通性具有破壞性的動作進行約束,從而實現(xiàn)網(wǎng)絡(luò)的連通保持.

以無人機i 為例,具體連通保持的算法流程設(shè)計如圖6所示.

圖6 連通保持算法流程圖Fig.6 Flowchart of connectivity preservation algorithm

由算法設(shè)計可知,無人機i 在協(xié)商一致階段確定優(yōu)勢目標(biāo)后,以優(yōu)勢目標(biāo)所在位置坐標(biāo)為自身下一步的移動位置,并以此坐標(biāo)結(jié)合所有鄰居的位置坐標(biāo)創(chuàng)建拓撲圖Gi,求解其拉普拉斯矩陣L 的第二小特征值,進而預(yù)估覆蓋該目標(biāo)后通信網(wǎng)絡(luò)的連通性.若＞0,則表示無人機i 前往并覆蓋優(yōu)勢目標(biāo)的過程中均可保持通信連通,可以對優(yōu)勢目標(biāo)執(zhí)行覆蓋任務(wù),從而將該目標(biāo)分配給無人機i,即zik=1；反之,若=0,則表示無人機i 移動后將不能保持通信連通.為了使無人機盡可能覆蓋到更多目標(biāo),本文加入了連通支援機制,因此,無人機i 在判定通信不連通后向局部li內(nèi)其他無覆蓋目標(biāo)的無人機發(fā)出連通支援請求.

收到連通支援請求的無人機j 以發(fā)出支援請求的無人機i 的位置為目標(biāo)位置,通過連通保持算法對拓撲圖Gj的連通性進行判定,若圖的拉普拉斯矩陣對應(yīng)第二小特征值＞0 時,無人機j 可保持通信連通的條件下給無人機i 提供連通支援.獲得連通支援后,無人機i 將再次對優(yōu)勢目標(biāo)進行連通性判定,若能實現(xiàn)連通,則無人機i 將獲得優(yōu)勢目標(biāo)并進行覆蓋.如果仍不能保持連通,無人機i 將放棄當(dāng)前優(yōu)勢目標(biāo),再次從中標(biāo)列表中選擇新的優(yōu)勢目標(biāo)并進行通信連通性判定,循環(huán)迭代直到獲得可覆蓋目標(biāo)或者所有目標(biāo)均不可前往覆蓋為止.最終沒有被分配到目標(biāo)的無人機i 將作為中繼無人機執(zhí)行通信連通任務(wù),以保持通信網(wǎng)絡(luò)連通.

通過以上協(xié)商過程,即可實現(xiàn)局部內(nèi)的無沖突目標(biāo)優(yōu)化分配和連通保持.在分布式控制下,各個局部以異步方式進行協(xié)商分配,從而實現(xiàn)無沖突的全局目標(biāo)優(yōu)化覆蓋和通信連通保持.

3 仿真與結(jié)果分析

本節(jié)從不同角度對算法的有效性與通用性進行仿真驗證.設(shè)置一定數(shù)量的無人機,分別在不同目標(biāo)數(shù)量、不同目標(biāo)移動方式、無人機不同覆蓋能力以及兩類目標(biāo)不同價值權(quán)重等多種場景下進行實驗.每類場景分別以不同隨機種子進行3 次實驗,每次實驗進行100 步,并將3 次實驗得到的目標(biāo)覆蓋率取平均值作為當(dāng)前場景下的目標(biāo)覆蓋率.選取當(dāng)前場景所有實驗過程中無人機通信網(wǎng)絡(luò)連接的最小連通度min（）作為全局連通性的評判標(biāo)準,min（）＞0 表明實驗所進行的每一步均實現(xiàn)了全局連通.由此,實驗采用無人機群對目標(biāo)的覆蓋率以及最小連通度min（）作為指標(biāo),來驗證算法的有效性.

3.1 實驗環(huán)境設(shè)置

考慮在10×10 平方單位的二維環(huán)境中,隨機生成M 個動態(tài)目標(biāo),其中,有m 個我方目標(biāo)和m*個敵方目標(biāo),相應(yīng)目標(biāo)類型的價值權(quán)重為α、β.實驗中可用的無人機數(shù)量設(shè)為n=30 架,所有無人機擁有相同的配置：覆蓋半徑Rr=0.5,探測半徑Rd=1.0,最大通信半徑Rc=2.0,覆蓋能力為c 個目標(biāo).在每個時間步長中,目標(biāo)移動速度為0.05.在每次實驗的初始時刻,無人機群的初始通信網(wǎng)絡(luò)被設(shè)置為連通,并且使得盡可能多的目標(biāo)M 在無人機群的覆蓋范圍內(nèi).

3.2 實驗過程與結(jié)果分析

為驗證無人機群在算法控制下的協(xié)同多目標(biāo)覆蓋性能,設(shè)置在地圖中隨機生成M=25 個目標(biāo),其中,我方目標(biāo)數(shù)量m=12,敵方目標(biāo)數(shù)量m*=13,兩類目標(biāo)價值權(quán)重為α=β,無人機的覆蓋能力c=1.所有目標(biāo)的移動方式為直線運動且逐漸聚集于某一空間范圍中,實驗進行100 步,其中,4 步的目標(biāo)覆蓋情況如圖7所示.

圖7 動態(tài)目標(biāo)覆蓋Fig.7 Dynamic targets coverage

由圖7（a）可知,無人機群在初始狀態(tài)下通信連通且少量目標(biāo)在覆蓋范圍外,在隨后的目標(biāo)移動過程中,需要無人機實時探測獲取目標(biāo)信息,從而進行協(xié)商覆蓋.從圖7中可以直觀地看到,無人機群隨著目標(biāo)的移動而靈活變換通信拓撲網(wǎng)絡(luò),這是由于當(dāng)無人機發(fā)現(xiàn)更高價值目標(biāo)后,可通過連通判斷、發(fā)出連通請求等多種機制,實現(xiàn)多無人機的協(xié)同移動.通過以上分析得知,本文提出的分布式協(xié)商目標(biāo)分配算法可以使無人機群擁有良好的協(xié)同覆蓋性能.

在下一組實驗中,為了驗證算法在不同目標(biāo)優(yōu)先級分配下的有效性,基于目標(biāo)直線移動實驗,設(shè)置兩類目標(biāo)的價值權(quán)重關(guān)系分別為α＞β 和α＜β,并在不同目標(biāo)數(shù)量M 下進行實驗測試,其中,不同類型的目標(biāo)數(shù)量m=m*.實驗得到不同價值權(quán)重下目標(biāo)平均覆蓋率以及實驗中的最小連通度min（）如表1所示.

表1 不同目標(biāo)價值權(quán)重下的覆蓋性能測試Table 1 Coverage performance test under different target value weights

從表1中可以直觀得知,隨著目標(biāo)數(shù)量的增加,算法性能指標(biāo)趨于下降,即目標(biāo)的覆蓋率逐漸降低,這是因為在有限的無人機數(shù)量下,算法為了保持通信網(wǎng)絡(luò)的連通而選擇放棄部分目標(biāo),這同時也說明了算法在通信連通保持方面的有效性.此外,當(dāng)目標(biāo)m*的權(quán)重較大時（α＞β）,無人機對目標(biāo)m*的覆蓋率高于對目標(biāo)m 的覆蓋率,且隨著目標(biāo)數(shù)量的增加,覆蓋率的差距逐漸增大,這是因為目標(biāo)的增加使得無人機有了更多的目標(biāo)選擇,從而分配更大收益的目標(biāo)m*執(zhí)行覆蓋目標(biāo).同理,當(dāng)α＜β 時也有類似的測試效果.上述分析表明,所提出的算法在目標(biāo)具有不同優(yōu)先級的條件下具有較好的覆蓋性能,同時在不同的動態(tài)目標(biāo)數(shù)量場景下具有很好的泛化性能.

最后,設(shè)置了不同的動態(tài)目標(biāo)數(shù)量分別以不同的方式移動,并分別測試無人機在不同的覆蓋能力c=1和c=5 下對目標(biāo)的覆蓋性能,其中,設(shè)置α=β,目標(biāo)的移動方式為直線移動以及隨機移動兩種,測試結(jié)果如表2所示.

由表2可知,對于無人機的覆蓋能力c=1 而言,隨著目標(biāo)數(shù)量的增加,目標(biāo)的覆蓋率相對于覆蓋能力c=5 時的差距逐漸增加,這是因為覆蓋能力更大時,相同數(shù)量的無人機可以覆蓋更多的目標(biāo),從而使得在面臨較大數(shù)量的目標(biāo)時,無人機覆蓋能力越大則總覆蓋率越高.此外,當(dāng)目標(biāo)數(shù)量較少時,將有足夠的無人機前往覆蓋目標(biāo),即有多個目標(biāo)處于同一柵格中時,算法將分配多架無人機前往同一柵格覆蓋不同目標(biāo),因此,在目標(biāo)數(shù)量較少的情況下,即使單架無人機覆蓋能力較低,也將有較好的覆蓋性能.

表2 不同覆蓋能力下的覆蓋性能測試Table 2 Coverage performance test under different coverage capabilities

4 結(jié)論

本文提出了一種基于分布式協(xié)商的多無人機目標(biāo)覆蓋與連通保持算法,以解決多無人機動態(tài)多目標(biāo)覆蓋與通信連通保持問題.實驗結(jié)果表明,本文提出的分布式協(xié)商算法,可以綜合考慮無人機的覆蓋能力、目標(biāo)類型、目標(biāo)覆蓋優(yōu)先級以及通信連通保持多種因素,使得多無人機可以在分布式控制下,在動態(tài)環(huán)境中實現(xiàn)目標(biāo)優(yōu)化覆蓋和通信連通保持.