融合動態風險圖和改進A^*算法的動態改航規劃

李海 郭水林 周曄

摘要：結合機載氣象雷達探測信息，本文提出了一種融合動態風險圖和改進A^*算法的動態改航規劃方法。該方法首先利用機載氣象雷達的探測結果，將其進行離散化處理，建立一個定期更新的動態風險圖，以此作為算法的仿真環境；然后，綜合考慮了航跡長度、航跡偏離度和管制約束等因素來構造算法的代價函數，基于該代價函數進行航跡規劃。同時，對A^*算法的搜索方式進行了改進，并對規劃后的航跡進行了平滑優化處理；最后，提出兩種不同策略進行了仿真分析試驗，試驗結果驗證了所提方法的有效性，并且適用于動態改航規劃。

關鍵詞：機載氣象雷達；風險圖；A^*算法；航跡平滑；動態改航

中圖分類號：V355文獻標識碼：ADOI：10.19452/j.issn1007-5453.2021.05.009

目前，國內外在航跡規劃方面的研究主要分為飛行前航跡規劃和實時航跡規劃[1]。參考文獻[2]、參考文獻[3]運用傳統規劃算法對飛行航跡進行規劃，為解決傳統算法易陷入局部最優的問題，對算法進行了改進，但是規劃后的航跡不夠平滑。參考文獻[4]～參考文獻[6]采用智能仿生學算法進行航跡規劃，此類算法具有容易實現、魯棒性強等優勢，但算法的計算量大，而且無法保證所規劃的航跡是全局最優的航跡。參考文獻[7]、參考文獻[8]結合了圖形學的規劃方法，規劃過程直觀，而且能夠兼顧規劃時間和航跡質量，但算法復雜度隨著危險區域增多時提升，因此不適用于復雜的危險氣象場景。A^*算法[9-10]作為一種啟發式搜索算法，在應用于復雜的氣象環境場景下時，可能會出現搜索陷入死循環無法跳出，以及規劃后的航跡不夠平滑。

綜上所述，目前關于航跡規劃的研究大多數都沒有利用機載氣象雷達的探測信息，在這種情況下，規劃的航跡就容易產生冗余的繞飛距離，導致無謂的航油消耗。機載氣象雷達作為民航飛機的“雙眼”，能夠實時探測飛行航路前方的危險氣象，為飛行員繞飛策略的制定提供了最直接的先驗信息。現行的機載氣象雷達采用的是單極化雷達，單極化雷達發射時發射垂直或水平單一極化信號，接收時接收同一單一極化的雷達回波信號，目標在單極化雷達照射下只受垂直或水平單一極化電磁波激勵。因此，單極化雷達僅能通過雷達反射率對降水目標的含水量予以檢測，并用不同的顏色來表示不同的降水等級，并不具備降水粒子區分的功能[11]。而作為下一代的機載氣象雷達——雙極化雷達，能夠同時接收目標雷達回波信號的同極化和交叉極化分量。因此，雙極化雷達能夠對降雨粒子進行精確的分類[12]，揭示各種降水系統中小雨滴、大雨滴、霰、冰雹、雪花、冰晶等多種水凝物粒子的分布，為飛行員繞飛策略的制定提供了更加精確的先驗信息。

本文利用機載氣象雷達的探測結果，并結合改進A^*算法，提出了一種融合動態風險圖和改進A^*算法的動態改航規劃方法。首先，在改航約束條件下，根據機載氣象雷達的探測結果對空域進行離散化處理，建立一個飛行區域初始化風險圖，并利用實時得到的機載氣象雷達的探測結果對初始化風險圖進行定期更新，得到一個動態風險圖，以此作為改進A^*算法的搜索環境。然后，對傳統A^*算法的代價函數和搜索方式（即航跡規劃）進行了改進，并增加了航跡平滑優化處理。最后，從航油消耗、經濟環保、空域利用率等角度考慮，對雷達回波強度小于41dBZ的危險區域提出了保守策略和非保守策略[13]的兩種不同規避策略，并設計了本文方法與A^*算法、蟻群算法、遺傳算法和人工勢場算法[14]，以及與基于改進人工勢場法的動態改航規劃[2]、基于改進多目標粒子群算法的航空器改航研究[4]、利用自適應擴展節點的A^*算法對改航路徑規劃進行求解[15]的對比仿真試驗。試驗結果表明，本文方法規劃的航跡能夠安全有效地規避危險氣象，并且優于A^*算法、蟻群算法、遺傳算法、人工勢場算法、改進人工勢場算法、改進對目標粒子群算法和自適應擴展節點的A^*算法。

1整體框架

融合動態風險圖和改進A^*算法的動態改航規劃方法主要由兩部分組成：動態風險圖和改進A^*算法。首先，根據機載氣象雷達的探測結果對空域進行離散化處理得到一個風險矩陣，根據風險矩陣建立一個飛行區域初始化風險圖，并利用實時得到的機載氣象雷達探測結果對初始化風險圖進行定期更新，得到一個動態風險圖，以此作為改進A^*算法的搜索環境。然后，對傳統A^*算法的代價函數和搜索方式進行改進，并對規劃后的航跡進行了平滑優化處理。改進A^*算法分為代價函數設計、航跡規劃和航跡平滑優化三部分。所提方法的整體框架如圖1所示。

在圖1中，本文中設定風險圖的定期更新時間為5min[16]，每隔5min利用改進A^*算法對動態風險圖進行航跡規劃。

2動態風險圖

機載氣象雷達的最大探測距離是600km，運輸航空完成一次轉彎至少需要7.4km[1]。因此，將機載氣象雷達的探測結果進行離散化處理，針對不同的危險氣象類型進行數字化風險評估[17]，數字化風險評估表見表1。為簡化模型，并保證航空器能在一個單元格內順利執行一次轉彎，選取距離為15km作為一個單元格的邊長，則可以得到一個M×N的探測結果矩陣，其中M=40，N=40。為簡單起見，本文只考慮航空器的巡航階段，因為對于起飛和進近階段也可以進行類似的考慮。

假設某一時刻得到的機載氣象雷達的探測結果經過離散化處理后得到的探測結果矩陣見表2。

利用表1的數字化風險評估表并結合雷達探測的回波強度，對表2的機載氣象雷達探測結果矩陣進行數字化風險評估，并進行歸一化處理，得到一個M×N的風險矩陣，見表3，表中的不同數值表示不同危險氣象類型的數字化評估結果。

（3）危險區域限制

通常情況對于航空器來說，當雷達回波強度大于等于41dBZ的危險區域，不允許航空器穿越飛行，必須采取規避策略。

（4）改航點數量限制

為減少導航誤差，避免過度增加飛行員和管制員在實施改航過程中的工作負荷，航空器在遠距離飛行時一般不希望迂回行進和頻繁的轉彎，改航點數量每100km應不多于1個。

（5）危險系數設置

在規避危險氣象的過程中，根據選擇策略[20]的不同可設置相應的規避危險系數T（0≤T≤1）。在保守策略下，設置的危險系數T=0；在非保守策略下可設置不同的危險系數T，需要注意的是設置的T越大，則規避的危險系數越高。

3.2.2正向擴展式搜索

首先，初始化截距d=3，并將飛行區域I內風險系數Fx，y> T的單元格點設置為非可行單元格點（路障點）。其次，通過代價函數在A（3）內進行搜索，當搜索陷入死區（被路障點包圍，算法無法自動跳出的區域）時，則基于當前單元格點，在其相鄰單元格點中隨機選取未被遍歷的可行單元格點繼續搜索。此時，當搜索到達改航終點時，則停止搜索，輸出搜索得到的單元格點集合；否則，判定A（3）內無法通行。然后，增大d值，基于A（3）約束邊界上被遍歷過的單元格點，隨機選擇其在A（6）內的相鄰可行單元格點繼續搜索（搜索區域包含A（6）和A（3））。此時，如果沒有搜索到達改航終點，則繼續增大d值，基于A（6）約束邊界上被遍歷過的單元格點，隨機選擇其在A（9）內的相鄰可行單元格點繼續搜索，并依此類推，直到A（3n）搜索到達改航終點為止。在增大d值進行搜索的過程中，如果d > N時還沒有搜索到達改航終點，則判定該飛行區域在當前危險系數T值下，航空器無法穿越飛行，搜索結束。對于飛行區域II的搜索操作同飛行區域I一樣，在此就不再贅述。正向擴展式搜索的具體流程圖如圖5所示。

正式擴展式搜索結果存在以下三種可能。

情況1：飛行區域I和飛行區域II僅有一個區域能夠搜索到達改航終點。此時，選擇能夠搜索到達改航終點的飛行區域，并獲得該區域內搜索得到的單元格點集合。

情況2：飛行區域I和飛行區域II都搜索到達改航終點。此時，根據機載氣象雷達的探測結果選擇危險氣象分布比較稀疏且危險氣象的風險系數比較小的飛行區域，并獲得該區域內搜索得到的單元格點集合。

情況3：飛行區域I和飛行區域II都沒有搜索到達改航終點，則判定當前危險系數T值下航空器無法穿越飛行。此時，飛行員可以考慮在保證飛行安全的情況下，適當增大T值重新進行航跡規劃，或者采取其他策略（如就地備降、上升飛行高度、降低飛行高度等）。

3.4算法流程

改進A^*算法的主要步驟如下：（1）利用機載氣象雷達的探測結果建立當前飛行區域風險圖；（2）根據選擇的規避策略，設置不同的危險系數T；（3）將風險圖中大于危險系數T的單元格點設置為路障點；（4）在計劃航跡兩側進行正向擴展式搜索；（5）利用最小二乘法對正向擴展式搜索得到的單元格點集合進行優化篩選；（6）對優化篩選出來的單元格點進行逆序搜索；（7）航跡平滑優化處理；（8）輸出最優的航跡。改進A^*算法的流程圖如圖7所示。

4仿真分析

對本文方法進行仿真分析。試驗1在簡單氣象環境下，本文方法和A^*算法進行對比仿真分析；試驗2在復雜氣象環境下，本文方法與蟻群算法、遺傳算法、人工勢場算法[14]、改進人工勢場算法[2]、改進多目標粒子群算法[4]和自適應擴展節點的A^*算法[15]進行對比仿真分析。

試驗1：簡單氣象環境下，模擬仿真試驗數據采用本文中建立動態風險圖的方法構建模擬仿真環境，利用本文方法進行仿真試驗，并與A^*算法進行了對比。圖8是在保守策略下，危險系數T=0，兩種方法的對比仿真結果圖。圖9和圖10是在非保守策略下，危險系數T=0.2和T=0.4，兩種方法的對比仿真結果圖。

航程指航空器從改航起點到改航終點所飛行經過的航跡長度，其公式定義如式（12）所示：

表5為非保守策略下，危險系數T=0.2，本文方法與A^*算法關于上述三個評估指標以及算法運行時間的仿真結果對比數據。

表6為非保守策略下，危險系數T=0.4，本文方法與A^*算法關于上述三個評估指標以及算法運行時間的仿真結果對比數據。

通過表4～表6的試驗對比數據可知，在保守策略下，本文方法在航程上和算法運行時間上都要優于A^*算法，雖然A^*算法在側向偏離度上小于本文方法，但是綜合比較本文方法還是要優于A^*算法；在非保守策略下，當規避策略采取T=0.2和T=0.4時，本文方法算法在航程、側向偏離度、風險值和算法運算時間都要小于A^*算法。綜上所述，本文方法優于A^*算法。

試驗2：復雜氣象環境下，模擬仿真試驗數據采用圖2中的飛行區域風險圖，利用本文方法進行仿真試驗，但由于A^*搜索陷入“死區”而無法得到搜索航跡。在此，采用了蟻群算法、遺傳算法、人工勢場算法、改進人工勢場算法、改進多目標粒子群算法和自適應擴展節點的A^*算法進行了對比仿真試驗。圖11是在保守策略下，當危險系數T=0的對比仿真結果；圖12是在非保守策略下，當危險系數T=0.2的對比仿真結果；圖13是在非保守策略下，當危險系數T=0.4的對比仿真結果。

為定量評估本文方法規劃的航跡與蟻群算法、遺傳算法、人工勢場算法、改進人工勢場算法、改進多目標粒子群算法和自適應擴展節點的A^*算法所規劃的航跡的優劣性，同樣采用試驗1中建立的三個評估參數：航程、側向偏離度、風險值，以及算法的運行時間進行對比分析。

表7為保守策略下，危險系數T=0，本文方法、蟻群算法、遺傳算法、人工勢場算法、改進人工勢場算法、改進多目標粒子群算法和自適應擴展節點的A^*算法關于上述三個評估指標以及算法運行時間的仿真結果對比數據。

表8為非保守策略下，危險系數T=0.2，本文方法、蟻群算法、遺傳算法、人工勢場算法、改進人工勢場算法、改進多目標粒子群算法和自適應擴展節點的A^*算法關于上述三個評估指標以及算法運行時間的仿真結果對比數據。

表9為非保守策略下，危險系數T=0.4，本文方法、蟻群算法、遺傳算法、人工勢場算法、改進人工勢場算法、改進多目標粒子群算法和自適應擴展節點的A^*算法關于上述三個評估指標以及算法運行時間的仿真結果對比數據。

從表7可知，在保守策略下，本文方法在航程上除了比改進多目標粒子群算法的要大，比其他方法都小。雖然改進多目標粒子群算法的航程要比本文方法的小，但是這不足以彌補本文方法在側向偏離度和算法運行時間上相對于改進多目標粒子群算法的優勢；從表8可知，在非保守策略T=0.2下，本文方法在航程上除了比改進多目標粒子群算法和自適應擴展節點的A^*算法的要大，比其他方法都小。雖然在航程上改進多目標粒子群算法和自適應擴展A^*算法要比本文方法的更好，但是這不足彌補本文方法在側向偏離度、風險值和算法運行時間上相對于這兩種方法的優勢；從表9可知，在非保守策略T=0.4下，本文方法在航程上除了比人工勢場算法和改進人工勢場算法的要大，比其他方法都小。雖然在航程上人工勢場算法和改進人工勢場算法要比本文方法的小，但是這不足彌補本文方法在側向偏離度、風險值和算法運行時間上相對于這兩種方法的優勢。綜上所述，本文方法優于蟻群算法、遺傳算法、人工勢場算法、改進人工勢場算法、改進多目標粒子群算法和自適應擴展節點的A^*算法。

5結論

本文提出了一種融合風險圖和改進A^*算法的動態改航規劃方法。首先，利用機載氣象雷達的探測結果建立一個飛行區域初始化風險圖，并利用實時得到的機載氣象雷達的探測結果對初始化風險圖進行定期更新得到一個動態風險圖，以此作為算法的搜索環境。然后，對傳統A^*算法的代價函數和搜索方式進行了改進，并且增加了航跡平滑優化。最后，對改進A^*算法進行仿真試驗，并且還采取了保守策略和非保守策略的兩種規避策略進行飛行航跡規劃，為飛行員安全規避危險氣象提供可選擇的繞飛策略。同時，在簡單氣象環境下，設計了本文方法與A^*算法的對比試驗；在復雜氣象環境下，設計了本文方法與蟻群算法、遺傳算法、人工勢場算法、改進人工勢場算法、改進對目標粒子群算法和自適應擴展節點的A^*算法的對比仿真試驗。并設定了三個定量評估指標和算法運行時間來分析試驗的仿真結果。研究結果表明，本文方法能夠在兩種規避策略下安全有效地規避危險氣象，并且優于A^*算法、蟻群算法、遺傳算法和人工勢場算法、改進人工勢場算法、改進多目標粒子群算法和自適應擴展節點的A^*算法。

參考文獻

[1]李雄.飛行危險天氣下的航班改航路徑規劃研究[D].南京：南京航空航天大學，2009. Li Xiong. Research on flight diversion route planning in dangerous weather[D]. Nanjing ： Nanjing University of Aeronautics andAstronautics， 2009. （in Chinese）

[2]陳可嘉，陳琳琳.基于改進人工勢場法的動態改航規劃[J].飛行力學，2020，38（5）：84-89. Chen Kejia， Chen Linlin. Dynamic course modification planning based on improved artificial potential field method[J]. Flight Dynamics， 2020，38（5）：84-89.（in Chinese）

[3]李憲強，馬戎，張伸，等.蟻群算法的改進設計及在航跡規劃中的應用[J].航空學報，2020，41（S2）：213-219. Li Xianqiang， Ma Rong， Zhang Shen， et al. Improved design of ant colony algorithm and its application in route planning[J]. Acta Aeronautica et Astronautica Sinica，2020，41（S2）：213-219.（in Chinese）

[4]杜實，王俊凱，任景瑞.基于改進多目標粒子群算法的航空器改航研究[J].安全與環境學報，2020，20（1）：177-185. Du Shi， Wang Junkai， Ren Jingrui. Research on aircraft diversion based on improved multi-objective particleswarm optimization [J]. Journal of Safety and Environment， 2020，20（1）： 177-185. （in Chinese）

[5]李根，李航，張帥陽，等.基于蟻群算法的最優路徑規劃及參數研究[J].中國科技論文，2018，13（16）：1909-1914. Li Gen， Li Hang， Zhang Shuaiyang， et al. Research on optimal path planning and parameters based on ant colony algorithm[J]. China Science Paper， 2018， 13 （16）： 1909-1914. （in Chinese）

[6]Norouzi A，Kazemi R，Abbasi O R. Path planning and replanning of lane change maneuvers in dynamic traffic environments[J]. International Journal of Vehicle Autonomous Systems，2019，14（3）：239-264.

[7]徐琳，宋萬強，嚴沖，等.基于威脅評估和擴展Voronoi圖的戰術飛行軌跡規劃方法[J].航空科學技術，2019，30（1）：35-43. Xu Lin， Song Wanqiang，Yan Chong， et al. Tactical flight path planning method based on threat assessment and extended Voronoi diagram[J]. Aeronautical Science & Technology， 2019， 30（1）：35-43. （in Chinese）

[8]陳雨童，胡明華，楊磊，等.受限航路空域自主航跡規劃與沖突管理技術[J].航空學報，2020，41（9）：253-270. Chen Yutong， Hu Minghua，Yang Lei， et al. Autonomous track planning and conflict management technology in restricted air route airspac[J]. Acta Aeronautica et Astronautica Sinica， 2020， 41（9）：253-270. （in Chinese）

[9]Xie L，Xue S，Zhang J，et al. A path planning approach based on multi-direction A^*algorithm for ships navigating within wind farm waters[J]. Ocean Engineering，2019，184（15）：311-322.

[10]劉永琦，徐丹，程歸，等.基于改進A～*算法的無人機快速軌跡規劃方法[J].飛行力學，2020，38（2）：40-46. Liu Yongqi， Xu Dan， Cheng Gui， et al. Fast trajectory planning method of UAV based on improved A～* algorithm[J]. Flight Dynamics， 2020，38（2）：40-46.（in Chinese）

[11]Zhao C，Zhang Y，Zheng D，et al. An improved hydrometeor identification method for X-band dual-polarization radar and its application for one summer Hailstorm over Northern China[J]. Atmospheric Research，2020，245：105075.

[12]Ma Jianli. Improvement of X-Band polarization radar melting layerrecognition by the bayesian method and its impact on hydrometeorclassification[J].AdvancesinAtmospheric Sciences，2020，37（1）：105-116.

[13]Marconnet D，Norden C，Vidal L.Optimum use of weather radar[J]. Safety First，2016，22：22-43.

[14]徐肖豪，李成功，趙嶷飛，等.基于人工勢場算法的改航路徑規劃[J].交通運輸工程學報，2009，9（6）：64-68. Xu Xiaohao， Li Chenggong， Zhao Yifei， et al. Path planning for course change based on artificial potential field algorithm[J]. Journal of Traffic and Transportation Engineering， 2009，9（6）：64-68.（in Chinese）

[15]趙元棣，李瑞東，吳佳馨.動態危險天氣下改航路徑快速規劃方法[J].中國科技論文，2020，15（6）：678-681. Zhao Yuandi， Li Ruidong，Wu Jiaxin. A fast planning method for course change under dynamic dangerous weather[J]. China Science Paper， 2020，15（6）：678-681.（in Chinese）

[16]Chernokulsky A，Shikhov A，Bykov A，et al. Satellite-based study and numerical forecasting of two tornado outbreaks in the Ural Region in June 2017[J]. Atmosphere，2020，11（11）：1146.

[17]Sermi F，Cuccoli F，Mugnai C，et al. Aircraft hazard evaluation for critical weather avoidance[C]// 2015 IEEE Metrology for Aerospace Conference. Benevento，Italy：IEEE，2015：454 - 459.

[18]趙元棣，付云峰，吳佳馨.航空器飛行軌跡表示方法及其應用[J].科學技術與工程，2020，20（12）：5000-5004. Zhao Yuandi， Fu Yunfeng， Wu Jiaxin. Representation of aircraft flight path and its application[J]. Science Technology and Engineering， 2020，20（12）：5000-5004.（in Chinese）

[19]占偉偉，王偉，陳能成，等.一種利用改進A^*算法的無人機航跡規劃[J].武漢大學學報（信息科學版），2015，40（3）：315-320. Zhan Weiwei， Wang Wei， Chen Nengcheng， et al. An unmanned aerial vehicle （UAV） path planning using improved A^*algorithm[J]. Geomatics and Information Science of Wuhan University， 2015，40（3）：315-320.（in Chinese）

[20]胡中華，許昕，陳中.無人機三維航跡非均勻三次B樣條平滑算法[J].控制工程，2020，27（7）：1259-1266. Hu Zhonghua， Xu Xin， Chen Zhong. Three-dimensional nonuniform B-spline smoothing algorithm for unmanned aerial vehicle[J]. Control Engineering of China， 2020， 27（7）： 1259- 1266.（in Chinese）

（責任編輯皮衛東）

作者簡介

李海（1976-）男，博士，教授。主要研究方向：機載氣象雷達信號處理、分布式目標檢測與參數估計、自適應信號處理、陣列信號處理、動目標檢測與參數估計。

Tel：13602155208

E-mail：haili@cauc.edu.cn

郭水林（1996-）男，碩士研究生。主要研究方向：飛行航跡規劃。

Tel：16622986909

E-mail：ShuilinGuo@163.com

周曄（1982-）女，碩士，高級工程師。主要研究方向：機載氣象雷達系統技術、雷達信號檢測及識別等。

Tel：15951585397E-mail：zhouye@chinaleihua.com

Dynamic Diversion Planning Combining Dynamic Risk Map and Improved A^*Algorithm

Li Hai1，*，Guo Shuilin1，Zhou Ye2

1. Tianjin Key Lab for Advanced Signal Processing，Civil Aviation University of China，Tianjin 300300，China 2. AVIC Leihua Electronic Technology Research Institute，Wuxi 214063，China

Abstract： Combining with airborne weather radar detection information， this paper proposes a dynamic diversion planning method which combines dynamic risk map and improved A^*algorithm. Firstly， the detection results of airborne weather radar are discretized to establish a dynamic risk map which is updated regularly， which is used as the simulation environment of the algorithm. Secondly， the cost function of the algorithm is constructed by considering the track length， track deviation and control constraints etc.， the cost function is used for route planning. At the same time， the search method of A^*algorithm is improved， and the planned track is smoothed and optimized. Finally， two different strategies are proposed to carry out simulation analysis experiments. The experimental results verify the effectiveness of the proposed method which is suitable for dynamic diversion planning.

Key Words： airborne weather radar； risk map； A^*algorithm； track smoothing； dynamic diversion