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

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

0 引言

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

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

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

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

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

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

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

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

式中，a表示單位長度代價，即柵格的邊長。D表示目的點，i表示路徑上某點。

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

1）令 S∈OPEN，CLOSED=φ；

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

3）若OPEN表不為空，則將OPEN表中第1個頂點n1移入CLOSED表；

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

5）若n1不為終點，則對n1周圍鄰節(jié)點nj（j≤m，j≠i）進行擴展，判斷其是否存在于OPEN表和CLOSED表中，并計算F（nj）值；

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

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

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

6）根據F（nj）大小對OPEN表中頂點進行升序排列，之后再返回步驟2）。流程圖如下頁圖1所示。

2 基于“追蹤”思想的改進A＊算法

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

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

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

1）飛機始終以速度v1勻速飛行；

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

3）飛機具有自動導航系統(tǒng)和較強的運算能力。

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

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

2）對于初始航跡中方向變化的柵格采用追蹤模型。柵格的中心點，即航跡轉折點為假定動態(tài)目標，飛機駛入該柵格后，其速度方向時刻指向該動態(tài)目標，并在動態(tài)目標駛出該柵格時追上目標；

3）當飛機到達航跡方向變化的柵格時，激活柵格中心點，此時該動態(tài)目標將以速度vi（i=A，B，C，D）沿初始航跡勻速向下一個柵格前進，并在即將駛出柵格時被飛機追上，此時飛機的轉彎航跡是一條光滑的追蹤曲線。

按照目標點移動方向與坐標軸的關系將追蹤模型分為水平追蹤、斜向追蹤和豎直追蹤3種模型，如圖2所示。

根據以上基本假設和追蹤策略，以水平追蹤為例構建如下模型：

飛機進入新的柵格時與其邊界交于C（a1-a/2，a2-a/2），此時目標 D（a1，a2）以勻速 vD向 E（a1+a/2，a2）移動。假設 t時刻，飛機行駛至（x，y）點，此點軌跡切線與 DE 交于點 F（a1+v0t，a2），如圖 3 所示。

根據假設可知：

此外，（x，y）點切線滿足以下斜率：

結合式（4）和式（5）可得：

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

化簡式（8），可得飛行航跡的解析表達式如下所示：

2.2 改進A＊算法的基本流程

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

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

2）令指針指向CLOSED表當前節(jié)點；

3）連接當前節(jié)點與下一節(jié)點；

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

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

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

7）若沒有指向終點，則返回步驟3）。

改進A*算法主要鑲嵌到航跡生成模塊，其相應流程圖如圖4所示。

3 仿真分析

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

其中黑色方框代表障礙區(qū)域，藍色實線代表傳統(tǒng)A*算法得到的初始航跡，紅色曲線代表轉彎處改進航跡?？梢钥闯龈倪MA*算法對飛行航跡作了優(yōu)化處理，經計算改進航跡比初始航跡節(jié)省航程約18.69 km，占初始航跡航程的1.15%。

進一步以“西安-上?！薄ⅰ爸貞c-濟南”、“鄭州 - 杭州”、“昆明 - 合肥”、“南京 - 北京”、“廣州 -上?！?條航線的航班為例進行仿真，其結果如下頁圖6所示。

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

表1 各組仿真結果

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

4 結論

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