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

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

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

0 引言

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

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

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

1 EOSID制作規(guī)范

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

圖1 離場(chǎng)保護(hù)區(qū)

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

2 路徑規(guī)劃算法

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

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

2.1 算法流程

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

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

2.2 規(guī)劃空間處理

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

圖3 搜索空間

2.3 航跡約束條件

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

2.4 航跡點(diǎn)代價(jià)函數(shù)

算法航跡點(diǎn)代價(jià)函數(shù)為

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

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

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

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

2.5 稀疏A*與人工勢(shì)場(chǎng)法搜索

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

具體步驟如下：

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

（2）將OPEN 表中最小代價(jià)點(diǎn)存進(jìn)CLOSED表，同時(shí)將其置于當(dāng)前節(jié)點(diǎn)；

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

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

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

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

3 算例與分析

3.1 計(jì)算條件

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

3.2 結(jié)果與分析

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

圖4 05號(hào)EOSID三維航跡

圖5 05號(hào)跑道EOSID水平軌跡

圖6 05號(hào)跑道EOSID垂直軌跡

圖7 05號(hào)跑道EOSID三維航跡擬合

圖8 05號(hào)RNP AR EOSID

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

4 結(jié)語(yǔ)

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