基于稀疏A*與人工勢場算法的EOSID路徑規(guī)劃

楊軍利，李阿丹，2*，程 穎，李立坤

（1. 中國民用航空飛行學院飛行技術(shù)學院，廣漢 618300；2. 中國東方航空武漢有限責任公司，武漢 430000；3. 中國商用飛機有限責任公司，上海 200000）

0 引言

隨著我國民航業(yè)的快速發(fā)展，行業(yè)規(guī)模不斷擴大，通航機場特別是高原和復(fù)雜機場不斷增多。截止2022年，我國境內(nèi)運輸機場（不含港澳臺）達到了254 個，其中高原機場43 個。從安全與效益的角度，民航業(yè)對于制作EOSID 的需求日益增加。

早期的研究側(cè)重于EOSID 設(shè)計與性能分析［1-3］，起飛一發(fā)失效路徑由制作人員根據(jù)經(jīng)驗手工完成，工作量很大。為提高EOSID 的制作效率，需結(jié)合機場的數(shù)字地形實現(xiàn)路徑的自動規(guī)劃。路徑規(guī)劃算法分為數(shù)學規(guī)劃方法、基于圖形學的方法如Dijkstra 路徑搜索算法、A*算法和隨機路標圖（PRM）算法等，智能優(yōu)化算法如蜜獾算法、獅群算法等，以及一些融合算法。劉曉民［4］基于高精度數(shù)字地圖，利用PRM 和Dijkstra 算法結(jié)合飛機性能軟件生成了滿足起飛性能要求的EOSID 航跡。Masson 等［5］將基于A*算法應(yīng)用于規(guī)劃起飛一發(fā)失效路徑［6-7］；蔣維安等［8］總結(jié)了EOSID 總體設(shè)計流程，提出了基于A*算法的應(yīng)急程序路徑搜索方法；焦衛(wèi)東等［9］在考慮了航向角和地形威脅的基礎(chǔ)上，利用稀疏A*生成了EOSID 的三維連續(xù)航跡。人工勢場法［10-13］也是常用于路徑規(guī)劃的方法之一，其局部避障能力較優(yōu)。文獻［14］將稀疏A*搜索算法和改進的人工勢場法相結(jié)合，應(yīng)用在不同的障礙物所構(gòu)成的威脅分布中，規(guī)劃出了給定威脅指標下的無人機最優(yōu)路徑，結(jié)果證明了其具有良好的避障性能。對于地形復(fù)雜機場進行一發(fā)失效應(yīng)急程序路徑規(guī)劃，不僅需要著眼于機場附近整體凈空條件進行全局規(guī)劃，還需要關(guān)注局部避障能力，尤其在新增障礙物時，才能充分結(jié)合民航飛機性能提升業(yè)載。

本文旨在采用稀疏A*算法的全局搜索能力融合人工勢場法的局部避障能力，結(jié)合一發(fā)失效規(guī)章限制及DEM 數(shù)據(jù)，快速規(guī)劃民航飛機一發(fā)失效應(yīng)急程序路徑。稀疏A*算法考慮航向角、爬升/下滑角、起始轉(zhuǎn)彎點等約束條件，結(jié)合飛機性能的同時縮小搜索空間，縮短算法收斂時間；對于地形復(fù)雜的區(qū)域融合人工勢場法，提升算法的局部避障能力。最后對規(guī)劃航跡進行平滑處理并在MATLAB 中對規(guī)劃路徑進行驗證，實現(xiàn)基于電子地形圖的EOSID路徑規(guī)劃。

1 EOSID制作規(guī)范

對高原機場及地形復(fù)雜機場，在起飛離場和進近復(fù)飛中，障礙物是最主要的安全風險。一般飛機的全發(fā)性能可滿足標準儀表進離場程序的起飛和復(fù)飛越障要求。對于一發(fā)失效后沿標準離場程序的起飛，由于飛機性能大大降低，可能使得最大起飛重量過小，不能滿足航空公司運行經(jīng)濟性要求，這就是制作一發(fā)失效應(yīng)急程序的初衷。2014 年民航局發(fā)布了EOSID 制作規(guī)范［15］，具體規(guī)定了該程序的水平保護區(qū)和垂直越障要求。起飛離場保護區(qū)如圖1所示。

圖1 離場保護區(qū)

在有航跡引導時，飛機一發(fā)失效起飛離場保護區(qū)半寬從90 米開始以12.5%梯度擴張至900 米，之后保持900 米直至起飛航跡結(jié)束點。與無人機規(guī)劃僅要求避開障礙物不同，民航飛機需要根據(jù)保護區(qū)內(nèi)的障礙物來精確計算飛機起飛性能，對路徑規(guī)劃提出了更高的要求。在總起飛飛行軌跡的基礎(chǔ)上，考慮到飛行員的飛行技術(shù)誤差和飛機性能變化引起上升梯度減小等因素，減去一個梯度后所得到的凈起飛垂直飛行軌跡（對于水平加速階段，加速度要減少當量的數(shù)值），起飛減去的梯度值為：0.8%（雙發(fā)）、0.9%（三發(fā)）、1.0%（四發(fā)）。凈起飛飛行航跡的超障余度為10.7米。

2 路徑規(guī)劃算法

傳統(tǒng)A*算法是一種啟發(fā)式全局路徑規(guī)劃算法，它通過迭代函數(shù)進行求解，從起始點向鄰節(jié)點進行求解，其算法結(jié)構(gòu)直觀、易實現(xiàn)、搜索效率較高。稀疏A*算法在計算當前節(jié)點到目標點的評估代價時只使用了部分圖信息，適用于大規(guī)模稀疏圖的搜索，這種算法將搜索空間劃分為一組子空間。例如，如果在一個大型的室內(nèi)環(huán)境中查找路徑，可以將一個房間看作一個子空間，只考慮從一個房間到一個房間的最短路徑，而不考慮房間內(nèi)部的每一個可能的狀態(tài)，從而大大減少搜索空間的大小，加速查找過程。路徑規(guī)劃所使用的SRTM地形圖分辨率為90×90米，屬于大規(guī)模稀疏圖，適用稀疏A*算法。

本文稀疏A*算法結(jié)合飛機性能考慮航向角、爬升角、起始轉(zhuǎn)彎點等約束條件縮小搜索空間，縮短算法收斂時間；缺點是當問題規(guī)模較大時，時空復(fù)雜度很高，易陷入局部最優(yōu)解或無解。人工勢場法是常見的路徑規(guī)劃方法，局部避障能力較優(yōu)。其基本思想是在障礙物周圍構(gòu)建障礙物斥力勢場，在目標點周圍構(gòu)建引力勢場，決定斥力勢場的因素是飛機與障礙物之間的距離，當飛機未進入障礙物的影響范圍時，其受到的勢能值為零；當飛機進入障礙物的影響范圍后，兩者之間的距離越小、障礙物越高，飛機受到的勢能值就越大；反之則越小。

2.1 算法流程

采用稀疏A*和人工勢場算法進行EOSID路徑規(guī)劃，數(shù)據(jù)源為SRTM（shuttle radar topography mission）的DEM 數(shù)據(jù)，算法流程如圖2 所示。EOSID路徑規(guī)劃分多個航段進行規(guī)劃時，應(yīng)結(jié)合起飛性能四個階段性能參數(shù)，每段航跡采取相同路徑規(guī)劃方法完成，本文分兩段完成路徑規(guī)劃。

圖2 EOSID路徑規(guī)劃流程圖

2.2 規(guī)劃空間處理

根據(jù)機場地形情況進行初步分類，受機場周圍地形條件的差異影響，選擇不同的梯度對地形數(shù)據(jù)進行篩選處理，構(gòu)造三維搜索空間。如圖3 所示，超過錐形面的區(qū)域被視為不可通過，反之則為可通過區(qū)域。此外，通過腐蝕算法，將與不可通過區(qū)域相鄰的區(qū)域進行裁剪，縮小可通過區(qū)域空間，避免規(guī)劃的起飛一發(fā)失效路徑保護區(qū)引入地形較高障礙物。

圖3 搜索空間

2.3 航跡約束條件

首先，根據(jù)各大機場公布的機場信息、標準儀表離場程序（SID），確定航跡規(guī)劃起始點、起始航跡走向。航跡規(guī)劃過程中，主要的約束條件為：最大轉(zhuǎn)彎角?max、最大爬升角θmax、最大/小航跡段長度LmaxLmin等。其中轉(zhuǎn)彎角、爬升角最大/最小航跡長度均不能超限。飛機改變飛行姿態(tài)前必須保持直飛的最短距離由飛機機動能力和導航要求決定，視為最小航跡段長度；最大航跡段長度可根據(jù)需要進行調(diào)整，通常最大航跡長度都不是民航飛機起飛一發(fā)失效路徑規(guī)劃的限制因素。

2.4 航跡點代價函數(shù)

算法航跡點代價函數(shù)為

式中：F(n)為起始點經(jīng)由節(jié)點n到目標點的評估代價；G(n)為起始點到節(jié)點n的實際代價；H(n)為節(jié)點n到目標點最優(yōu)路徑的評估代價。H(n)有各種不同的定義方式，常用的啟發(fā)距離有歐幾里得距離、曼哈頓距離、切比雪夫距離等。綜合考慮應(yīng)用場景后，本式中使用的是歐幾里得距離，即直線距離。其中：

式（2）中：N為航跡總段數(shù)，w1為航跡長度權(quán)重因子，w2為人工勢場斥力權(quán)重因子，w3為路徑地形高度權(quán)重因子。li為第i段航跡的長度，ri為估值函數(shù)中引入的人工勢場法斥力因子，h為規(guī)劃節(jié)點的地形高度。評估函數(shù)中引入規(guī)劃路徑地形高度在于規(guī)劃路徑不僅要避開高大障礙物，更要在可運行空間內(nèi)選擇地形相對平坦的區(qū)域運行。

式（5）中ρ0為一常數(shù)，表示障礙物對飛機產(chǎn)生作用的最大影響范圍。ρ(q,qi)為飛機到第i個障礙物的距離。

稀疏A*算法在求解最優(yōu)路徑過程中，依靠啟發(fā)函數(shù)對擴展節(jié)點進行選取，受地形復(fù)雜、搜索空間削減等影響，容易陷入局部無解。通過加入人工勢場斥力因子避開障礙物，提升稀疏A*算法的魯棒性。此外，評估函數(shù)中增加考慮各待擴展節(jié)點高度數(shù)值項，在不同凈空條件的機場調(diào)整其在評估函數(shù)中的權(quán)重，從而不僅僅規(guī)避障礙物，還選擇最有利的地形來產(chǎn)生最優(yōu)飛機性能數(shù)據(jù)。

2.5 稀疏A*與人工勢場法搜索

從當前節(jié)點，在航向角限制范圍內(nèi)均勻選取M個扇面，由爬升角確定每個扇面的區(qū)域范圍，根據(jù)爬升角限制范圍，將扇面均勻分為N個扇區(qū)，從而構(gòu)成結(jié)合飛機性能的起飛、爬升轉(zhuǎn)彎的三維搜索方向，共得到M×N個扇區(qū)，及M×N個子節(jié)點。如M=N= 3，則由傳統(tǒng)算法的26 個子節(jié)點削減為9 個，有效縮小了搜索空間，提升算法運行效率。將每次代價函數(shù)計算得到代價最小的點保存于CLOSED 列表內(nèi)，直至目標點，進行回溯后即可獲得一條完整的EOSID規(guī)劃航徑。

具體步驟如下：

（1）將起始節(jié)點插入OPEN 表內(nèi)，置空CLOSED表；

（2）將OPEN 表中最小代價點存進CLOSED表，同時將其置于當前節(jié)點；

（3）如果目標點加入CLOSED 表則搜索結(jié)束，得到一條從起始節(jié)點到目標節(jié)點代價最小的路徑；

（4）擴展當前節(jié)點。將進入當前節(jié)點的航線在水平面上投影方向作為對稱軸，水平擴展區(qū)是最大轉(zhuǎn)彎角的兩倍。待擴展區(qū)垂直剖面水平方向?qū)ΨQ，亦為最大爬升角的兩倍，將可用節(jié)點加入到OPEN列表中；

（5）將上一步計算得到的每一個最小代價節(jié)點與OPEN表中的節(jié)點進行對比，如果代價值更小，則更新該節(jié)點代價相關(guān)參數(shù)值；如果該節(jié)點在CLOSED表中則忽略；

（6）輸出規(guī)劃結(jié)果。

3 算例與分析

3.1 計算條件

某機場位于西藏東南部，雅魯藏布江的河谷地帶。機場場區(qū)較為平坦，但兩側(cè)山體較高，凈空條件比較復(fù)雜。以該機場05 號跑道離場程序為例，采用稀疏A*與人工勢場算法進行路徑規(guī)劃，數(shù)據(jù)源為SRTM 90×90 米數(shù)字地形高程模型；離場航跡起始點位于05 跑道末端，經(jīng)緯度坐標（N29°18'，E094°20'），標高2947 米，終點經(jīng)緯度（N29°39'，E094°21'），最大拐彎角和最大爬升角分別為45°和30°；最小步長90 米，扇面?zhèn)€數(shù)3，扇區(qū)個數(shù)3。

3.2 結(jié)果與分析

圖4為擬合三維航跡結(jié)合地形呈現(xiàn)結(jié)果；圖5、圖6 為基于稀疏A*與人工勢場法規(guī)劃水平路徑、垂直剖面；圖7 為基于稀疏A*算法與人工勢場法融合局部避障完成規(guī)劃三維路徑。圖8為該機場公共RNP AR EOSID程序圖。

圖4 05號EOSID三維航跡

圖5 05號跑道EOSID水平軌跡

圖6 05號跑道EOSID垂直軌跡

圖7 05號跑道EOSID三維航跡擬合

圖8 05號RNP AR EOSID

圖5～圖8 對比顯示，本文算法規(guī)劃EOSID路徑與公共RNP AR EOSID較一致。

4 結(jié)語

通過稀疏A*與人工勢場算法的融合，提升了局部避障能力，增強了算法的魯棒性，為航空公司進行民用飛機EOSID 路徑規(guī)劃提供了現(xiàn)實可行的方案。稀疏A*與人工勢場法的融合也增加了計算量，尤其是障礙物數(shù)量多的情況，因此需要在算法效率上進一步優(yōu)化。