基于改進粒子群算法的UAV航跡規劃方法

1212

(1.衛星導航系統與裝備技術國家重點實驗室，石家莊 050081；2.中國電子科技集團公司 第五十四研究所，石家莊 050081)

0 引言

無人機具有低成本、操作簡單、無人員傷亡等特點，正在成為未來信息化的重要基礎平臺。隨著近年來無人機越來越廣泛的應用，無人機集群協同編隊飛行已經成為了當前研究的熱點。無人機集群航跡規劃是實現集群編隊飛行執行任務的關鍵技術之一，其是指考慮飛行地形、氣候、威脅等因素，以及飛機自身平臺性能約束，為無人機集群制定從初始位置到目標位置的最優飛行路徑。

解決無人機集群航跡規劃問題的關鍵在于優化算法設計，當前國內外對無人機航跡規劃算法設計進行了一些嘗試與突破，但仍存在較大的局限性，主要問題在于算法計算復雜度、求解精度、搜索時間難以平衡同時滿足任務要求，因此設計具有計算快、精度高、容錯率大等特點的航跡規劃算法是未來發展趨勢。

解決航跡規劃問題的算法一般包括傳統優化算法和各類進化算法，其中進化算法又以群智能算法為重點研究對象。粒子群優化算法就是一類典型的群智能算法，也是本文重點研究對象。粒子群算法(particle swarm optimization，PSO)是在1995年由美國社會心理學博士Kennedy和電子工程學博士 Eberhart共同提出的一種優化算法，是一個基于迭代方法的隨機搜索與最優化處理過程[1]。和遺傳算法相似，粒子群算法也是通過迭代尋找最優解，但它沒有遺傳算法中“交叉”和“變異”的操作，因此規則更加簡單。在粒子群優化算法中，目標被看作是所優化問題的可能解，個體被看作沒有質量和體積的粒子，每個粒子的運動方向和速度都受到自己和群體的歷史狀態信息的雙重影響，利用群體中個體間的信息共享和協作，引導群體朝著更好的解的方向運動，從而完成整個粒子群在解空間中搜索最優解[2]。

1 經典粒子群算法

在D維的解空間上，粒子群的速度更新和位置更新如下兩式所示，其中d表示位置或速度的第d維。

通常用Ns表示粒子群種群規模，記f(xi)為所優化問題的評價函數，粒子位置的優劣是依靠f(xi)的值來決定的。得到粒子新的位置后，可以求出對應的f(xi)，并更新粒子的歷史最優位置信息pBesti和種群的歷史最優位置信息gBesti，繼續迭代進行下一步操作。

圖1是粒子群優化算法求解優化問題的示意圖，搜索空間是二維，全局最優解在黑點處，粒子從初始位置更新到了更新位置。其中v1是全局歷史最優解引起的粒子的速度，v2是粒子歷史最優解引起的速度，v3是粒子原來具有的速度。粒子最終的速度v由v1、v2和v3共同決定，使得粒子從初始位置到達更新位置，接下來以同樣的方式繼續更新速度和位置，粒子會逐漸接近全局最優解位置[4]。

圖1 粒子群優化算法求解優化問題的示意圖

粒子群算法的優點包括：通用性較強、搜索能力全面、算法原理簡單等等。但是標準粒子群算法的缺點也很明顯，比如在以全局最優值為搜索目標時局部搜索能力較差、容易早熟陷入局部最優，無法保證一定能夠搜索到全局最優值等等[5]。

2 改進粒子群算法在航跡規劃中的應用

由于傳統粒子群優化算法應用在集群航跡規劃中有早熟收斂過快，后期容易陷入局部最優，搜索到的航跡點軌跡不一定是最優解的問題，而單純增加種群數量和節點個數則會導致計算量大幅度增加[6]，故本文采用整體粒子群航跡規劃和節點間粒子群航跡再規劃相結合的策略，可以更好地滿足航跡規劃從快速全局搜索過渡到精確局部搜索的要求。

整體粒子群航跡規劃。建立無人機航跡規劃模型，考慮無人機各項約束條件、優化指標等信息，設定粒子群種群數量、節點數目、迭代次數、學習因子、慣性權重等參數，快速規劃得出無人機由當前位置到目標位置的最優飛行航跡。

節點間粒子群航跡再規劃。在整體粒子群航跡規劃之后，對于每兩個相鄰的節點間的航跡，先利用改進評價函數判斷其可靠性，若滿足指標則保留，若不滿足指標，則選取該相鄰兩個節點作為初始點和目標點，考慮無人機各種約束信息，改進位置速度更新公式使其滿足局部搜索要求，進行粒子群航跡的再規劃。

利用改進粒子群算法進行航跡規劃流程大致如圖2所示。

圖2 航跡規劃流程圖

對于整體粒子群航跡規劃，首先進行航跡規劃模型建立，包括環境建模以及確定約束條件和評價函數[7-8]。

航跡規劃的環境模型包括基準地形模型、障礙區域以及威脅區域3個部分。基準地形建模設置飛行區域為200 m×200 m×100 m的直角坐標區域；障礙區域建模采用山峰模型，其數學描述為：

式中，hi表示第i座山的高度，(xi,yi)為山峰的地理中心坐標，xsi,ysi分別表示山峰在x軸和y軸方向的坡度向量，(x,y)代表地形中每個點投影到平面的點坐標，z(x,y)表示地形中每個點的高度；威脅區域一般指電磁干擾區域、禁飛區域以及敵方探測區域[9]等，可采用半球形模型對威脅區域建模，其數學描述為：

式中，Wi(x,y,z)表示第i個威脅區域；(xi,yi,0)表示威脅區域的中心；ri表示威脅區域半徑。

約束條件一般包括以下幾項[10-11]：

1)航跡長度Lp：無人機一次任務的總飛行路程。設第i個節點與下一個節點間的距離為li，兩個節點的坐標分別為(xi,yi,zi)，(xi+1,yi+1,zi+1)，則有:

2)剩余飛行時間tp：無人機在執行一次任務過程中，最大飛行時間與已飛行時間的差值；

3)最低飛行高度h：無人機在飛行中與地形之間允許的最短距離，h太小會增加無人機與地面碰撞的概率；

還有很多無人機集群約束和環境約束條件，例如無人機數量約束、節點間距約束、大氣威脅等[12]。本文選擇航跡長度、剩余飛行時間和最低飛行高度來組成整體航跡評價函數，如下式所示:

式中,N為節點總數，Li為第i個節點與前一個節點間的距離；ti為到第i個節點的剩余時間；Ti為第i個節點處的高度威脅值。φ1、φ2和φ3為0～1的權重系數，通過調整它們的大小來改變各項約束條件對整體航跡評價函數的影響。

對于節點間粒子群航跡再規劃，其要求航跡搜索的解更加精確，所得到的航跡結果更加圓滑，故可以采用改進航跡評價函數和速度位置更新公式的方法增強算法局部搜索能力。

與整體粒子群航跡規劃評價函數不同，節點間航跡的評價函數應當更加關注無人機自身飛行條件約束情況[13]。本文選擇最小轉彎角、最大上升角和最大下降角來組成節點間航跡評價函數，如下式所示:

fi=?1θi+?2φi+?3αi，i=1,…,N-1

式中,N為節點總數；θi為第i個節點間距中的最小轉彎角度；φi為第i個節點間距中的最大上升角度，αi為第i個節點間距中的最大下降角度。?1、?2和?3為0～1的權值。通過該評價函數判斷各個節點間的航跡是否符合要求，滿足要求的則保留，不滿足要求的則利用改進的粒子群更新公式進行節點間航跡再規劃。

對于節點間粒子群航跡規劃的更新公式的改進主要在于合理調節算法參數上。由于慣性權重ω的取值對算法的搜索性能有很大的影響，較大的慣性權重可加快算法搜索速度，較小的慣性權重可增強算法搜索能力。但是單純設計成線性遞減的慣性權重在迭代后期不能很好地滿足精確搜索的要求，而節點間粒子群航跡規劃重點就在于迭代后期的精確搜索，故本文設計了一種針對局部精確搜索的慣性權重調整方法。具體的調整公式為：

式中，ωmax和ωmin為慣性權重的最大值和最小值，t為已迭代次數，T為最大迭代次數。λ1和λ2表示算法前期所占的比例，范圍為0≤λ1<λ2<1。λ1和λ2的取值是由規劃問題的復雜程度、要求的搜索精度等因素共同決定的[14]。由于節點間粒子群搜索前已經由整體粒子群搜索規劃好大致航跡，所以在實驗中λ1應當盡可能地取小，必要時可取為0。這種分段式調整策略使得在節點間航跡規劃的初期有一個短暫的快速搜索階段，防止在算法初期就陷入局部搜索停滯不前的情況；在算法前中期搜索速度快速下降，搜索精度快速大幅度上升，并在算法后期維持最高的搜索精度，有助于節點間航跡規劃問題的解決[15-16]。

3 仿真與分析

針對本文提出的基于改進粒子群算法的航跡規劃方法，利用Matlab R2017a進行仿真，并與傳統和其他粒子群航跡規劃方法進行對比分析。

建立環境模型：設定2000 m×2000 m×1000 m的直角坐標區域，給定半球形威脅模型、山峰模型的中心及半徑。環境建模如圖3所示。

圖3 環境建模仿真

設置整體航跡規劃粒子群算法參數：設定無人機數量為12，種群數量N=50，群體最大迭代次數T=100，航跡節點數目取為30，最大迭代時間tmax取1000。學習因子取C1=C2=2，慣性權重ω取0.7。整體粒子群航跡規劃評價函數中φ1、φ2和φ3分別取0.5,0.3,0.2。整體粒子群航跡規劃仿真結果如圖4所示。

圖4 整體粒子群航跡規劃圖

繼續進行節點間航跡規劃。利用節點間航跡規劃評價函數判斷各節點航跡合理性，?1、?2和?3分別取0.4,0.3,0.3。設置節點間航跡規劃粒子群算法參數：種群數量改為100，航跡節點數目改為10。慣性權重ω按照調整公式設置，其中λ1和λ2分別取為0.1和0.3，ωmax和ωmin取為0.9和0.4。其余參數不變。

12架無人機航跡規劃結果如圖5所示。可見無人機編隊形成圓滑航跡，繞過障礙和山峰飛行并在目的地形成大致圓形構型。

圖5 最終航跡規劃結果圖

表1 算法性能對比

可以看出，本文提出的改進算法對比傳統粒子群航跡規劃算法(BPSO)，在整體航跡規劃評價值相差不多的情況下，航跡規劃時間明顯縮短；對比慣性權重線性變化的粒子群算法(LPSO)，整體航跡規劃評價值和時間相近，而節點間航跡規劃評價平均值明顯更大，航跡規劃時間也明顯縮短，因此可以很好地滿足無人機集群航跡規劃搜索速度和精度的要求。但是，無論是LPSO還是IPSO，兩部分航跡規劃的時間總和都要比一次航跡規劃時間要多，雖然很大程度上提高了解的精度，卻在某些方面不能滿足航跡規劃實時性的需要，因此也為后續的研究指出了方向。

4 結束語

本文提出了一種基于改進粒子群算法的無人機航跡規劃策略，相較于標準粒子群算法和傳統航跡規劃策略具有如下優點：

1)算法適應性強。對于慣性權重ω的分段式調整簡單快捷，使得算法既滿足了航跡規劃前期的快速搜索要求又滿足了后期高搜索精度要求，對于評價函數的兩種設計使得不同階段的航跡規劃更加有針對性。

2)航跡規劃策略靈活。采用的整體航跡規劃和節點間航跡規劃相結合的策略確保了在計算資源的高效利用下，快速搜索到滿足要求的精確航跡。

該算法策略可以很好地滿足航跡規劃的需求，但仍存在一些不足之處，比如應對突發威脅時缺乏在線實時航跡規劃手段，集中式計算負擔過大有時不能滿足需要等等。后續將在算法自主實時性方面尋求突破，重點關注在線實時航跡規劃方法和分布式算法架構，完善本文所提出的無人機集群航跡規劃策略。