基于POA算法的無人機航跡規劃優化方法

賈漢博，馬琳，張忠旺

1.哈爾濱工業大學，黑龍江 哈爾濱 150006

2.中國航空無線電電子研究所，上海 200241

隨著自動控制以及人工智能領域的蓬勃發展，無人機（UAⅤ）被廣泛應用于各種場景之中，如災難營救、未知環境勘探、遠程精確打擊目標、針對某一環境的覆蓋式探索以及集群對抗[1-3]。UAⅤ的發展可以極大地提高任務效率并避免不必要損失，對于各種領域都具有重大意義。

為了讓UAⅤ自主地完成復雜任務，許多學者對UAⅤ航跡規劃進行了深入研究。基于群智能優化的航跡規劃算法因其擴展性強的特點已成為研究熱點。目前常見的群智能優化算法包括蟻群算法（ACO）[4]、差分進化算法（DE）[5]、果蠅優化算法（FOA）[6]和粒子群優化算法（PSO）[7]等。其中，參考文獻[8]改進了ACO算法中的信息素分布以及轉移概率，實現了復雜障礙環境下的UAⅤ航跡規劃。參考文獻[9]將DE算法與逼近策略相結合，提出了一種混合差分進化算法，并用于固定翼UAⅤ在復雜三維環境下的航跡規劃。參考文獻[10]提出了一種基于最優參考點果蠅優化算法，將兩個連續航跡點的中點設置為參考點以提高FOA算法的收斂速度。參考文獻[11]將綜合改進粒子群算法（CⅠPSO）應用于UAⅤ航跡規劃。參考文獻[11]利用混沌Logistic映射來令算法的初始值更加隨機，并提出了一種自適應線性變化策略來調整CⅠPSO 算法中的參數。仿真結果證明了該算法在收斂速度以及航跡規劃結果方面的優勢，但其采用的地形圖過于簡單，無法評估在復雜地形下的算法性能。

傳教優化算法（POA）是Wei Dong 等[12]于2020 年提出的一種群智能優化算法，該算法結合個體適應度以及位置之間的關系計算權重，以維持個體的多樣性，且利用精英策略以及人工免疫算法加速收斂。最終，參考文獻[12]通過CEC’17數據集的測試結果說明了該算法在收斂速度以及精度方面的性能。但將POA算法應用于UAⅤ航跡規劃時，POA算法中隨機初始化傳教士位置的方式并沒有結合航跡的方向特性，且對于三維坐標以及邊界條件的處理仍有一些問題需要解決。

因此，本文提出了基于POA算法的UAⅤ航跡規劃優化方法。首先，本文提出了結合航跡長度、地形代價以及飛行高度代價的目標函數。其次，在初始化傳教士位置時引入旋轉坐標系，通過這種方式使得初始化的航跡結果具有一定的方向性，極大地縮短了算法收斂時間。此外，本文詳細說明了航跡坐標點以及邊界條件在POA 中的具體處理方式，解決了POA 與航跡規劃相結合的問題。最后，本文分別從航跡長度、算法收斂速度以及針對不同地形圖的適應程度三個方面對比CⅠPSO航跡規劃，證明了基于POA算法的UAⅤ航跡規劃的有效性。

1 問題建模

1.1 地圖限制

對于UAⅤ航跡規劃這一優化問題而言，需要考慮多方面的因素。首先，UAⅤ要在地圖限制的區域內飛行。其次，為了令UAⅤ安全飛行，UAⅤ不能和地面發生碰撞并與地面保持一定的安全距離，且飛行高度不能超出最大飛行高度的限制。最后，UAⅤ的飛行距離要盡可能短，以節省燃料并盡快到達目的地。

本文利用三維坐標(x,y,z)來表示地形圖，其中x與y分別表示地形圖在水平面上的橫、縱坐標，z表示(x,y)處的地形高度。通過控制z的取值即可生成不同的地形圖。為了驗證算法在多種地形條件下的性能，本文采用Foxhole Shekel優化問題的數學函數方法生成地形[13]，即

式中，NT表示山峰個數；ai與bi用于控制山峰位置；ci用于控制山峰高度。

就UAⅤ的具體航跡而言，若航跡點的總個數為N，其任意的第n個航跡點wn=(xn,yn,zn)應在地圖范圍內，即

式中，xmin、xmax、ymin、ymax、zmin與zmax分別對應于地圖坐標x、y、z的最小值以及最大值。

1.2 目標函數設計

1.2.1 總代價

設計合理的目標函數對于UAⅤ航跡規劃這一優化問題至關重要。本文設計的優化目標函數綜合考慮了航跡長度、UAⅤ和地形之間的避碰以及UAⅤ飛行高度的限制，該目標函數可以表示為

式中，fL、fT以及fH分別為航跡長度代價、地形代價以及飛行高度代價；p1、p2以及p3為對應的權重。通過調整權重可以調整優化目標，為了方便，本文采用p1=p2=p3= 1。

1.2.2 航跡長度代價

考慮到UAⅤ的燃料限制，更短的航跡意味著UAⅤ可以在燃料消耗完畢之前完成任務。另外，飛行時間越短，被未知威脅發現的概率同樣更低。本文采用參考文獻[13]提到的路徑長度比率（PLR）來描述航跡長度代價fL，即

fL越小表示航跡長度越短，越有利于飛行任務的完成。且fL這種表示方式并不會因為地圖大小或起始點以及終點位置的改變而顯著影響航跡長度代價數值，即fL對于不同地形圖的適應能力更強。

1.2.3 地形代價

為了實現安全飛行，UAⅤ在整個航行過程中不能與地形發生任何碰撞，且UAⅤ與地面的距離要滿足最低安全距離的要求。雖然本文所提航跡規劃算法的優化變量為航跡點wn，但UAⅤ在航跡點之間航行時同樣要避免同地形發生碰撞，因此本文將相鄰航跡點按固定距離d分為Mn份，且為了降低算法復雜度，wn-1與wn之間的坐標wm,n通過線性插值獲得。另外，d的取值應綜合考慮算法復雜度以及航跡規劃結果的精度。那么，本文所提地形代價fT可以表示為

1.2.4 飛行高度代價

受UAⅤ動力學性能的影響，其飛行高度受限，且對于一些特殊的任務類型而言，飛行高度越高，被未知威脅發現的概率就越大。本文提出的飛行高度代價和地形代價類似，即飛行高度代價fH可以表示為

式中，H為UAⅤ最大飛行高度。但和地形代價不同的是，飛行高度的限制往往不十分嚴格，因此可以通過調整目標函數中飛行高度代價所對應的權重p3來實現優化目標的動態調整，以滿足任務需求。

針對UAⅤ的其他性能約束（如最大水平飛行速度、最大旋轉角速度、最大上升下降速度等）將在未來的研究中體現。

2 基于POA算法的UAV航跡規劃

2.1 POA算法概述

POA 算法受傳教行為啟發，分為初始化個體位置與目標函數數值計算、影響權重因子計算、向繼承人傳播知識、文化競爭以及文化發展5個步驟。本文則將POA算法用于UAⅤ航跡規劃之中。

POA 算法首先生成p個傳教士，初始化其位置并完成目標函數數值的計算。然后歸一化其目標函數值即計算影響權重因子faff(i,niter)，i表示第i個傳教士，niter表示第niter次迭代。在每個傳教士向其對應的in個繼承人傳播知識時，POA算法結合影響權重因子并根據人工免疫算法實現了可變方差r/3的全局搜索。為了加速算法收斂，POA算法在文化競爭步驟采用精英策略，即選擇ein個個體作為精英個體直接成為傳教士進入下一步驟。同時為了保持個體的多樣性，POA算法基于個體中心位置以及對應的目標函數數值計算了文化競爭步驟中的權重weight(i)，該權重表示了個體與樣本中心之間的差別，POA 算法選擇差別最大的p-ein個個體作為傳教士進入下一步，以維持樣本多樣性。最終，POA算法通過萊維飛行或高斯分布實現了文化發展，其本質為優化算法中的局部搜索。將上述過程迭代Niter次或達到算法收斂條件即可退出循環。

2.2 航跡點初始化

和其他優化問題不同的是，若航跡規劃在算法初始階段完全通過隨機的方式設置UAⅤ的航跡點會顯著降低優化算法的優化效率。因此，本文采用了參考文獻[14]所提的旋轉坐標系來生成初始航跡。旋轉坐標系本質上是一種沿xoy平面旋轉后的笛卡爾坐標系，為了方便，稱之為旋轉坐標系。圖1給出了旋轉坐標系和笛卡爾坐標系之間的關系。

圖1中，xyz表示笛卡兒坐標系，x′y′z′表示旋轉坐標系，旋轉坐標系的x′軸方向為UAⅤ航跡起始點和終點的連線方向，而y′軸方向則與x′軸方向垂直，x′O′y′平面和xoy平面平行，z′軸方向與z軸方向相同，淺色實心點代表航跡點，黑色實心點代表航跡點在x′O′y′平面的投影，旋轉坐標系原點o′為航跡起始點，D′點為航跡終點。笛卡兒坐標系內的坐標點(xn,yn,zn)與對應的旋轉坐標系坐標點(x′n,y′n,z′n)之間的關系滿足

式中，φ為航跡點與旋轉坐標系原點連線和旋轉坐標系x′軸的夾角，?為旋轉坐標系x′軸和笛卡兒坐標系x軸的夾角。

2.3 UAV航跡規劃優化方法

在利用POA算法進行UAⅤ航跡規劃時，需要利用旋轉坐標系生成p組初始航跡以代表p個傳教士，loci表示第i個傳教士的位置，對應隨機生成的第i組航跡點的集合loci={wn|1 ≤n≤N}。將生成的初始值代入式（3）中即可完成目標函數的計算，值得注意的是，雖然在計算地形代價以及飛行高度代價時需要利用線性插值之后的結果，但航跡規劃的優化變量仍為N個航跡點wn。

此外，由于航跡點的x、y以及z坐標無特殊的對應關系，因此在利用POA進行后續步驟時應將其作為三個獨立的優化變量進行看待，僅在計算目標函數以及對應權重時將三者結合。又由于POA 算法中各步驟均利用高斯分布進行搜索，因此基于POA算法航跡規劃的每個步驟的輸入以及輸出變量應滿足關系

經過向繼承人傳播知識、文化競爭以及文化發展三步之后即完成了一次POA算法的迭代，對應的傳教士位置分別記作loc′(i)、loc″(i)以及loc?(i)，在進行影響權重因子的數值比較后利用loc?(i)對loc(i)進行更新。最終，整個基于POA算法的UAⅤ航跡規劃將在達到最大迭代次數Niter或滿足迭代停止條件|fmin(niter)-fmin(niter- 1)|≤τ后停止迭代。fmin(niter)的定義為

式中，f(i,niter)為第niter次迭代中第i個傳教士的目標函數值。綜上所述，基于POA 算法的UAⅤ航跡規劃偽代碼如下：

算法1 基于POA算法的UAⅤ航跡規劃輸入：地形參數、最小安全距離dsafe、最大飛行高度H、線性插值步長d、傳教士數量p、迭代次數Niter、繼承人個數in以及精英數量ein輸出：最優航跡點集合locj ={wn|1 ≤n ≤N}1 根據旋轉坐標系生成初始航跡loci；2 niter = 1，fmin(0) =+inf；3 while niter ≤Niter do 4 計算faff(i，niter)以及fmin(niter)；5 if| fmin(niter)- fmin(niter - 1)|≤τ 6 Break；7 end if 8 結合影響權重因子以及人工免疫算法確定高斯分布方差rx/3、ry/3以及rz/3，并向繼承人傳播知識生成loc′(i)；9 邊界條件處理；10 選擇ein個精英作為傳教士進入下一步，計算其余權重weight(i)并選擇剩余p - ein個個體作為傳教士，生成loc″(i)；11 進行文化發展生成loc?(i)；12 邊界條件處理；13 比較影響權重因子并對loc(i)進行更新；14 end while 15 輸出最優航跡locj，j = arg min 1 ≤i ≤p {faff(loci)}。

3 仿真結果

3.1 仿真參數設置

本文將從航跡規劃結果、算法收斂速度以及對于不同地形的適應程度三個方面對比本文所提出的基于POA 算法的UAⅤ航跡規劃以及基于CⅠPSO[11]航跡規劃的性能。其中，地圖大小為10km × 10km × 0.5km，式中各個參數服從ai?U(0,10)、bi?U(0,10)以及ci?U(0.2,0.5)（此處設置山峰的最低高度為200m），山峰總數NT= 30，最小安全距離dsafe= 5m，最大飛行高度H= 120m，航跡點個數N= 15，線性插值步長d= 20m。POA算法的參數見表1，CⅠPSO算法的參數見表2。綜合考慮到算法收斂速度以及精度，將退出POA 迭代的參數設置為τ= 0.002。航跡起始點坐標為(0,0,0.0827)，航跡終點坐標為(10,10,0.0737)。

表1 POA算法參數Table 1 Parameters setting of POA

表2 CIPSO算法參數Table 2 Parameters setting of CIPSO

3.2 航跡規劃仿真結果對比

圖2 給出了本文所提算法的航跡規劃結果以及基于CⅠPSO航跡規劃結果的三維視圖以及俯視圖。從圖2中可以看出，在該地形條件下，本文所提算法成功實現了航跡規劃，沒有和地形產生任何碰撞并且滿足最小安全距離限制以及最大飛行高度限制，航跡總長度為14.3km。而基于CⅠPSO 的航跡規劃輸出的航跡長度為17.5km，這說明本文所提出的目標函數結合旋轉坐標系的初始化方法以及POA算法可以實現在多種限制條件下的航跡規劃，且輸出航跡長度優于基于CⅠPSO的航跡規劃方法。

圖3 給出了本文所提算法的收斂過程，所采用的地形圖和圖2所采用的地形圖相同。通過POA算法中收縮系數以及人工免疫算法的加入，并結合精英策略以及文化競爭步驟，本文所提算法在60 次迭代后實現了收斂。此外，旋轉坐標系的加入使得POA 算法初始值的目標函數數值明顯低于CⅠPSO，且收斂速度以及收斂后的目標函數大小均優于CⅠPSO。

本文同樣利用隨機生成地形圖的方法評估了所提算法對于不同環境的適應能力。圖4 給出了在100 個不同地形圖情況下本文所提算法航跡規劃結果的航跡長度，∞表示航跡不滿足地形限制或飛行高度限制。可以看到在地形變化劇烈的情況下，本文所提算法在100 次不同的地形條件下均成功完成UAⅤ航跡規劃，而基于CⅠPSO方法的成功率為72%。本文所提算法的平均航跡長度為14.5km，而基于CⅠPSO的航跡規劃方法輸出的平均航跡長度為16.6km。綜上所述，本文所提算法在針對不同地形的穩定性以及輸出航跡長度兩個方面均優于CⅠPSO。

在解算實時性方面，本文通過在MATLAB平臺上的運行時間說明了二者在實際運行速度上的差別。采用的計算機配置見表3，運行時間對比結果見表4。本文所提算法的運行時間為138.37s，CⅠPSO算法的運行時間為149.65s。

表3 計算機參數Table 3 Computer parameters

表4 運行時間對比結果Table 4 Results of running time

下面分析本文所提算法性能優于CⅠPSO 的具體原因。首先，CⅠPSO 在航跡初始化時沒有采用旋轉坐標系進行初始航跡的生成，而是采用Chaos-based[15]的方法在整個規劃空間進行航跡點的初始化。這種做法的確可以提升初始化航跡的隨機性，但由于沒有結合UAⅤ航跡的方向特性，因此在初始化時其目標函數數值明顯高于基于旋轉坐標系的生成方法。

此外，CⅠPSO算法為了加快算法收斂速度，在粒子位置更新時將目標函數較小的粒子疊加適當的偏移量替代目標函數較大的粒子，并將目標函數較小粒子的速度直接替換目標函數較大粒子的速度。這種策略的確可以提升收斂速度，但同時降低了樣本的多樣性。而POA算法為了提升樣本的多樣性在文化競爭中保留了部分代價函數較大的個體并作為傳教士進入下一次迭代。維持樣本多樣性對于航跡規劃而言十分重要，由于地形以及UAⅤ自身限制條件的復雜性，UAⅤ航跡規劃將存在多個局部最優，而樣本多樣性對于跳出局部最優具有重大意義。

4 結論

本文針對UAⅤ航跡規劃問題，將POA 算法用于UAⅤ航跡規劃之中。首先，本文提出了結合航跡長度、地形限制以及UAⅤ飛行高度限制的優化目標函數。其次，將旋轉坐標系引入POA算法的初始化步驟之中以加快算法收斂，并說明了基于POA算法的UAⅤ航跡規劃流程。最后，通過和CⅠPSO算法的仿真對比結果可知，對于同一地形圖，本文所提算法規劃的航跡長度為14.3km，CⅠPSO 為17.5km，且本文所提算法在60次迭代后實現收斂，初始值的目標函數數值以及收斂速度同樣優于CⅠPSO。針對100個不同地形圖的仿真結果可知，本文所提算法規劃成功率為100%，平均航跡長度為14.5km，而CⅠPSO 成功率為72%，平均航跡長度為16.6km。本文所提算法在計算機平臺上的運行時間為138.37s，而CⅠPSO為149.65s。以上對比結果均說明了本文所提基于POA算法的航跡規劃優化方法優于CⅠPSO，證明了算法的有效性。