任思潛,吳娟
(中國(guó)民用航空飛行學(xué)院飛行技術(shù)學(xué)院,廣漢618307)
現(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*算法。
為了能夠在復(fù)雜地形條件下找出一條符合實(shí)際的RF航段,需要從被搜索空間的地形中獲取地形信息及障礙物信息,如圖1所示。研究考慮采用余弦相似度法進(jìn)行障礙物特征信息提取[6-7],提取的障礙物信息如下:
式中,(Xi,Yi)則為第i個(gè)障礙物的中心坐標(biāo);Zi是障礙物參數(shù),表示其高度;i表示障礙物的數(shù)量。
圖1障礙物特征信息提取
根據(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之間的差值。
根據(jù)RF航段的特征,列出RF航段飛行曲線模型的參數(shù)方程:
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é)束。
針對(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)流程
利用Python根據(jù)改進(jìn)后A*算法搜尋得到路徑,由于在某些點(diǎn)處出現(xiàn)了較大的曲折,考慮利用佛洛依德法[9]對(duì)擬合得到的航段路徑進(jìn)行平滑處理,使得處理后的航段路徑滿足要求。
以深圳機(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)銷。
以深圳機(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ì)效率。