基于混沌灰狼優化的多無人機協同航路規劃

吳坤，池沛，2，王英勛，2，侯琳

1.北京航空航天大學，北京 100191

2.北京航空航天大學飛行器控制一體化技術國防科技重點實驗室，北京 100191

3.航空工業西安飛行自動控制研究所飛行器控制一體化技術國防科技重點實驗室，陜西 西安 710065

航路規劃(path planning)是根據任務需求規劃出滿足約束條件的飛行航路，是任務規劃的關鍵技術之一[1]。航路規劃的精度與速度能夠直接對任務規劃的效果產生影響。航路規劃系統基本框架由環境信息、航路規劃目標、機體物理約束以及航路規劃器組成。根據平臺規模，無人機航路規劃分為單機航路規劃、多機航路規劃和有人/無人協同航路規劃[2-3]；根據環境信息，可分為確定環境與突發威脅環境下的航路規劃；根據實現功能可劃分為靜態航路規劃與動態航路規劃，其中前者為離線預規劃，后者為在線實時規劃。

受計算能力的約束，航路離線預規劃問題由于不受計算時間約束，其更關注在可預測的已知任務環境下，如何得到評價最優的航路結果。而在線實時規劃則是在已有規劃結果的基礎上，針對突發意外情況進行重新規劃，對規劃時間要求較高。

航路規劃算法根據計算方法可以歸納為最優化方法與啟發式搜索算法(HSA)。常用的最優化算法包括枚舉法(EM)、牛頓法(NM)、梯度下降法(GD)、數學規劃(MP)以及動態規劃(DP)方法。

最優化方法在空間和時間上具有很強的復雜度，當規劃范圍增大、環境變復雜時，其求解時間與求解難度也隨之急劇增加。而啟發式算法是根據直觀經驗構造的一種搜索算法，在可接受的時間和空間復雜度下，能夠得到待優化問題的一個可行的近似最優解。啟發式搜索算法可進一步分為確定型搜索算法與隨機型搜索算法兩類。

通常確定型航路規劃算法首先對規劃區域進行柵格化處理，然后利用圖論在地形網格的基礎上搜索從起點到目標點的最短路徑。確定性方法主要包括Dijkstra 算法、Floyd 算法[4]、A*算法[5-6]、人工勢場法(APF)[7]以及Ⅴoronoi圖法[8-9]等。隨機型搜索方法通過在求解空間中進行隨機采樣，并按照一定的搜索規則尋找可行的較優解。典型的隨機型搜索方法有粒子群算法[10]、蟻群算法[11]、快速擴展隨機樹(RRT)算法[12]、人工神經網絡(ANN)[13]、禁忌算法(TS)[14]以及強化學習(RL)[15]等算法。

多無人機協同航路規劃可以同時為多個無人機規劃出多條可行航路，使每架無人機能夠沿不同的航路飛行。這樣生成的航路盡管對每架無人機來說不一定是最優的，但對整個多無人機系統來說是最優或次優的。參考文獻[16]對于多無人機對地面區域的最小時間覆蓋問題，首先采用K均值聚類對偵察區域進行劃分，然后采用并行GA算法對每個簇中的航路規劃問題進行計算。參考文獻[17]提出一種分解策略，將多無人機協同航路規劃問題分為三層框架結構，第一層采用Dubins為每架無人機規劃可飛航路；第二層對多機航路的空間位置進行調整，生成避障與防撞航路；第三層對每條航路的長度進行調整，使得所有的航路長度近似相等，以實現同時到達的時間協同目的。參考文獻[18]提出了三階段航路預測算法(TPP)算法，首先利用A*算法對任務航路進行估計，然后根據預估結果為每架無人機分配代價最優的航路結果，最后利用三次B 樣條差值算法實現可飛路徑的規劃。

多無人在協同執行任務過程中，要求多無人機應保持更加嚴格的占位和和攻擊方向。本文以有人/無人協同執行多方向飽和攻擊任務為研究背景，有人機擔任主要攻擊決策者，多無人機根據任務約束規劃出滿足要求的可行飛行航路。首先針對飽和攻擊任務特點進行分析，給出了面向任務需求的航路評價指標；其次針對任務的時空約束提出了基于幾何規劃的航路點擴展策略；最后利用改進的灰狼優化算法對離線航路規劃問題進行求解，得到滿足要求的規劃結果。

1 面向飽和攻擊任務的問題描述

1.1 航路規劃問題描述

當多無人機在協同執行任務過程中，在滿足任務約束的同時，每架無人機不僅需要具有自動規避威脅和障礙物的能力，還應當具有與團隊內其他成員的防撞能力。而多無人機協同航路規劃技術則是解決這一問題的有效途徑，它是指航路規劃層根據戰場的環境信息，以任務需求為導向，綜合考慮無人機的機動性能、燃油消耗等約束條件，為每架無人機設計出一條不僅能夠滿足團隊間任務協同需求，還能夠使團隊整體生存能力達到最大的可飛的航路[19]。

通常無人機的航路是指由一組離散點列組成的集合，即無人機U(i)(i= 1,…,n)的航路可以表示為

1.2 飽和攻擊任務描述

當使用無人機對敵方目標進行打擊時，通常由于目標強度的限制以及單架無人機的性能約束，如果采用一對一的作戰模式不能形成對目標的有效打擊。所以需要采用飽和攻擊(SA)的作戰策略對目標進行打擊，即利用多架無人機對同一目標進行多方向多批次的攻擊模式，從而實現一擊必毀的作戰效果。根據到達攻擊位置的時間要求與空間要求，可將飽和攻擊任務分為兩種，即分批次攻擊任務(BAAT)與多方向攻擊任務(MDAT)。其中BAAT是指多架無人機在一個規定的時間間隔ΔTa內陸續到達攻擊位置的貫序到達問題；而MDAT 則要求多架無人機在同一時刻從多個攻擊方向對目標實施打擊，MDAT即為同時到達問題。所以多無人機執行SA 任務的航路規劃方法的關鍵問題在于如何將SA 任務中的時間與空間約束轉換到單條航路規劃問題中。

1.3 航路評價指標

由于航路規劃的目標為在滿足無人機物理性能約束與飛行任務約束的前提下生成能夠對威脅進行規避的飛行路徑。如圖2 所示，可將無人機航路評價指標分為戰術生存性、飛行約束性以及任務有效性三類。

1.3.1 戰術生存性

戰術生存性是指無人機對敵方威脅進行規避的能力。一般能夠對無人機的飛行安全產生影響的威脅源包括：探測性威脅(如雷達)、殺傷性威脅(如地空導彈或高炮等)以及障礙物或禁飛區威脅。因為威脅程度主要與距離有關，所以在無人機航路規劃問題研究中，通常將威脅區域擬合為具有威脅半徑與威脅等級的圓形或矩形區域。

假設在規劃空間內任意一點位置為pi(x′,y′)，則威脅源Threatj為探測性威脅時對pi的威脅程度可以表示為

式中，Rminj與Rmaxj分別為殺傷性武器的攻擊近界與遠界；wmax為威脅源的威脅程度。

在執行任務過程中，運行航線穿過威脅區域，但禁止飛過障礙物與禁飛區，所以障礙物與禁飛區的威脅值可以表示為

1.3.2 飛行約束性

飛行約束性是指規劃的航路結果應滿足無人機的物理約束，主要包括飛行穩定性以及航程約束兩部分。為了使控制系統能夠更加容易實現對規劃航線的跟蹤以及提高飛行狀態的穩定性，通常需要對航路規劃的航點數量、轉彎角度以及相鄰航點間的距離進行約束。因為無人機在導航點處進行轉彎飛行，所以需要對規劃的航點數量進行限制即應滿足m(i)≤mmax。

1.3.3 任務有效性

式中，Ψ0為無人機的初始駛出方向；Δψ為駛出方向范圍限制。

式中，Tqs與Tqt分別為多無人機起始時間間隔與到達時間間隔。當Tqs= 0 且Tqt= 0 時的飽和攻擊任務即為MDAT，否則表示BAAT。ΔTS與ΔTE表示時間間隔誤差，即無人機從起飛到到達目標之間的時間誤差應在區間[0,ΔTS+ ΔTE]內。

假設每架無人機以vi勻速飛行，據此可將飽和攻擊任務中的同時到達問題轉換為航程問題，當預期的到達時間為TM時，則每架無人機的總航程Si應滿足

式中，ΔSM=(ΔTS+ ΔTE)vi為航程允許的誤差范圍，各無人機可通過在飛行速度微調實現總航程一致的目的。

多無人機協同作戰過程中，除需要對時間進行約束外，還應考慮空間中防撞問題。因為在同一規劃空間內，隨著無人機數量的增多，無人機間的航路容易出現時空重疊的現象，即出現碰撞現象。為了避免這一現象的發生，規劃的航路在瞬時位置上應具有一定的安全間隔，即?i,j∈{1,…,n}ijs

式中，pi(t)表示Ui在t時刻的位置；ds為無人機間的安全距離。

1.3.4 被控對象

多無人機協同航路規劃中，被控對象特性建模比較關鍵，決定了算法性能的優劣，本文假設無人機有一個可靠的飛行控制系統，該系統有效地控制空氣動力表面，以精確跟蹤速度和轉彎率指令，無人機的運動學方程為[20]

式中，v和ψ分別為無人機的速度和航向，u和ω分別為加速度和航向角速度。

2 基于混沌灰狼優化算法的協同規劃方法

2.1 混沌灰狼優化算法

近年來，引入自然進化思想的元啟發式算法，因其遵循“優勝劣汰”原則通過選擇和變異來實現對問題的尋優過程，特別適合解決較大規模的優化問題。由于元啟發式算法需要通過大量的迭代計算對問題進行求解，所以其不適用于航路的在線規劃。但對于計算時間要求不高但更注重規劃結果最優性的離線規劃問題，采用元啟發式算法能夠獲得更好的規劃結果。

2.1.1 灰狼優化算法

灰狼優化(GWO)算法是Mirjalili等于2014年提出的一種元啟發式優化算法[21]，通過模仿自然界中灰狼群的等級制度與捕食策略以迭代計算的方式實現對獵物（最優值)的搜索。種群中灰狼個體的位置更新滿足如下公式11×D時，表示灰狼個體向獵物位置（當前全局最優解）進行移動。而Ai表示GWO 算法對獵物的最優位置進行探索。因為a從2線性遞減至0，所以隨機數∈[-a,a]的取值范圍也逐漸減少，當算法迭代到一定程度時，個體只能在獵物周圍小范圍內進行移動。當迭代次數t=tmax，a=0時，則有Xi(t+1)=Ai，即實現整個算法對最優解的收斂。

GWO 算法通過式(11)實現了對獵物位置的探索與包圍。然而在實際過程中獵物的位置是未知的，所以根據狼群中的等級制度，將當前適應度最優的前三個灰狼個體稱為首領狼，分別用α、β與δ進行表示，剩余的灰狼個體稱為ω。在GWO 算法中，α、β與δ引領整個狼群向獵物位置進行靠近。將首領狼的位置Xi,i=α,β,δ當成獵物的位置代入式(11)中，則可得到

2.1.2 混沌算子

在使用群智能算法對優化問題進行求解的過程中，首先隨機生成一組初始解，并選取其中適應度最小的解作為當前狀態的目標解。然后種群中的其他個體通過一定的機制與策略不斷向此目標解靠近。同時個體的運動方向還會發生隨機偏移以實現更優解的搜索。最后在每次迭代過程中更新適應度最小解為目標解，當達到最大迭代次數后認為目標解即尋優問題的最優解。

盡管GWO算法在收斂性、全局搜索性等方面優于其他優化方法，但仍然存在易陷入局部最優解和收斂速度慢等缺點[22]。所以本節針對此問題對GWO算法進行改進，通過引入混沌搜索策略以增加算法在解空間中的遍歷性，從而提高整個算法的全局尋優能力與收斂速度。

混沌優化算法(COA)是指受混沌現象啟發的一種全局性優化算法，其中混沌現象是指無固定周期的循環行為?；煦鐑灮惴ň哂须S機性、遍歷性以及對初始條件敏感等特點。

本文從算法參數與搜索機制兩方面對GWO 算法進行改進，提出了基于COA的混沌灰狼優化(CGWO)算法，以提高原算法的全局尋優能力與尋優速度。如式(13)所示，GWO 算法主要利用參數a實現了對最優解的全局搜索與局部開發能力。根據迭代次數的增加，參數a從2線性遞減至0。如圖4所示，當a=2時表示算法前期具有較強的全局尋優能力，隨著a逐漸減少算法搜索精確解的能力逐漸加強。在算法初期即搜索到最優解附近時，利用此機制能夠較快地收斂到最優解。但在初期沒有搜索到最優解時，容易陷入局部最優解。所以本節將GWO算法的線性遞減操作改為混沌搜索，使得整個算法能夠一直具有全局搜索能力。參考文獻[23]已經證明采用混沌變量能夠跟線性遞減變量一樣使算法收斂到最優解，同時具有更快收斂速度。

因為初始值能夠明顯地影響群智能算法的收斂速度，所以可以利用混沌變量的遍歷性增加算法初期的尋優能力。假設灰狼種群的個體數量為Np，然后根據混沌映射可以得到2 ×Np組解，并對所得解的適應度進行排列，為了防止陷入局部最優解，所以選取排序后2 ×Np組解中的奇數項作為CGWO算法的初始解。

因為粒子群等優化算法是將當前群體中的最優解看作全局最優進行尋優的，而GWO則考慮了群體間的交流，由前三個最優解共同決定的最優解的位置，當并沒有考慮個體的歷史最優解。所以為了增加算法的全局搜索能力，引入粒子群算法中個體最優位置概念ω(b)i,i= 1,…,Np知道個體的尋優，則在式(14)的基礎上添加

在式(15)中灰狼個體的位置更新公式為X(i)(t),i=1,2,3的平均值。為了強化首領狼的領導作用，則根據適應度值確定權重系數得到灰狼個體的位置更新公式為

為了進一步加強算法的全局尋優能力，采用混沌搜索策略對式(18)的結果進一步搜索，但因為增加全局搜索能力勢必會降低算法的收斂速度。為了使算法能夠朝著最優解的方向發展，所以引入貪婪策略：在一定概率基礎上只接受比當前適應度更好的結果。所以可以得到基于貪婪策略混沌搜索方法為：

（1）將Xi(t+ 1)映射到(0,1)區間。假設Xmin與Xmax為解空間的搜索范圍，則可得映射函數為

（2）設迭代次數為Cmax，根據混沌映射進行迭代計算產生一組混沌變量?(i),i= 1,…,Cmax，并通過逆映射將混沌變量轉換至解空間，得到混沌解序列

式中，r3為區間[0,1]中的隨機數。

2.2 基于CGWO的離線航路規劃方法

航路的離線規劃問題是指無人機在實際飛行前，根據任務需求預先在已知的規劃空間中尋找一組滿足航路評價指標的從起始點到目標點的離散點列。相比于在線規劃問題，航路的離線規劃主要有如下特點：

（1）威脅環境透明。在離線規劃過程中，認為規劃范圍確定且其中的地形信息明確；同時假設敵方威脅源的位置分布、類型種類、威脅范圍以及威脅等級等因素已知。

（2）威脅源慢變化。對于運動的威脅目標或任務目標，通常假設其運動規律已知或是將其運動過程的中不確定因素通過概率的形式進行描述。

（3）計算時間充足，規劃算法所消耗的時間不是首要考慮因素，即離線規劃是通過大量的計算時間與計算量換取高質量的規劃結果。

（4）適用場景充分?；跉v史案例以及場景假設，離線規劃會對各種可能的情況進行充分考慮，使得規劃結果具有很強的適應性。從而不僅減少了實際規劃過程的不確定性，還有效地增加了任務的完成概率。

2.2.1 基于CGWO的單機航路規劃方法

所以基于CGWO 算法的單機航路規劃代價函數可以表示為

式中，wi為代價的權重，且有w1+w2+w3= 1。

2.2.2 基于幾何規劃的航路擴展法方法

執行多方向飽和攻擊任務的關鍵是多無人機能夠以預設的攻擊方向進入目標區域，且從起始點到目標點間的航程相等。其中攻擊方向是指無人機經過最后一個航點轉向后的飛行方向，對于給定攻擊目標的進入角的情況，如果按照從起始點開始搜索的方法，則預定的攻擊方向為一個全局限制條件，明顯增加了問題的復雜度。本節采用逆向航路節點擴展策略：從目標點出發以預設進入角方向進行逆向搜索，根據機體約束條件，尋找一條從目標點到起始點的滿足任務需求的飛行航路。假設多方向飽和攻擊任務的協同航程SM已經給定，則可根據橢圓第一定義建立基于幾何規劃的逆向節點搜索策略。

2.2.3 多機協同航路規劃策略

在基于幾何規劃的航點擴展過程中，已將任務要求的協同航程與目標進入角作為規劃條件進行考慮，但還需要考慮無人機間的防撞。多機間的防撞航路規劃策略為：

首先規劃出某架無人機的代價最優的航路LineA，然后將此規劃結果作為約束條件對另一架無人機的航路進行規劃，得到與LineA不相撞的航線LineB，最后以此類推得到滿足防撞要求的n條協同航路。

式(10)給出了無人機航路間的安全間隔限制，但航路間的間隔過遠會影響整體航路的協同性能，無人機航路應滿足協同間隔

式中，?i,j∈{1,…,n}。

如圖6 所示，通過引入雙曲正切函數可以將無人機間的間隔限制約束條件映射到[0,1]間[34]，令Δd表示緩存距離且有0 ＜Δd＜＜ds，則有

所以由式(23)、式(25)與式(35)可得多無人機協同航路的評價函數為

式中：wa+wb= 1為代價權重。

區別于單機航路規劃，采用CGWO算法對多機協同航路規劃問題求解的變量為輔助橢圓的隨機搜索方向χ(i)j與擴展比例λ(i)j，其中i={1,…,n}表示無人機序號，j∈[1,m]為規劃的航點序號。基于幾何規劃與CGWO 算法的多無人機協同航路規劃流程如圖7所示。

3 仿真分析與驗證

3.1 混沌算子選取

利用混沌映射的遍歷性以及與對初值的敏感性，本文所提出的混沌灰狼優化(CGWO)算法通過引入混沌映射以提高原算法的全局尋優能力。典型的混沌映射總共有12種，見表1，而不同的混沌映射將對原算法性能具有不同的改進程度。如圖8所示，當初始值為x0=0.58，最大迭代次數為tmax= 100時，不同的混沌映射具有不同變化規律。根據結果可得，由于混沌映射的非周期性，使得映射結果具有較大的離散性。但不同的映射具有不同的離散程度。所以為了實現對原算法更好的改進，本節在同一仿真環境下采用不同的混沌映射，通過統計結果確定CGWO算法中所使用的混沌映射。

表1 典型的混沌映射Table 1 Typical chaotic mapping

假設CGWO 算法的種群數量Np= 30，最大迭代次數tmax= 200，維度D= 5。對于同一場景的單無人機航路規劃問題，算法初始化以及變量a分別采用不同的混沌映射進行200 次運算，表2 給出了規劃結果的最大值、最小值以及平均值如圖9與圖10分別給出了統計結果的盒圖。

表2 不同混沌映射對航路規劃結果的影響Table 2 Influence of different chaotic maps on path planning results

混沌初始化映射選?。焊鶕y計結果可得，當CGWO算 法 采 用Piecewise 映 射(M9)、Chebyshev 映 射(M10)以 及Ⅰntermittency 映射(M12)時得到的航路規劃結果最優。將三種映射做進一步比較可得，CGWO 算法采用Ⅰntermittency映射能夠得到比較滿意的結果，且實現簡單。

混沌變量a選?。河杀? 可得，采用Ⅰntermittency 映射(M12)、Sinusoidal 映射(M6)與Gauss 映射(M3)時能夠得到較優的規劃結果。如圖10所示，M6存在較大的離散性，另外，因為M12對混沌初始化具有較為明顯的優化結果，所以混沌變量a選擇M12作為混沌算子。同時為了便于計算，式(21)同樣采用M12作為混沌算子。

表3 不同混沌變量a對航路規劃結果的影響Table 3 Influence of different chaotic variables a on path planning results

3.2 算法的比較以及有效性驗證

為了驗證本節所提出的算法的有效性，采用粒子群算法、灰狼優化算法與混沌灰狼優化對單無人機航路規劃問題進行求解，可以得到如圖11所示航路規劃結果。其中種群數量Np= 50，最大迭代次數tmax= 150，維度D= 5，規劃空間內威脅分布的情況見表4。本文在設計代價函數時進行了無量綱（量綱一）處理，所以仿真分析不考慮實際單位。

表4 規劃空間中威脅的分別情況Table 4 Threats in the planning space

將式(25)中航路代價的權重系數設為wi= 1/3,(i=1,2,3)，則航路代價隨迭代次數的變化情況如圖12所示。通過對比可得，CGWO 算法的初始代價高于其他兩種算法，為了增加在解空間中的遍歷性，CGWO算法選取的初始解為2 ×Np組混沌初始解按序排列后的奇數項，所以存在隨機初始解優于混沌初始解的情況。但是隨著尋優過程的進行，CGWO 算法很快找到了最優解。航路規劃的結果為1.18(CGWO) ＞1.21(GWO) ＞1.35(PSO)。

通過將式(25)中航路的代價權重進行調整可以得到不同規劃目標下的規劃結果。如圖13所示，定義wi(i= 1,2,3)的取值分別為(0.8,0.1,0.1)、(0.1,0.8,0.1)與(0.1,0.1,0.8)時采用CGWO算法可以分別得到航程最優、安全最優以及平滑最優的規劃結果。其中種群數量Np= 30，最大迭代次數tmax= 150，維度D=11。

為了進一步驗證本節所提的CGWO算法的性能，采用隨機生成威脅環境的方式進行仿真試驗。在1000 × 1000的規劃空間內設置10 個威脅源，威脅源的位置、威脅半徑與威脅類型隨機生成。CGWO 算法、GWO 算法與PSO 算法的種群數量為30，維度為D=5，最大迭代次數80，圖14與圖15給出了600次的仿真統計圖，結果證明了CGWO算法在解決單機航路規劃問題上具有明顯優勢。

在每次仿真過程中，三種算法都對同一個威脅環境進行仿真試驗，而在不同的仿真中，由于規劃環境不同，所以不能對仿真結果直接進行對比。假設算法的最優代價值分別為fCGWO、fGWO與fPSO，則采用式(36)所示的歸一化操作，即可得到圖14所示的統計盒圖。CGWO算法的仿真結果明顯優于其他兩種算法，能夠得到代價值更優的規劃結果。

令ΔfˉGWO=fˉCGWO-fˉGWO，ΔfˉPSO=fˉCGWO-fˉPSO，則得到如圖15所示的結果示意圖。在600 次仿真中，可以得到CGWO 算法優于GWO 的情況為74%，優于PSO 的情況為54.8%。ΔfˉGWO與ΔfˉPSO的平均值分別為-0.0129與-0.0466，相應的方差值分別為0.0017、0.0080，即CGWO算法的平均水平優于GWO 與PSO 算法。另外根據仿真結果可得GWO 算法的尋優能力強于PSO算法。

3.3 多機協同規劃結果分析

假設三架無人機U(i)(i= 1,2,3)分別從(10,350)、(0,0)以及(360,30)出發，目標位置為(990,990)。假設目標的進入角分別為μ1=150°,μ2=270°,μ3=390°，最小對準距離l(i)min=100。根據圖7所示的多無人機協同航路規劃流程，采用CGWO 算法對航路規劃問題進行求解，得到的規劃結果如圖16所示。

假設各無人機以相同的速度勻速飛行，則可以得到協同航程為SM= 1755.7。各無人機基于幾何規劃策略構造的航路規劃結果如圖17 所示。圖中五角星表示根據方位角χ(i)j確定的輔助橢圓O(i)j上的點，輔助橢圓根據剩余航程ΔS(i)進行構造。根據式(30)將參數(λ(i)j,χ(i)j)解碼為參考的航路點，即如圖中的符號*所示。

4 結論

本文針對多無人機協同執行飽和攻擊任務，根據橢圓第一定義提出了基于幾何規劃的從目標點出發的逆向航點擴展策略，從而構造出滿足任務攻擊時間與攻擊方位要求的航點序列。將混沌映射引入灰狼優化算法中，提出了基于混沌灰狼優化算法的多無人機協同航路規劃方法。仿真結果表明，提出的CGWO算法能夠根據任務需求生成滿足方位與時間約束的協同航路，同時算法的收斂速度與尋優精度明顯優于其他算法。

由于本文假設無人機為勻速運動，以便將“按時到達”問題轉換為路徑長度對話。但在實際工程應用中并不一定要求全部無人機按相同的速度到達，所以本文接下來的工作針對不同到達速度要求下的“同時到達”問題展開研究，并擴展到三維航路規劃，為實飛驗證提供必要的研究基礎。