基于改進(jìn)A*算法的航跡規(guī)劃設(shè)計(jì)研究*

鄭煜坤，王 瑛，呂茂隆，李正欣

（空軍工程大學(xué)裝備管理與安全工程學(xué)院，西安 710051）

0 引言

航跡規(guī)劃是飛機(jī)在執(zhí)行飛行任務(wù)前需要做的極其重要的一項(xiàng)工作。合理的航跡規(guī)劃可提高飛機(jī)執(zhí)行飛行任務(wù)的效率，縮短飛行航程，減少油耗代價(jià)，增強(qiáng)飛機(jī)安全性。我國(guó)空域存在大量“危險(xiǎn)區(qū)”、“禁飛區(qū)”和“限制區(qū)”[1]，在航跡規(guī)劃時(shí)，必須要考慮“三區(qū)”規(guī)避問(wèn)題，減少飛行成本，降低飛行風(fēng)險(xiǎn)。

目前常用的航跡規(guī)劃算法主要有遺傳算法、蟻群算法和A*算法等。遺傳算法能夠解決復(fù)雜背景下的航跡規(guī)劃問(wèn)題，魯棒性較強(qiáng)，但其編碼難度大、搜索時(shí)間長(zhǎng)。蟻群算法采用正反饋、分布式協(xié)作的策略，但其信息素的相關(guān)規(guī)則難以設(shè)定[2]。A*算法是一種啟發(fā)式搜索算法，編碼簡(jiǎn)潔，容易實(shí)現(xiàn)，能夠解決民航航跡規(guī)劃中的“三區(qū)”規(guī)避問(wèn)題[3]。文獻(xiàn)[4]采用離線(xiàn)航跡規(guī)劃和在線(xiàn)航跡規(guī)劃的思想，減少了算法在線(xiàn)運(yùn)行時(shí)間，降低了A*算法的信息存儲(chǔ)量。文獻(xiàn)[5]采用雙向A*算法提高搜索效率、減少搜索時(shí)間。文獻(xiàn)[6]將飛行器的機(jī)動(dòng)約束和燃油約束添加到代價(jià)函數(shù)中，減少了搜索的節(jié)點(diǎn)數(shù)，提高了算法運(yùn)行效率。文獻(xiàn)[7-8]提出了一種改進(jìn)A*算法的無(wú)人機(jī)航跡規(guī)劃方法，實(shí)現(xiàn)了變方向和變步長(zhǎng)擴(kuò)展節(jié)點(diǎn)。文獻(xiàn)[9]針對(duì)偵察無(wú)人機(jī)航跡規(guī)劃易陷入局部最優(yōu)問(wèn)題，引入“電勢(shì)場(chǎng)”理論，將威脅源視為帶電體，提出了一種改進(jìn)的蟻群算法。

然而，上述文獻(xiàn)多是針對(duì)復(fù)雜環(huán)境條件下的無(wú)人機(jī)航跡規(guī)劃，其關(guān)注點(diǎn)主要是算法的運(yùn)行時(shí)間和收斂速度。在民用航空領(lǐng)域，則更關(guān)注飛行安全和飛行成本，即在保證飛機(jī)運(yùn)行穩(wěn)定的條件下實(shí)現(xiàn)最優(yōu)航跡規(guī)劃。不同于無(wú)人飛行器，民用飛機(jī)具有體積大、飛行阻力大以及靈活性差等特點(diǎn)，因此，其轉(zhuǎn)彎半徑和過(guò)載要求更為嚴(yán)格[10]。利用傳統(tǒng)A*算法得出的飛機(jī)飛行航跡均為“折線(xiàn)航跡”，未考慮大型民航客機(jī)的機(jī)動(dòng)性和安全性，增大了轉(zhuǎn)彎處飛行航程，增加了飛行成本，難以滿(mǎn)足實(shí)際飛行需求。

結(jié)合導(dǎo)彈的目標(biāo)指示型追蹤方法，根據(jù)民航客機(jī)實(shí)際，忽略導(dǎo)彈追蹤過(guò)程中的復(fù)雜機(jī)動(dòng)動(dòng)作和多維追蹤曲線(xiàn)，僅采納其追蹤策略，本文提出了一種改進(jìn)的A*算法，采用水平、豎直和斜向3種追蹤模式，將“折線(xiàn)航跡”優(yōu)化為“光滑曲線(xiàn)航跡”，保證了優(yōu)化后航跡的平滑性和可實(shí)現(xiàn)性，減少了飛機(jī)飛行距離。

1 傳統(tǒng)A＊算法基本原理

傳統(tǒng)A*算法基于啟發(fā)型搜索函數(shù)建立，具有快速、高效、準(zhǔn)確的特點(diǎn)，在機(jī)器人路徑尋優(yōu)和路線(xiàn)規(guī)劃等領(lǐng)域有著廣泛的應(yīng)用[11]。根據(jù)不同的搜索任務(wù)，可以采取有針對(duì)性的代價(jià)函數(shù)。在最短路徑尋優(yōu)過(guò)程中，A*算法的代價(jià)函數(shù)如式（1）所示：

其中，F(xiàn)（ni）表示當(dāng)前節(jié)點(diǎn)i的代價(jià)總和，F(xiàn)（ni）的值越小，說(shuō)明經(jīng)過(guò)i點(diǎn)到達(dá)終點(diǎn)的代價(jià)越小，i點(diǎn)越有價(jià)值；G（ni）表示“既定代價(jià)”，指起始點(diǎn)到i點(diǎn)的已耗代價(jià)值；H（ni）表示“估算代價(jià)”，指自i點(diǎn)到達(dá)終點(diǎn)需要付出的可能代價(jià)值。

啟發(fā)公式H（ni）是決定A*算法運(yùn)算效率和精確性的關(guān)鍵函數(shù)，當(dāng)H（ni）=0時(shí)，F(xiàn)（ni）=G（ni），該算法就會(huì)變成靜態(tài)條件下的路徑尋優(yōu)問(wèn)題。通常情況下，使用兩點(diǎn)之間的距離表示代價(jià)函數(shù)[12]，其表達(dá)式如式（2）所示：

式中，a表示單位長(zhǎng)度代價(jià)，即柵格的邊長(zhǎng)。D表示目的點(diǎn)，i表示路徑上某點(diǎn)。

為詳細(xì)說(shuō)明傳統(tǒng)A*算法的搜索流程，給出以下規(guī)范：搜索區(qū)域包括m個(gè)柵格，其中S點(diǎn)為起點(diǎn)，D點(diǎn)為終點(diǎn)，i為當(dāng)前點(diǎn)；OPEN表用于存放未考察點(diǎn)，即當(dāng)前點(diǎn)i的可達(dá)點(diǎn)，CLOSED表用于存放已考察點(diǎn)；F（ni）表示i點(diǎn)的代價(jià)函數(shù)。A*算法的具體流程如下：

1）令 S∈OPEN，CLOSED=φ；

2）判斷OPEN表是否為空，若為空，則不存在最短路徑；

3）若OPEN表不為空，則將OPEN表中第1個(gè)頂點(diǎn)n1移入CLOSED表；

4）判斷n1是否為終點(diǎn)，若為終點(diǎn)，則搜索成功，按追溯法畫(huà)出最優(yōu)航跡；

5）若n1不為終點(diǎn)，則對(duì)n1周?chē)徆?jié)點(diǎn)nj（j≤m，j≠i）進(jìn)行擴(kuò)展，判斷其是否存在于OPEN表和CLOSED表中，并計(jì)算F（nj）值；

① 若 nj?（OPEN∪CLOSED），則令 nj∈OPEN，設(shè)置父節(jié)點(diǎn)為n1；

②若nj∈OPEN，則更新F（nj），取較小值并設(shè)置父節(jié)點(diǎn)為n1；

③若nj∈CLOSED或nj是障礙點(diǎn)則舍棄，返回步驟5）選擇其他鄰節(jié)點(diǎn)；

6）根據(jù)F（nj）大小對(duì)OPEN表中頂點(diǎn)進(jìn)行升序排列，之后再返回步驟2）。流程圖如下頁(yè)圖1所示。

2 基于“追蹤”思想的改進(jìn)A＊算法

針對(duì)傳統(tǒng)A*算法的弊端，引入導(dǎo)彈追蹤模型對(duì)折線(xiàn)路徑進(jìn)行優(yōu)化并使用柵格法表示出來(lái)。柵格法是指用尺寸相同的正方形柵格將飛行空域分解為一系列網(wǎng)格單元[13]，并將網(wǎng)格與平面坐標(biāo)系結(jié)合，構(gòu)成柵格坐標(biāo)網(wǎng)。

2.1 建立追蹤數(shù)學(xué)模型

導(dǎo)彈追蹤模型采用目標(biāo)指示追蹤方式，在追蹤過(guò)程中自動(dòng)導(dǎo)航系統(tǒng)指引導(dǎo)彈時(shí)刻瞄準(zhǔn)目標(biāo)[14]。在飛機(jī)航跡規(guī)劃問(wèn)題中，為將“折線(xiàn)航跡”優(yōu)化為“曲線(xiàn)航跡”，可以在折線(xiàn)處將飛機(jī)類(lèi)比為導(dǎo)彈，將柵格中心點(diǎn)類(lèi)比為目標(biāo)，并作出以下基本假設(shè)。

1）飛機(jī)始終以速度v1勻速飛行；

2）飛行全程高度保持不變，忽略起飛降落階段帶來(lái)的高度變化；

3）飛機(jī)具有自動(dòng)導(dǎo)航系統(tǒng)和較強(qiáng)的運(yùn)算能力。

此外，為確保飛行航跡能最終指向目的地，需提出以下追蹤策略：

1）利用傳統(tǒng)A*算法得出初始航跡并在柵格坐標(biāo)網(wǎng)中表示；

2）對(duì)于初始航跡中方向變化的柵格采用追蹤模型。柵格的中心點(diǎn)，即航跡轉(zhuǎn)折點(diǎn)為假定動(dòng)態(tài)目標(biāo)，飛機(jī)駛?cè)朐摉鸥窈螅渌俣确较驎r(shí)刻指向該動(dòng)態(tài)目標(biāo)，并在動(dòng)態(tài)目標(biāo)駛出該柵格時(shí)追上目標(biāo)；

3）當(dāng)飛機(jī)到達(dá)航跡方向變化的柵格時(shí)，激活柵格中心點(diǎn)，此時(shí)該動(dòng)態(tài)目標(biāo)將以速度vi（i=A，B，C，D）沿初始航跡勻速向下一個(gè)柵格前進(jìn)，并在即將駛出柵格時(shí)被飛機(jī)追上，此時(shí)飛機(jī)的轉(zhuǎn)彎航跡是一條光滑的追蹤曲線(xiàn)。

按照目標(biāo)點(diǎn)移動(dòng)方向與坐標(biāo)軸的關(guān)系將追蹤模型分為水平追蹤、斜向追蹤和豎直追蹤3種模型，如圖2所示。

根據(jù)以上基本假設(shè)和追蹤策略，以水平追蹤為例構(gòu)建如下模型：

飛機(jī)進(jìn)入新的柵格時(shí)與其邊界交于C（a1-a/2，a2-a/2），此時(shí)目標(biāo) D（a1，a2）以勻速 vD向 E（a1+a/2，a2）移動(dòng)。假設(shè) t時(shí)刻，飛機(jī)行駛至（x，y）點(diǎn)，此點(diǎn)軌跡切線(xiàn)與 DE 交于點(diǎn) F（a1+v0t，a2），如圖 3 所示。

根據(jù)假設(shè)可知：

此外，（x，y）點(diǎn)切線(xiàn)滿(mǎn)足以下斜率：

結(jié)合式（4）和式（5）可得：

聯(lián)立式（4）～式（6）可得到飛機(jī)飛行航跡方程為：

化簡(jiǎn)式（8），可得飛行航跡的解析表達(dá)式如下所示：

2.2 改進(jìn)A＊算法的基本流程

傳統(tǒng)A*算法采用追溯法獲取飛行航跡[15]，如圖1虛線(xiàn)框所示。但是，由于子節(jié)點(diǎn)只能向著8個(gè)方向拓展，因此，轉(zhuǎn)向角只能是45°或90°，與實(shí)際航跡不符且增大航程。改進(jìn)A*算法針對(duì)追溯法缺陷，提出基于追蹤模型的航跡生成規(guī)則。其具體流程如下：

1）根據(jù)傳統(tǒng)A*算法求得完整CLOSED表；

2）令指針指向CLOSED表當(dāng)前節(jié)點(diǎn)；

3）連接當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)；

4）判斷航跡方向是否發(fā)生變化，若變化，則采取相應(yīng)的追蹤模型優(yōu)化航跡，然后移動(dòng)指針令其指向下一節(jié)點(diǎn)；

5）若未發(fā)生變化，則直接移動(dòng)指針到下一節(jié)點(diǎn)；

6）判斷指針是否指向終點(diǎn)。若是，則航跡優(yōu)化結(jié)束；

7）若沒(méi)有指向終點(diǎn)，則返回步驟3）。

改進(jìn)A*算法主要鑲嵌到航跡生成模塊，其相應(yīng)流程圖如圖4所示。

3 仿真分析

中國(guó)航路網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，網(wǎng)絡(luò)內(nèi)部存在大量“三區(qū)”，為了保證民航飛行的安全順暢，需對(duì)“三區(qū)”空域進(jìn)行避讓[1]。與文獻(xiàn)[3，14]一樣，為驗(yàn)證改進(jìn)A*算法的優(yōu)越性將飛機(jī)模型作為質(zhì)點(diǎn)來(lái)處理，忽略其微觀飛行姿態(tài)。以“成都-北京”航班航跡為例進(jìn)行仿真，選擇1 210 km×1 110 km的區(qū)域，設(shè)置柵格邊長(zhǎng)為50.45 km，則得到24×22的柵格網(wǎng)，仿真結(jié)果如圖5所示。

其中黑色方框代表障礙區(qū)域，藍(lán)色實(shí)線(xiàn)代表傳統(tǒng)A*算法得到的初始航跡，紅色曲線(xiàn)代表轉(zhuǎn)彎處改進(jìn)航跡。可以看出改進(jìn)A*算法對(duì)飛行航跡作了優(yōu)化處理，經(jīng)計(jì)算改進(jìn)航跡比初始航跡節(jié)省航程約18.69 km，占初始航跡航程的1.15%。

進(jìn)一步以“西安-上?！?、“重慶-濟(jì)南”、“鄭州 - 杭州”、“昆明 - 合肥”、“南京 - 北京”、“廣州 -上海”6條航線(xiàn)的航班為例進(jìn)行仿真，其結(jié)果如下頁(yè)圖6所示。

由圖6可以看出對(duì)于跨越“三區(qū)”密集分布且航程較遠(yuǎn)的航班，改進(jìn)A*算法能有效優(yōu)化其初始航跡，縮短飛機(jī)飛行距離，規(guī)避禁飛區(qū)域，實(shí)現(xiàn)了二維準(zhǔn)確快速航跡規(guī)劃，各航班仿真結(jié)果如表1所示。

表1 各組仿真結(jié)果

由表1可知改進(jìn)A*算法相對(duì)于傳統(tǒng)A*算法的運(yùn)行時(shí)間更少，規(guī)劃航程更短，提高了遠(yuǎn)距航班的飛行安全和效率。

4 結(jié)論

本文對(duì)民航飛行航跡進(jìn)行研究，針對(duì)傳統(tǒng)A*算法難以規(guī)劃出符合實(shí)際轉(zhuǎn)彎需求的飛行航跡問(wèn)題，提出了一種基于“追蹤”思想的改進(jìn)A*算法，該算法有效縮短了飛行航程，同時(shí)能夠?qū)︼w行過(guò)程中所遇威脅進(jìn)行規(guī)避，實(shí)現(xiàn)二維準(zhǔn)確快速航跡規(guī)劃。最后，對(duì)“北京-成都”等7條航線(xiàn)的航班進(jìn)行仿真，驗(yàn)證了所提方法的有效性，為我國(guó)民用航空航跡規(guī)劃提供了一種重要參考。