基于POA算法的無人機(jī)航跡規(guī)劃優(yōu)化方法

賈漢博，馬琳，張忠旺

1.哈爾濱工業(yè)大學(xué)，黑龍江 哈爾濱 150006

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

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

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

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

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

1 問題建模

1.1 地圖限制

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

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

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

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

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

1.2 目標(biāo)函數(shù)設(shè)計(jì)

1.2.1 總代價

設(shè)計(jì)合理的目標(biāo)函數(shù)對于UAⅤ航跡規(guī)劃這一優(yōu)化問題至關(guān)重要。本文設(shè)計(jì)的優(yōu)化目標(biāo)函數(shù)綜合考慮了航跡長度、UAⅤ和地形之間的避碰以及UAⅤ飛行高度的限制，該目標(biāo)函數(shù)可以表示為

式中，fL、fT以及fH分別為航跡長度代價、地形代價以及飛行高度代價；p1、p2以及p3為對應(yīng)的權(quán)重。通過調(diào)整權(quán)重可以調(diào)整優(yōu)化目標(biāo)，為了方便，本文采用p1=p2=p3= 1。

1.2.2 航跡長度代價

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

fL越小表示航跡長度越短，越有利于飛行任務(wù)的完成。且fL這種表示方式并不會因?yàn)榈貓D大小或起始點(diǎn)以及終點(diǎn)位置的改變而顯著影響航跡長度代價數(shù)值，即fL對于不同地形圖的適應(yīng)能力更強(qiáng)。

1.2.3 地形代價

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

1.2.4 飛行高度代價

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

式中，H為UAⅤ最大飛行高度。但和地形代價不同的是，飛行高度的限制往往不十分嚴(yán)格，因此可以通過調(diào)整目標(biāo)函數(shù)中飛行高度代價所對應(yīng)的權(quán)重p3來實(shí)現(xiàn)優(yōu)化目標(biāo)的動態(tài)調(diào)整，以滿足任務(wù)需求。

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

2 基于POA算法的UAV航跡規(guī)劃

2.1 POA算法概述

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

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

2.2 航跡點(diǎn)初始化

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

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

式中，φ為航跡點(diǎn)與旋轉(zhuǎn)坐標(biāo)系原點(diǎn)連線和旋轉(zhuǎn)坐標(biāo)系x′軸的夾角，?為旋轉(zhuǎn)坐標(biāo)系x′軸和笛卡兒坐標(biāo)系x軸的夾角。

2.3 UAV航跡規(guī)劃優(yōu)化方法

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

此外，由于航跡點(diǎn)的x、y以及z坐標(biāo)無特殊的對應(yīng)關(guān)系，因此在利用POA進(jìn)行后續(xù)步驟時應(yīng)將其作為三個獨(dú)立的優(yōu)化變量進(jìn)行看待，僅在計(jì)算目標(biāo)函數(shù)以及對應(yīng)權(quán)重時將三者結(jié)合。又由于POA 算法中各步驟均利用高斯分布進(jìn)行搜索，因此基于POA算法航跡規(guī)劃的每個步驟的輸入以及輸出變量應(yīng)滿足關(guān)系

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

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

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

3 仿真結(jié)果

3.1 仿真參數(shù)設(shè)置

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

表1 POA算法參數(shù)Table 1 Parameters setting of POA

表2 CIPSO算法參數(shù)Table 2 Parameters setting of CIPSO

3.2 航跡規(guī)劃仿真結(jié)果對比

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

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

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

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

表3 計(jì)算機(jī)參數(shù)Table 3 Computer parameters

表4 運(yùn)行時間對比結(jié)果Table 4 Results of running time

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

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

4 結(jié)論

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