RF航段自動(dòng)路徑規(guī)劃研究

任思潛，吳娟

（中國(guó)民用航空飛行學(xué)院飛行技術(shù)學(xué)院，廣漢618307）

0 引言

現(xiàn)國(guó)內(nèi)一些機(jī)場(chǎng)地形復(fù)雜且障礙物分布較為特殊，例如林芝、深圳等機(jī)場(chǎng)。在進(jìn)行飛行程序設(shè)計(jì)時(shí)較為困難，為了滿足規(guī)章規(guī)定的越障需求，躲避障礙物，提高航空器的運(yùn)行能力及飛行安全，往往會(huì)嘗試采用RF航段。RF航段是以某一個(gè)定位點(diǎn)（Fix）作為圓心，以固定轉(zhuǎn)彎半徑從一個(gè)定位點(diǎn)沿弧徑飛至另一個(gè)定位點(diǎn)。

目前，在飛行程序設(shè)計(jì)中，RF航段的設(shè)計(jì)均是通過(guò)人工篩選完成，但對(duì)于復(fù)雜地形機(jī)場(chǎng)，需要考慮地形和障礙物限制、航段保護(hù)區(qū)限制及航空器性能限制等眾多條件才能夠完成。這些諸多的限制條件給程序設(shè)計(jì)人員帶來(lái)了非常大地工作量。隨著路徑規(guī)劃算法的廣泛應(yīng)用，將其應(yīng)用于RF航段自動(dòng)路徑規(guī)劃的研究中，用計(jì)算機(jī)代替人工篩選與設(shè)計(jì)，可以在更大地、更復(fù)雜地搜索空間內(nèi)，使用更加多地約束條件，快速地確定一條最優(yōu)的RF航段。迄今為止，在我國(guó)，有關(guān)路徑規(guī)劃的研究較為豐富，但均是針對(duì)于無(wú)人機(jī)避障路徑規(guī)劃、無(wú)人機(jī)航跡規(guī)劃以及機(jī)器人路徑規(guī)劃等相關(guān)文章。李燕、季建楠等[1]提出一種自適應(yīng)變化信息素總量的方式，對(duì)蟻群算法進(jìn)行改進(jìn)，在復(fù)雜環(huán)境下研究了移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題。岳高峰、昱衡等[2-3]在綜合考慮路程與時(shí)間開(kāi)銷花費(fèi)情形下，經(jīng)過(guò)改進(jìn)A*算法的代價(jià)函數(shù)，提出了一種基于改進(jìn)A*的全局路徑規(guī)劃算法，分別對(duì)機(jī)器人移動(dòng)和采礦車的最優(yōu)路線規(guī)劃進(jìn)行了分析、討論。李曉輝等[4]在傳統(tǒng)A*算法的基礎(chǔ)上，考慮了多種類型的禁飛區(qū)，對(duì)原有的A*算法進(jìn)行改進(jìn)，研究了在任意兩個(gè)客戶點(diǎn)之間如何規(guī)劃搜索出一條最優(yōu)的無(wú)人機(jī)避障飛行路徑。趙睿、樓佩煌等[5]針對(duì)現(xiàn)有的遺傳算法收斂速度較慢等缺點(diǎn)，通過(guò)加入基于時(shí)間窗的調(diào)整策略方法，對(duì)AGV集結(jié)路徑進(jìn)行了研究。然而，關(guān)于RF航段自動(dòng)路徑規(guī)劃研究幾乎沒(méi)有。

本文采用一種余弦相似度法，結(jié)合點(diǎn)云圖像處理算法對(duì)地形障礙物特征信息進(jìn)行提取，通過(guò)三次樣條插值方法對(duì)地形進(jìn)行擬合。其次，根據(jù)RF航段特征，建立RF航段飛行曲線模型。考慮RF航段的保護(hù)區(qū)限制及規(guī)章規(guī)定越障標(biāo)準(zhǔn)等限制要求，采用改進(jìn)的A*算法尋找從一個(gè)定位點(diǎn)到另一個(gè)定位點(diǎn)之間搜尋出一條飛行路徑最短的RF航段。最后，為進(jìn)一步驗(yàn)證改進(jìn)A*算法的性能，選取A*算法和遺傳算法，進(jìn)行對(duì)比分析。結(jié)果表明，在搜尋時(shí)間與航段路徑長(zhǎng)度兩方面，改進(jìn)A*算法在性能上都優(yōu)于A*算法和遺傳算法；在內(nèi)存占用率方面，改進(jìn)A*算法明顯優(yōu)于A*算法。

1 RF航段自動(dòng)規(guī)劃建模

1.1 障礙物特征提取

為了能夠在復(fù)雜地形條件下找出一條符合實(shí)際的RF航段，需要從被搜索空間的地形中獲取地形信息及障礙物信息，如圖1所示。研究考慮采用余弦相似度法進(jìn)行障礙物特征信息提取[6-7]，提取的障礙物信息如下：

式中，(Xi,Yi)則為第i個(gè)障礙物的中心坐標(biāo)；Zi是障礙物參數(shù)，表示其高度；i表示障礙物的數(shù)量。

圖1障礙物特征信息提取

1.2 路徑規(guī)劃約束條件

根據(jù)飛行設(shè)計(jì)要求規(guī)定[8]，進(jìn)行RF航段自動(dòng)路徑規(guī)劃需考慮最短航段長(zhǎng)度、航跡角改變大小、航段保護(hù)區(qū)寬度、被搜索空間地形高及轉(zhuǎn)彎半徑等約束條件。

式（2）中，dmin為最短RF航段長(zhǎng)度；θ2和θ1分別為航段起始、終點(diǎn)的航跡角；α為預(yù)定航跡所需要的最大坡度；V1為航空器在轉(zhuǎn)彎最高點(diǎn)的最大轉(zhuǎn)彎空速；V2為在轉(zhuǎn)彎最高點(diǎn)中的最大風(fēng)速；L為保護(hù)區(qū)半寬距離，Q+Rmin在保護(hù)區(qū)內(nèi)滿足最低的越障礙要求；H為障礙物標(biāo)高，其值加上0.75海里不能大于航路點(diǎn)之前航段的超障高h(yuǎn)OCA與航路點(diǎn)之前航段的主區(qū)超障余度hMOC之間的差值。

1.3 建立RF航段數(shù)學(xué)模型

根據(jù)RF航段的特征，列出RF航段飛行曲線模型的參數(shù)方程：

2 自動(dòng)路徑規(guī)劃算法

2.1 傳統(tǒng)A＊算法

A*算法，全稱A-Star，一種啟發(fā)式搜索算法，是求解靜態(tài)路網(wǎng)中最短路徑的一種最直接有效的搜索方法。它在搜索過(guò)程中，其搜索方向是通過(guò)一個(gè)評(píng)價(jià)函數(shù)來(lái)確定的，向著終點(diǎn)開(kāi)始搜尋。它是將已知的迭代步數(shù)及從初始狀態(tài)或者當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的費(fèi)用信息作為評(píng)價(jià)量度，計(jì)算每一個(gè)節(jié)點(diǎn)的開(kāi)銷值，并將其添加到一個(gè)open_set集合中，選取開(kāi)銷最小的相鄰節(jié)點(diǎn)作為下一個(gè)延伸節(jié)點(diǎn)，直至目標(biāo)節(jié)點(diǎn)添加到該open_set集合中。然后通過(guò)回溯關(guān)系找到滿足約束條件的最優(yōu)解。利用A*算法進(jìn)行RF航段自動(dòng)路徑規(guī)劃時(shí)，在考慮地形障礙物限制條件和最少迭代步數(shù)條件下，盡可能地找出每一個(gè)最佳狀態(tài)，根據(jù)每個(gè)最佳狀態(tài)確定最終規(guī)劃得到的最優(yōu)RF航段。

航空器在復(fù)雜地形區(qū)域進(jìn)行路徑規(guī)劃時(shí)，除障礙物與障礙物邊緣以外的區(qū)域都可看作是可行搜索空間。

航空器從航段起始點(diǎn)start搜尋至航段的終點(diǎn)end的過(guò)程中，引入當(dāng)前節(jié)點(diǎn)i的評(píng)價(jià)函數(shù)f*(i)=g(i)+h*(i)，這里g(i)表示從起始點(diǎn)至當(dāng)前節(jié)點(diǎn)i所消耗的實(shí)際費(fèi)用，h*(i)則表示從節(jié)點(diǎn)i至終點(diǎn)所消耗的實(shí)際費(fèi)用大小的估計(jì)，且其必須小于節(jié)點(diǎn)i到終點(diǎn)的實(shí)際最小費(fèi)用，其中g(shù)(i)和h*(i)選取曼哈頓距離來(lái)度量消耗的費(fèi)用大小。規(guī)劃算法主要步驟：

（1）定義兩個(gè)列表集合open_set=set（）、closed_set=set（），其中open_set集合用于存儲(chǔ)已經(jīng)遍歷過(guò)的節(jié)點(diǎn)，未被尚未遍歷的節(jié)點(diǎn)則存儲(chǔ)進(jìn)closed_set集合。

（2）從open_set集合中選取出開(kāi)銷費(fèi)用最小的節(jié)點(diǎn)，并將其添加進(jìn)closed_set集合，同時(shí)再將與該添加節(jié)點(diǎn)周圍相鄰的節(jié)點(diǎn)也一起加入至closed_set集合中。

（3）在步驟（2）完成后，更新open_set集合中起始節(jié)點(diǎn)至每一個(gè)節(jié)點(diǎn)之間的開(kāi)銷花費(fèi)，以及每一個(gè)節(jié)點(diǎn)至目標(biāo)點(diǎn)的開(kāi)銷花費(fèi)。

（4）判斷目標(biāo)點(diǎn)是否被添加至open_set集合，如果被添加，則完成搜尋。反之，則重復(fù)步驟（2）和步驟（3），直至目標(biāo)點(diǎn)被添加進(jìn)open_set集合，算法結(jié)束。

2.2 算法改進(jìn)

針對(duì)傳統(tǒng)A*算法在搜尋過(guò)程中存在計(jì)算量大、效率低、內(nèi)存空間耗費(fèi)嚴(yán)重以及搜索路徑不唯一等缺陷，考慮通過(guò)改進(jìn)評(píng)價(jià)函數(shù)計(jì)算方式并結(jié)合動(dòng)態(tài)多路徑規(guī)劃算法對(duì)傳統(tǒng)的A*算法進(jìn)行改進(jìn)。

（1）評(píng)價(jià)函數(shù)的改進(jìn)方式。評(píng)價(jià)函數(shù)作為A*搜索算法中很重要的一個(gè)函數(shù)，其對(duì)算法的效率優(yōu)化起著重大作用。針對(duì)原有算法計(jì)算量大、效率低的情況，通過(guò)改進(jìn)評(píng)價(jià)函數(shù)優(yōu)化程序運(yùn)行效率。傳統(tǒng)的A*算法通常采用的是曼哈頓距離或者歐氏距離作為度量標(biāo)準(zhǔn)，然而由于事先定義航空器的運(yùn)動(dòng)方向?yàn)?個(gè)方向，從而導(dǎo)致規(guī)劃得到的路徑不滿足曼哈頓距離或歐氏距離計(jì)算結(jié)果?？紤]通過(guò)引入一個(gè)協(xié)方差矩陣S，將原有的歐氏距離進(jìn)行變換：

式中，i、j均是屬于1至n的正整數(shù)；向量xi為向量xj對(duì)應(yīng)的均值。

因此，改進(jìn)后的評(píng)價(jià)函數(shù)為：

式（7）中，C表示在搜尋過(guò)程中每移動(dòng)一小方格的路徑開(kāi)銷。

（2）動(dòng)態(tài)多路徑規(guī)劃策略下的改進(jìn)。針對(duì)傳統(tǒng)A*算法在搜尋過(guò)程中存在搜尋路徑不唯一的情形，考慮在A*算法中融合動(dòng)態(tài)多路徑規(guī)劃策略，它是在算法中通過(guò)引入重復(fù)路徑懲罰因子，然后對(duì)在搜尋到的航段起點(diǎn)start和目標(biāo)點(diǎn)end之后得到多條路徑通行代價(jià)與目標(biāo)路徑相似度之間取得相對(duì)最優(yōu)的動(dòng)態(tài)優(yōu)化路徑。其算法的主要思想為：首先利用上一節(jié)的自動(dòng)路徑規(guī)劃算法搜索出n條可行路徑，再將n條路徑上每一個(gè)節(jié)點(diǎn)的通行代價(jià)都乘以一個(gè)懲罰因子，然后分別將n條路徑相似度與目標(biāo)路徑的相似度進(jìn)行對(duì)比，取相似比最接近于1的那條路徑即為最優(yōu)動(dòng)態(tài)路徑。相似度計(jì)算公式如下：

圖2動(dòng)態(tài)多路徑規(guī)劃策略下改進(jìn)流程

2.3 路徑平滑處理

利用Python根據(jù)改進(jìn)后A*算法搜尋得到路徑，由于在某些點(diǎn)處出現(xiàn)了較大的曲折，考慮利用佛洛依德法[9]對(duì)擬合得到的航段路徑進(jìn)行平滑處理，使得處理后的航段路徑滿足要求。

3 仿真驗(yàn)證及結(jié)果分析

以深圳機(jī)場(chǎng)RWY34的一條進(jìn)場(chǎng)程序?yàn)槔?，RF航段起始點(diǎn)為SZ951，終點(diǎn)為SZ950，圓心為RSZ45，圓心角取30°，轉(zhuǎn)彎半徑為2.1 NM，航空器垂直下降率通常取300 ft/min，在地形障礙物約束下進(jìn)行路徑自動(dòng)搜尋。圖3為考慮地形障礙物后，按限制要求搜索產(chǎn)生的一條RF航段。

圖3改進(jìn)A*算法規(guī)劃得到RF航段

為進(jìn)一步驗(yàn)證改進(jìn)后算法的可行性，分別對(duì)A*算法、改進(jìn)A*算法和遺傳算法進(jìn)行仿真分析。結(jié)果如表1所示。

表1改進(jìn)的A*算法性能對(duì)比分析

結(jié)果表明，在搜尋花費(fèi)時(shí)間方面，改進(jìn)的A*算法相對(duì)于遺傳算法減少了20.54 s，相對(duì)A*算法減少了6.17 s；在航段長(zhǎng)度方面，改進(jìn)的A*算法與遺傳算法搜尋獲得結(jié)果相比遺傳算法減少了0.06 NM，相比A*算法更是減少了0.25 NM；在最優(yōu)開(kāi)銷代價(jià)方面，改進(jìn)A*算法雖然明顯優(yōu)于A*算法，但是相比遺傳算法增加了6%的開(kāi)銷。

4 結(jié)語(yǔ)

以深圳機(jī)場(chǎng)為研究對(duì)象，其仿真結(jié)果表明，在滿足RF航段限制條件及規(guī)章規(guī)定的越障要求的情況下，改進(jìn)A*算法實(shí)現(xiàn)了從起始定位點(diǎn)至目標(biāo)定位點(diǎn)之間RF航段路徑自動(dòng)規(guī)劃，將其與現(xiàn)有的RF航段作對(duì)比，結(jié)果大致相同，驗(yàn)證所設(shè)計(jì)RF航段飛行曲線模型及自動(dòng)路徑規(guī)劃算法的可行性與合理性。

在實(shí)際RF航段的設(shè)計(jì)與規(guī)劃過(guò)程中，應(yīng)用改進(jìn)的自動(dòng)路徑規(guī)劃算法，在滿足航段設(shè)計(jì)約束情形下，能夠快速地規(guī)劃出一條RF航段，減小了設(shè)計(jì)人員的工作量，提高了設(shè)計(jì)效率。