基于粒子群算法的無人機智能航跡規(guī)劃技術

陳 偉（電子信息控制重點實驗室）

本文分析了復雜環(huán)境下無人機航跡規(guī)劃問題。首先，基于飛行環(huán)境建立了約束模型和優(yōu)化模型；其次在算法的設計上，采用了引入局部搜索操作的粒子群算法，有效平衡了算法在整個搜索過程中的全局搜索能力和局部搜索能力，并通過仿真實驗證明了模型和算法的有效性。

引言

無人機具有低成本、小體積、強隱蔽性和高生存力等特點，在多個領域取得了廣泛應用。為保證無人機高效完成指定任務，需要為其規(guī)劃特定的航跡，而隨著任務復雜性和飛行環(huán)境復雜多變性逐漸增加，預規(guī)劃航跡往往不能滿足實際需求，需要對環(huán)境和任務進行實時評估，并進行在線航跡規(guī)劃。

無人機航跡規(guī)劃技術，是在綜合考慮無人機任務、飛行環(huán)境以及自身性能約束下，設計合理的飛行路線，以最大限度地保障無人機成功完成任務并返航。其核心是在綜合考慮無人機平臺約束和環(huán)境約束前提下，如續(xù)航時間、油耗、機動性能、威脅等，設計最優(yōu)或較優(yōu)的航跡。由于約束因素較多，數學模型較為復雜，是典型的NP-Hard優(yōu)化問題。在相關理論研究中，廣泛采用的方法包括概略圖法、單元分解法、人工勢場法、數學規(guī)劃法和進化算法。其中，進化算法基于其啟發(fā)式的搜索能力，能夠處理復雜且變化的問題，得到廣泛的研究，主要包括遺傳算法、蟻群算法和粒子群算法。

遺傳算法是一種模擬生物進化過程的啟發(fā)式搜索算法，在早期的路徑規(guī)劃問題中被廣泛采用。但受限于編碼方式，遺傳算法在進行航跡規(guī)劃時的編解碼過程往往比較復雜，增加了計算復雜度。蟻群算法是模擬螞蟻覓食行為的啟發(fā)式算法，通過不斷更新起點至食物源的路徑信息素實現最優(yōu)路徑的獲取。由于蟻群算法起源于路徑選擇，使其在航跡規(guī)劃中設計思路清晰、編解碼過程簡單，應用非常廣泛。然而，蟻群算法的運行機制使得求解過程易于陷入局部最優(yōu)值，同時當解空間增大時，計算復雜度顯著提升，限制了其在三維航跡規(guī)劃上的應用。

粒子群算法是模擬鳥群覓食行為的啟發(fā)式算法，形式簡單，性能高效，廣泛應用于神經網絡、數據挖掘等領域。在航跡規(guī)劃中，有多種三維航跡規(guī)劃的粒子群算法，第一種是基于地形和威脅信息建立最小威脅曲面，并在該曲面上進行最優(yōu)航跡搜索。同時，通過將三維航跡在水平面進行投影構建有限多項式，進而將航跡規(guī)劃問題轉化為解空間多項式組合問題，降低了計算復雜度；第二種是以平臺機動性能限制、威脅程度和目標距離作為適應度函數，采用連續(xù)粒子群算法進行實時規(guī)劃，求取航跡的中間節(jié)點；第三種粒子群算法，引入自適應變異算子，實現粒子速度和位置的自適應更新和變異，以處理三維航跡規(guī)劃問題；第四種是結合粒子群優(yōu)化算法和B樣條插值方法，通過特定的編碼方式和適應度評價函數，使得生成的航跡具有較好的平滑度；第五種以障礙物頂點為基礎構造二維解空間，將航跡規(guī)劃問題轉化為非線性最小化問題，在靜態(tài)和動態(tài)環(huán)境下實現了最優(yōu)無碰撞航跡的設計；第六種是針對粒子群算法后期搜索能力不足等缺點，對慣性權重因子進行了改進，并在三維航跡規(guī)劃中取得了良好的效果。

相關研究表明，標準的粒子群算法在前期具有良好的全局搜索能力，但后期局部搜索能力不足，因此引入的動態(tài)調整慣性權重因子方法被廣泛采用，以提升算法在后期的局部搜索性能。然而，在相關的改進算法中，由于慣性權重因子的逐漸減小，算法的全局搜索能力顯著下降，易于陷入局部最優(yōu)解。為保證算法的全局搜索能力，同時加強算法的局部搜索能力，本文引入局部搜索算子，實現算法整體性能的提升。

問題分析

在航跡規(guī)劃的相關設計中，主要對飛行環(huán)境模型、約束條件和性能指標函數進行分析。在飛行環(huán)境模型中，主要包括可通行威脅區(qū)和不可通行威脅區(qū)。其中，可通行威脅區(qū)是指無人機可以從該區(qū)域飛行通過，但該區(qū)域的某些因素會影響無人機的飛行安全和任務執(zhí)行能力，包括強風區(qū)、側風區(qū)或其他人為影響因素。不可通行威脅區(qū)是指無人機不能從該區(qū)域威脅通過，否則無人機會損毀，主要包括地形限制和障礙物等。其飛行環(huán)境模型如圖1所示。

圖1 飛行環(huán)境威脅圖。

在約束條件分析上，主要考察平臺機動性能的限制，包括轉向角、最小航跡段和油耗。設無人機航跡表示如(1)所示。

其中（xS，yS）和（xT，yT）分別表示無人機任務的起點和終點，（xi，yi）表示航跡第i個中間節(jié)點。

根據平臺的機動性能，航跡的轉向角應不小于特定角度θmin，即有

其中(xi-1，yi-1)，(xi，yi)，和(xi+1，yi+1)為航跡的相鄰節(jié)點，Angle{.，.}為兩向量間的夾角，可由余弦定理進行計算。

在最小航跡段約束中，由于平臺的慣性，無人機在相鄰兩次改變飛行姿態(tài)期間，必須保證最低的直線飛行距離，即有

在油耗約束中，忽略無人機在不同飛行速度下油耗的差異，將油耗與整體航程等同考慮，可得

在航跡規(guī)劃中，性能指標作為衡量航跡的唯一標準，在很大程度上決定了算法的性能。結合相關文獻研究，以航跡所經過區(qū)域的威脅度和航跡長度作為評價指標，可以建立如下的優(yōu)化數學模型。其中，α為權重因子，表征航跡長度length(x，y)和航跡威脅threat(x，y)在總體性能指標中所占比重，可以根據不同需求進行具體設計。

算法設計

粒子群優(yōu)化算法的每個粒子都有自己的位置和速度，粒子的位置代表解空間的點，通常以xi表示，粒子的速度代表粒子的搜索方向和前進距離，通常以vi表示。該算法在初始時候隨機初始化，以f(xi)衡量該粒子的適應度，并以pBesti表示第i個粒子搜索過的最優(yōu)位置，以gBest表示種群搜索過的最優(yōu)位置。在進化過程中，粒子基于個體最優(yōu)信息和全局最優(yōu)信息進行更新，如(6)、（7）所示。

其中ωd為慣性權重因子，c1和c2分別為個體學習因子和全局學習因子。

研究表明，粒子群算法的搜索能力和更新方程中的參數有很大關系，包括慣性權重因子、個體/全局學習因子和種群規(guī)模。慣性權重因子能夠平衡算法的全局和局部搜索能力，是重要的控制參數。研究指出，較大的慣性權重因子可以保證算法具有較好的全局搜索能力，而較小的慣性權重因子可以保證較好的局部搜索能力。學習因子決定著粒子向個體歷史信息和全局歷史信息學習的程度，相關文獻對其進行了深入研究并給出了指導性設計意見。在種群規(guī)模上，大量的理論研究和仿真實例表明，針對解空間較小的情形，種群規(guī)模為20，一般能夠滿足性能需求，而對于復雜解空間，種群規(guī)模為50，一般能夠滿足性能需求。

從上述分析可知，通過動態(tài)調節(jié)慣性權重因子，能夠有效平衡算法在前期的全局搜索能力和后期的局部搜索能力，一般采用線性或指數遞減的形式。另一方面，由于算法在中后期的全局搜索能力下降，會增加陷入局部最優(yōu)解的風險，尤其在處理具有較多局部最小值的問題時性能欠佳。針對此類情形，本文提出了局部搜索的優(yōu)化策略，其中粒子群算法始終保持較大的慣性權重因子，以保證算法對全局的搜索能力。同時，在每一次迭代后引入局部搜索算子，對當前解的相鄰空間進行局部隨機搜索，如(8)所示。

可以看出，局部搜索的前進方向依然受個體最優(yōu)和全局最優(yōu)的影響，可以有效地增加算法對歷史信息的利用效率。同時應滿足v d＜vmax，其中vmax表征算法進行局部搜索領域的范圍。根據隨機搜索的步長，可以形成新的個體。進一步，將局部搜索的新個體與當前個體進行比較，保留性能較優(yōu)個體。算法流程如圖2所示。

圖2 改進PSO算法流程圖。

仿真實驗

根據圖1的環(huán)境威脅圖，采用基于局部搜索的改進粒子群算法，設計種群數為50，迭代50代，慣性權重因子ω=0.9，學習因子分別為c1=c2=1.5，其穩(wěn)定的航跡規(guī)劃結果（最優(yōu)解出現概率不低于80%）如圖3所示。而對于標準粒子群算法（權重因子動態(tài)變化），在采用相同種群規(guī)模時達到相同的穩(wěn)定結果需迭代100代左右，體現了局部搜索操作的有效性。

為了進一步比較標準粒子群算法與本文改進粒子群算法的效率，按相同的參數設置運行分別運行20和50次，并進行統(tǒng)計分析，結果如表1所示?？梢钥闯觯疚闹械乃惴ㄔ谟邢薜牡綌祪染哂休^強的穩(wěn)定性。

圖3 航跡規(guī)劃效果圖

表1 運行結果統(tǒng)計表

結論

本文針對典型的無人機任務場景，考察了二維情形下無人機航跡規(guī)劃問題?；趯αＷ尤核惴ǖ纳钊胙芯亢头治觯岢隽司植克阉鞯倪M化策略。相對于慣性權重動態(tài)變化的粒子群算法，本文改進的算法既保證了在整個進化過程中都具有良好的全局搜索能力，也保證了對局部區(qū)域的充分搜索。仿真實驗表明，基于局部搜索的粒子群算法在航跡規(guī)劃中有效。 ■