王原 邢立寧 陳盈果 趙翔 黃魁華

1．國防科技大學系統(tǒng)工程學院湖南長沙410073

無人機集群(UAV swarm)[1]是由多無人機系統(tǒng)(multi UAV system)發(fā)展而來的一種多無人機協(xié)同模式.該模式為多無人機系統(tǒng)的高階形態(tài).相比于一般的多無人機系統(tǒng),無人機集群呈現規(guī)模大、協(xié)同等級高、協(xié)同過程人工干預少等顯著特征[2].采用無人機集群進行空間信息采集,能夠有效降低任務的執(zhí)行成本,且增加可處理任務的復雜性.

自組織無人機集群(self-organized UAV swarm)構架是無人機集群的一種高階形態(tài).在自組織無人機集群中,無人機個體通過與環(huán)境及其他無人機個體的交互進行自主決策,從而使整個無人機集群在任務執(zhí)行的過程中保持整體性并共同解決復雜任務.因此,自組織無人機集群是一種“集群涌現式智能”[3].

基于虛擬物理規(guī)則(virtual physical law)的自組織無人機集群航跡規(guī)劃方法是一種在現實中具有廣泛應用的方法.該方法首次被提出于文獻[4].該文獻提出了一種基于人工勢力場(artificia potential field APF)的無人機集群航跡規(guī)劃模型.在該模型中,無人機集群中的個體的行動由兩種不同的力決定:來自目標的定向力以及來自可探測范圍內的個體或其他障礙物的斥力.基于虛擬物理規(guī)則的無人機航跡規(guī)劃方法的主要優(yōu)勢有[5]:

1)能夠通過簡單地擴展規(guī)則使無人機集群具有應對復雜多變環(huán)境的能力.

2)無人機的個體行為能夠通過簡單計算獲得.

3)能夠使用通用理論工具對無人機集群的行為進行量化分析.

以此為基礎,該領域研究者針對基于虛擬物理規(guī)則的自組織無人機集群航跡規(guī)劃問題進行了大量的研究.其中,文獻[6] 提出了速度障礙(velocity obstacle,VO)規(guī)則.文獻[7] 將速度障礙規(guī)則進一步擴展為虛擬群組速度障礙(virtual group velocity obstacle,VGVO)規(guī)則.該規(guī)則保證了無人機集群在分散為多個子集群的同時仍能夠較好的完成避障任務.文獻[8]將不同無人機以及物體運動的相對速度納入了虛擬物理規(guī)則系統(tǒng).文獻[9]在上文所述規(guī)則的基礎上提出了一種一般化的無人機集群控制模型,該模型能夠廣泛適用于不同的無人機編隊維持任務并支持自組織無人機集群規(guī)模的動態(tài)擴展.文獻[10]提出了一種集群中存在通訊樞紐的基于Vicesk 模型的無人機集群控制模型,該模型在存在通訊樞紐的無人機集群中能夠獲得更好地運動一致性表現.

為提升控制模型在不同環(huán)境下表現的穩(wěn)定性,一類重要手段是采用自適應可變參數.針對可變參數的自組織無人機集群控制系統(tǒng)最早由文獻[11]提出.該系統(tǒng)由一個包含可變參數的無人機集群控制模型以及用于求解模型參數的進化算法組成.文獻[12] 探討了不同類型的優(yōu)化算法求解無人機集群控制模型參數的效果,并證明了采用粒子群算法比遺傳算法具有更好地優(yōu)化表現.文獻[13]在經典Vicsek 控制模型的基礎上增加了可變參數控制集,用于處理無人機集群的聚合任務.文獻[14] 采用無人機可變參數控制模型解決了分布式無人機集群的聚合任務,該方法在不同規(guī)模的無人機集群環(huán)境下均具有良好表現.文獻[15]提出了一種包含11 個可變參數的無人機集群控制模型.該模型還研究了無人機存在加速度限制條件下的控制模型的優(yōu)化問題.

為解決無人機集群可變參數控制模型在多任務環(huán)境下的控制效能問題,提出了一種基于規(guī)則庫的無人機集群控制模型,并給出基于多目標優(yōu)化方法的無人機集群控制模型參數優(yōu)化方法.最終,設計多個不同的仿真場景證明該模型的有效性.

1 自組織無人機集群控制模型

介紹基于規(guī)則庫的無人機集群控制模型(rule based swarm control Model with tunable parameters,RSCMTP).

1.1 基本假設

針對RSCMTP 模型,存在如下基本假設:

針對無人機個體的假設:

1)集群中不存在領導者角色的無人機,集群中無人機個體的行為完全通過個體與周邊環(huán)境的信息交互自主決定.

2)集群中的個體在任務執(zhí)行的過程中除了目標點位置信息外不需要接收來自指揮控制系統(tǒng)的其他指令.

3)無人機個體有最大速度限制.

4)無人機個體的探測范圍和通訊范圍均有限.

5)無人機間的通訊存在延遲.

針對環(huán)境的假設如下:

1)無人機集群的任務是穿過任務區(qū)域到達指定目標位置,過程中的任務主要涉及避障、隊形保持以及到達中間目標點.

2)無人機集群中的個體不應觸碰任務區(qū)域邊界,飛出任務區(qū)域邊界視為個體死亡.

3)無人機個體不應與障礙物或其他個體發(fā)生碰撞,發(fā)生碰撞則視為個體死亡.

1.2 無人機速度更新規(guī)則

結合環(huán)境假設1 可知,該自組織無人機集群的任務主要包括避障任務和目標定向任務.同時,需要保證無人機集群能夠維持密集隊形.其中,維持密集隊形的主要原因是為了維持自組織無人機集群中個體間通訊的暢通.圖1 展示了維持密集隊形的必要性.

RSCMTP 模型包括3 部分基本控制要素:對目標導航的導航力,避免無人機個體與障礙物碰撞和飛出場地邊界的避障力,以及保證無人機集群編隊隊形的隊形維持力.以上3 個力可通過圖2 表示.

圖2 中,目標位置由無人機集群指揮控制中心輸入,隊形維持力和避障力則通過無人機個體與環(huán)境的交互獲得,具體如圖3所示.

圖2 3 種力的作用Fig.2 Three forces

圖3 中,當無人機個體在R3范圍內探測到存在障礙時,會在可探測到的障礙物表面產生虛擬個體,虛擬個體會向該無人機個體發(fā)出避障力以阻止無人機個體繼續(xù)向該虛擬個體方向移動.當無人機個體探測到其探測范圍R0,R1,R2內存在其他無人機時,該范圍內的無人機分別向當前無人機個體施加斥力、同向力和引力,以上3 種力的合力被稱為隊形維持力.在RSCMTP 模型中,設定R0= 1/3R3,R1= 2/3R3,R2=R3.下面分別對所述的力對應的速度更新規(guī)則進行介紹.

圖3 無人機個體環(huán)境交互原則Fig.3 Detection rules of UAV individual

1.2.1 導航力

導航力是指引導無人機個體向當前目標區(qū)域飛行的力.導航力可通過式(1)描述.

其中,?vti為個體i受到的導航力,pt和pi分別為用向量表示的目標區(qū)域和無人機個體所處的空間位置,rit為目標區(qū)域距離當前無人機的距離.

1.2.2 避障力

避障力是為避免無人機個體和任務區(qū)域邊界或任務區(qū)域內可能存在的障礙物碰撞而產生的力.避障力可通過式(2)描述.

1.2.3 隊形維持力

隊形維持力的主要作用為維持無人機集群的編隊構型.隊形維持力由斥力、同向力和引力3 部分構成.以下分別對這3 種力進行介紹.

1)斥力.斥力是保證無人機個體之間不發(fā)生碰撞的力.斥力可通過式(3)描述.

2)同向力.同向力的作用是維持無人機個體之間運動方向和速度的一致性.同向力通過式(4)描述.

3)引力.引力的作用是維持無人機個體間的距離不超過其探測范圍.引力可通過式(5)描述.

1.2.4 速度更新規(guī)則

通過上述描述,最終可得受到3 種力影響的無人機個體的速度更新規(guī)則如式(6)所示.

其中,vi(t)為個體i在時刻t的速度,?vi(t)為個體i在時刻t受到3 種力的影響產生的速度的增量,?vi(t)可通過式(7)求得.

式(7)中,{a,b,c,d,e} 為5 個可變參數,代表不同力在時刻t對速度增量?vi(t)影響的重要性程度.全部{a,b,c,d,e}5 個參數的取值范圍均為[0,1].

1.3 速度更新規(guī)則系統(tǒng)

在第1.2 節(jié)所述速度更新規(guī)則的基礎上,RSCMTP 模型還包含一個速度更新規(guī)則系統(tǒng).該系統(tǒng)的主要特征是在速度更新規(guī)則的基礎上,通過無人機個體探測到的環(huán)境信息的不同,采用不同的速度更新規(guī)則對無人機的速度進行更新,從而增強了無人機個體的環(huán)境適應能力.式(8)介紹了該規(guī)則系統(tǒng)中的主要規(guī)則.

式(8)中,i為無人機探測范圍內其他無人機的數量,o為無人機探測范圍內障礙物的數量.通過式(8)可得最終的無人機個體速度更新規(guī)則如式(9).

另外需要指出的是,由于無人機個體的速度存在上限,因此,最終的速度更新公式為式(1).

其中,vmax為無人機個體的速度上限.

2 NSGAIII 多目標優(yōu)化算法

為求解式(9)所述的RSCMTP 模型參數,采用基于NSGAIII[16]的多目標優(yōu)化算法.該算法是NSGAII[17]多目標優(yōu)化算法的改進,其在求解多目標優(yōu)化問題時具有比NSGAII 算法更好的種群多樣性表現.以下介紹求解RSCMTP 模型參數的NSGAIII 算法流程.

2.1 編碼

用于求解RSCMTP 模型參數的NSGAIII 算法的染色體采取一維順序編碼,該編碼方式可通過圖4表示.

圖4 編碼Fig.4 Problem encoding

2.2 交叉

NSGAIII 算法中,采用隨機交叉算子進行染色體的交叉,具體是指:NSGAIII 算法隨機選擇父代染色體上最多5 個基因位,并將兩條父代染色體上對應的基因位上的參數進行交換.隨機交叉算子的具體操作如圖5所示.

圖5 隨機交叉算子Fig.5 Random crossover operator

需要額外指出的是,父代染色體的選擇采用輪盤賭算法.

2.3 變異

NSGAIII 算法中,采用隨機變異算子進行染色體的變異操作,具體是指:NSGAIII 算法隨機選擇父代染色體上最多3 個基因位,并在參數范圍[0,1]內對這些基因位進行重新賦值.隨機變異算子的具體操作如圖6所示.

圖6 隨機變異算子Fig.6 Random mutation operator

2.4 選擇

NSGAIII 算法采用基于非支配排序的方式進行下一代種群的選擇.設第t代種群為pot,則若要產生種群pot+1,需遵循如下步驟:

步驟1.對pot中的染色體進行評估,并賦予每個染色體非支配排序值,非支配排序值通過支配該染色體的染色體數量決定.例如,設當前染色體i被pot中的2 個其他染色體支配,則染色體i的非支配排序值為2.

步驟2.按非支配排序值從小到大的順序依次將具有相同非支配排序值的pot中的染色體加入pot+1,直到pot+1中的染色體數量達到或超過種群規(guī)模上限.

步驟3.若pot+1中的染色體超過種群規(guī)模上限則將pot+1中擁擠度較大的染色體移出pot+1,直到pot+1中的染色體數量等于擁擠度的具體計算方式見文獻[18].

染色體質量主要通過以下3 個指標進行評價:

1)死亡率:死亡率用于評價自組織無人機集群中的個體和其他個體,以及環(huán)境中的障礙發(fā)生碰撞或者飛出任務區(qū)域邊界的概率.死亡率可通過式(11)計算.

其中,dr為死亡率,D死亡無人機個體數,S N為無人機集群規(guī)模.

2)任務完成時間.任務完成時間指標用于評價無人機集群中的個體到達目標區(qū)域所需要的時間.任務完成時間可用式(12)計算.

3)聚集指標.聚集指標是指無人機集群維持隊形的能力,該指標通過計算仿真過程中無人機集群中的個體距離集群虛擬中心的距離均值得出.為計算聚集指標,需要采用式(13)計算無人機集群的虛擬中心.

在式(13)的基礎上,通過式(14)計算無人機集群的聚集指標.式(14)中,da為聚集指標.

3 仿真實驗及分析

3.1 仿真實驗設計

仿真實驗中涉及的模型,場景和算法類型如表1所示.

表1 仿真實驗設計Table 1 Simulation experiment design

其中,仿真場景的具體設置如下:

1)任務區(qū)域設定為邊長為500 的正方形區(qū)域.

2)無人機最大速度vmax=5/step.

3)自組織無人機集群規(guī)模被設定為20.

4)無人機間的通訊延遲被設定為1 step.

5)無人機傳感器存在誤差,誤差范圍為(0,1).

6)無人機傳感器的探測范圍取值為(45,5)中的一個隨機數.

7)每個仿真場景的仿真時長上限被設定為200 step.

8)在全部場景中,無人機集群的任務均包括從開始區(qū)域出發(fā)飛向目標區(qū)域.在飛行過程中,無人機個體必須避免與任務場地內存在的障礙和任務區(qū)域邊界或其他無人機個體發(fā)生碰撞.另外,在多目標任務中,無人機集群還需要按順序到達任務區(qū)域內的其他目標點.

全部被測算法中,種群規(guī)模被統(tǒng)一設定為30,算法最大迭代次數被設定為200,變異系數被設定為30%.全部被測算法所使用的交叉算子和變異算子均與NSGAIII 算法相同.所有算法和仿真實驗均運行在一臺使用Intel R○CoreTMi7-6700HQ CPU(4核,2.6 GHz),32 GB 內存的電腦上.

3.2 優(yōu)化算法表現分析

仿真實驗對比了多種不同的多目標優(yōu)化算法在RSCMTP 模型上的優(yōu)化性能表現,主要采用不同算法的均值/最優(yōu)表現分析以及基于超體積(hyper volume,HV)的多目標優(yōu)化能力分析.給出優(yōu)化算法表現分析所采用的測試場景如圖7所示.

圖7 算法效能測試場景Fig.7 Algorithm performance comparison scenarios

算法具體表現如表2、表3所示.

表2 中,“DR”代表死亡率,“TT”代表任務完成時間,“AI”代表聚集指標.從表2 可知,測試的全部3個場景中,NSGAIII 算法均能找到具有最好死亡率、聚集指標和任務完成時間的參數組合.

表2 最優(yōu)/均值表現分析Table 2 Best/average performance analysis

在最優(yōu)/均值分析的基礎上,采用超體積分析方法測試不同算法的多目標優(yōu)化能力.由于本問題的實際最優(yōu)帕累托前沿未知,因此,使用一種基于蒙特- 卡洛方法的超體積分析方法.該程序可從網址https://ww2.mathworks.cn/matlabcentral/file xchange/30785-hypervolume-computation?s_tid=srchtitle_hypervolume4 獲取.超體積分析的參考點下界設定為全部算法在3 個場景內取得的優(yōu)化目標的最優(yōu)值,參考點上界統(tǒng)一設置為{1,1,1}.每次仿真產生的采樣點數量均為500 000,采樣點分布均采用完全隨機分布.為消除采樣方法導致的隨機誤差,每個測試場景均執(zhí)行20 次,并分別記錄各個算法的平均超體積分析表現如表3所示.

表3 算法超體積分析Table 3 Hypervolume analysis

由表3 可知,在測試的全部算法中,NSGAIII 在全部3 個測試場景中均能夠獲得平均和最差情況下的最好超體積分析表現.這表明從平均情況和最壞情況來看,NSGAIII 算法求得的帕累托前沿均能夠覆蓋最大范圍的目標值空間.另外,表3 還展示了測試的全部算法的變異系數.從變異系數指標可得出結論,NSGAIII 算法在全部3 個測試場景中的超體積評價表現均具有較好的穩(wěn)定性.

綜合表2 及表3 的測試結果可得,NSGAIII 算法在測試的全部多目標優(yōu)化算法中具有最好的優(yōu)化效能表現.

3.3 控制模型表現分析

為測試參數調優(yōu)后的RSCMTP 模型效能,設計了兩類不同測試場景:1)多障礙場景；2)混合障礙場景.為決定本測試最終采用的RSCMTP 模型控制參數,對NSGAIII 算法在第3.1 節(jié)的3 個測試場景中求得的參數組合的評價值進行了線性加權聚合,該方法可由式(15)表示.

其中:

其中,分別為當前解的死亡率、任務完成時間、聚集指標.分別為死亡率、任務完成時間、聚集指標在該場景下的最小值.分別為死亡率、任務完成時間、聚集指標在該場景下的最大值.w1,w2,w3為代表各參數指標重要度的系數,在當前實驗中,設w1=w2=w3=1/3,即認為3 個指標的重要度相等.

測試共包含4 種不同的控制模型,各模型表現如圖8、圖9所示.

圖8 多障礙場景Fig.8 Multi obstacles scenario

圖9 混合障礙場景Fig.9 Mixed obstacles scenario

各項評價指標的具體評估結果如表4所示.

表4 控制模型表現分析Table 4 Control model performance analysis

如表4所示,參數調優(yōu)后的RSCMTP 模型在兩個復雜場景下均具有死亡率、聚集性和任務完成速度上的較大優(yōu)勢.需要指出,由于APF 模型在處理復雜障礙時傾向于分裂為多個小規(guī)模群體,因此,表4 中不再給出APF 模型的聚集性指標.顯而易見的,RSCMTP 模型和Reynolds 模型對比APF 模型在聚集性上具有較大優(yōu)勢.

3.4 多目標場景分析

多目標任務場景中,自組織無人機集群需要從開始區(qū)域出發(fā),途徑任務區(qū)域內的多個中間目標點,最終到達目標區(qū)域.在兩個測試場景中,串行任務場景代表無人機集群中的全部無人機需要按順序依次通過多個目標區(qū)域；并行任務場景代表無人機集群需要自主分裂為多個集群,同時通過多個目標點,并最終集體到達目標區(qū)域.需要額外指出的是,由于APF 和APF 兩個模型無法處理多目標問題,因此,僅給出Reynolds 模型和RSCMTP 模型在以下兩類場景內的實驗結果.

3.4.1 串行場景分析

串行任務場景中無人機集群控制模型的對比結果如圖10 至圖12所示.

圖10 串行任務場景1Fig.10 Multi-mission scenario 1

圖12 串行任務場景3Fig.12 Multi-mission scenario 3

從路徑規(guī)劃結果可以看出,對比Reynolds 模型,RSCMTP 模型能夠在任務執(zhí)行的過程中維持更密集的隊形,同時其避障性能更好,且規(guī)劃后總飛行時間消耗也更低.其主要原因是經過參數調優(yōu)后的RSCMTP 模型能夠更加精確的控制不同環(huán)境下無人機個體受到環(huán)境施加的力的影響程度,從而提升模型的控制表現.由于串行任務場景能夠分解為多個3.2 節(jié)中的存在障礙的導航場景,因此,該結果是可以預見的.

3.4.2 并行場景分析

圖11 串行任務場景2Fig.11 Multi-mission scenario 2

并行任務場景中,無人機集群中的個體需要分別前往不同的目標點,因此,無人機個體首先采用式(19)對目標進行評價:

式(19)中,Tar(i)代表當前無人機對第i個并行目標的評分,ri為無人機距該目標的距離,asgi為該無人機觀測到前往目標i方向的無人機數量,maxD為前往該方向的無人機的數量上限.maxD=numUAV/tartotal,其中,numUAV為該個體能夠觀測到的無人機總數,tartotal為并行目標總數.式(19)的基本含義為無人機會選擇前往目前仍能夠選擇的距離其本身最近的目標點.并行場景測試結果如下:

圖13 ?圖15 展示了存在并行任務的場景兩種控制模型的路徑規(guī)劃表現.因在第3.2 節(jié)和第3.3.1節(jié)已經說明了RSCMTP 模型對比Reynolds 模型在任務完成速度和聚集性上具有較大優(yōu)勢,因此,本實驗僅對比在多任務并行條件下RSCMTP 模型的效能表現.從圖13?圖15 可得出結論:并行任務環(huán)境下(特別是圖15所示并行任務數量較多時),Reynolds模型已無法很好地滿足隊形保持和路徑規(guī)劃的要求,而RSCMTP 模型仍能夠很好地維持隊形,且無人機個體能夠在多個并行任務間有效的作出自主選擇.其主要原因是RSCMTP 模型能夠根據任務需要平衡維持隊形所需的力和任務目標對個體施加的引力之間的重要性關系,從而提高了控制模型表現.因此,可以得出結論:RSCMTP 模型對比經典Reynolds 模型,在處理并行任務時具有一定優(yōu)勢.

圖13 并行任務場景1Fig.13 Parallel mission scenario 1

圖15 并行任務場景3Fig.15 Parallel mission scenario 3

圖14 并行任務場景2Fig.14 Parallel mission scenario 2

4 結論

提出了一種基于規(guī)則系統(tǒng)和多目標優(yōu)化方法的自組織無人機集群航跡規(guī)劃方法.該方法以經典的基于虛擬物理規(guī)則的速度更新模型為基礎,在分析自組織無人機集群的典型任務場景的基礎上,建立了針對導航、避障和編隊隊形維持任務的無人機集群控制規(guī)則系統(tǒng).同時,設計相應的多目標優(yōu)化方法求解了該系統(tǒng)中的控制參數.最后,設計多種不同的仿真對比實驗,驗證了該控制模型的有效性.

針對RSCMTP 模型的后續(xù)研究方向包括:1)仿真實驗僅考慮了速度變化,未考慮無人機個體的加速度可能存在的上限.因此,未來的研究中,可以考慮設計針對無人機個體的加速度存在上限的控制模型.2)未考慮目標區(qū)域內的航跡規(guī)劃問題.考慮到無人機集群的任務可能包括區(qū)域覆蓋任務,未來可將目標區(qū)域內的航跡規(guī)劃問題加入控制模型設計的考慮范圍.3)用于求解RSCMTP 模型參數的NSGAIII算法所采用的算子均為通用算子,可以考慮針對該問題特性設計特定的操作算子,改善優(yōu)化算法的計算表現.