考慮航線危險天氣的動態繞爬路徑規劃

馬 蘭，劉佳月

(中國民航大學空中交通管理學院，天津 300300)

1 引言

從宏觀層次來講，主要有三個方面能對飛行安全產生影響，三種因素分別是：人、機、環境。在導致航班延誤和改航的各種原因中，強對流天氣無疑占據較大比例，其中雷暴云團內的閃電、過冷卻水很容易對機身和發動機造成損害，因其生命周期短且突發性為主要特征，飛行計劃中很難周全地考慮到。雖然這種天氣現象的尺度一般小于兩百公里、周期由幾分鐘至幾小時不等，但是對飛行安全來說仍然需要提高警惕。與此同時，在飛行過程中影響飛行安全的因素有很多，許多外在條件的變化都會使飛行路線需要實時的動態規劃。

路徑規劃的目的就是為了使飛機在受各種影響因素的情況下仍然能夠圓滿地完成飛行任務，國內外對這方面的研究已經有許多[1]。王莉莉、周娟為了應對靜態和動態突發天氣條件，設計啟發式算法將偏航因素考慮進去建立了最短航程模型[2]；王清琦、張兆寧為通過合理劃設飛行受限區，利用狀態轉移矩陣對雷暴軌跡預測，為改航飛行提供參考[3]；陳至坤、郭寶軍、王淑香通過柵格法對空間環境建模，以遺傳算法對A*算法改進路徑進行規劃提高了運算效率[4]；Victor Singh和Karen E.Willcox將動態路徑規劃問題分解為運動規劃和軌跡跟蹤兩部分，考慮了物理性能限制結合大量離線數據，把按約束條件規劃表達為馬爾科夫決策過程[5]；Egidio D’Amato和Massimiliano Mattei研究了多邊形障礙物、禁飛區等情況下的三維飛行路徑規劃問題，通過降維可見性圖(RVG)方法使路徑長度最小化[6]。

在實際飛行過程中，出現因操作誤差或天氣及其它因素導致的未能按既定航線飛行，需要盡快進行路徑規劃恢復正常，這樣才能減小對其它飛機的影響，在繁忙路段更是這樣。本文通過改進A*算法的底層結構，提出不同的啟發函數，減少算法對環境節點的探索，節約運行時間，針對危險天氣在航路上出現的路徑規劃問題做出主要研究思路如下：1)首先選擇全局靜態路徑規劃算法：A*算法作為頂層算法；2)通過Bresenham算法對A*算法底層結構做出優化，達到減少搜索節點的目的；3)二者結合不僅適用與靜態路徑規劃，同時也可以應用于移動障礙或突然出現障礙情況的動態路徑規劃；4)分析總結在不同的障礙情況下能否繼續進行自身查驗。

2 Bresenham算法模型

以現代導航的設施設備條件，在進行實際的飛行活動前就能夠獲取從出發點到目的地的許多相關信息，包括航線、機型性能、預計出發和到達時刻以及預期航空位置等，這相當于已知環境邊界以及部分環境做路徑規劃。傳統的路徑規劃的過程是有層次的，從動態路徑規劃和靜態路徑規劃來講主要可以分為A*算法和D*算法，從框架層級上來講可以分為High Level：Dijkstra、A*算法等；Low Level：VO算法、RVO算法、ORCA算法等。A*算法作為靜態路網中路徑規劃最直接有效的辦法被廣泛應用和改進。

但是就像引言中提及的，首先，將空域轉化為柵格后計算規模較大、時間復雜度高，不能滿足動態改航的需求；其次，雷暴云團的生命周期短，A*算法并不具備預知突發情況的能力，使用起來會與實際運行情況存在較大偏差。截至目前為止大部分對A*算法的改進仍停留在針對OPEN表和CLOSED表的方面，以飛行過程中遇到雷暴云團為例，A*算法會從出發點重新規劃一條到達目的地的航線，并不能直接對突發天氣現象這種動態情況作出及時反映，且運算時間也難以滿足需求。因此通過對A*算法的底層框架進行修改，在減少探索節點的同時，通過對探索節點的判別實現動態改航路徑規劃。

在一次完整的飛行過程中，不考慮備降場的情況下，出發點和目的地是固定的。Breshenham算法的原理就是通過判斷起訖點連線的斜率來確定前進的方向。假設以空間環境左下角為坐標原點，將空間轉化為柵格元素，坐標原點(0，0)，目標點(x，y)，由起訖點連線得到的一次方程可以表示為

(1)

以軸向右縱軸向上為正向，xi元素每次移動一個柵格。

以d1、d2分別表示當前位置在上下方向距離兩個柵格元素的距離。為了方便理解，圖1將線的交點視為質點化的柵格元素。則有

(2)

圖1 d1和d2

Bresenham算法在選取前進方向時主要有三種情況：

當D1>D2時，前進方向取(xi+1，yi+1)；當D1

其中：D1、D2的大小關系可以通過計算差值確定

D1-D2=2k(xi+1)-2yi+2b-1

(3)

Δx(D1-D2)=2Δy(xi+1)-Δx·2yi+Δx·(2b-1)

(4)

因Δx不存在小于0的情況，令Pi=Δx(D1-D2)，則判斷D1和D2的關系如下：Pi≥0時，D1≥D2，取(xi+1，yi+1)為前進方向；Pi<0時，D1

3 改進算法

3.1 無障礙節點模型

對傳統的A*算法來說，OPEN表和CLOSED表分別代表了環境空間內還未到達探索過的節點和已經訪問探索過的節點，通過不斷的減少OPEN表中的節點并將其合適的節點添加到CLOSED表中達到以節點連成路徑的目的。

算法公式可以表示為

Fn=gn+h(n)

(5)

F(n)是從出發點到n點的總代價，g(n)是在運行環境中從出發點到n點的實際代價，h(n)是從n點到目標點的最佳路徑的估計代價。其主要判斷的是當前位置與目標之間的距離D，也就是h(n)的大小。A*算法會在探索當前位置周圍全部節點的情況下選擇Dmin作為當前位置的最優節點，并重復這一過程，也就是不斷更新使

h(n)=h(Dmin)

(6)

F(n)=F(Dmin)

(7)

但是因為這一過程需要對每一個當前節點的周圍節點都進行探索，如果不根據改航的實際情況對算法的搜索方向進行限制，可能會出現偏離終點方向的探索，這類探索在航空器的改航中是沒有意義的運算，會導致算法運算時間過長、運算效率低下。針對這一點用Bresenham算法對底層結構做出調整，依據是在飛機的實際飛行路線中在當前位置能夠探索的節點數是有限的，需要在符合飛機性能的條件下篩選符合條件的節點進行運算，從而減小問題的規模。

Bresenham算法對A*算法的改進可以通過如下舉例說明：假設起點在環境空間偏左下的位置，終點在環境空間偏右上的位置，那么為了使從起點到終點走過的總距離盡量短，很明顯的是總體移動方向會向右和向上(假設在柵格化的環境空間中不允許直接斜向移動)，也就是起點的前進選擇方向是存在限制的，并不是全部的八個方向，而是最多只能從中選擇五方向前進，如圖2所示。

圖2 五方向前進

先定義這五個方向與當前位置的坐標夾角為表示該步長的方向矢量，用SL·cosθ表示，若物體當前位置已經移動到與終點同水平或同垂直邊界上，則當前位置的選擇方向繼續減少。在前進路徑上沒有障礙阻擋時，各方向步長相同，則當前位置到達周圍的柵格可以表示為

(8)

以當前位置正上為0°順時針計算角度，與空中導航原則保持一致。這樣定義的原因是斜向前進每次需要兩個步長才能夠到達，而直向移動僅需要一個步長就可以到達。與此同時，如果在直向移動一次后發現相對上一步來說斜向移動才是最優路徑的話，二者最終在步長上會體現出等同的數量，不會因為方向問題而導致結果不準確。而如果斜向移動兩個步長的方向與指向終點的方向相反，則判定該次移動屬于冗余移動，需要兩個步長回到原位置后再繼續。這樣帶有矢量的方向選擇會在一定程度上減少無意義的探索運算，對提升效率、減少運算時間有很大幫助。

在橫軸方向上移動的長度表示為dx-nx,在縱軸方向上移動的長度表示為dy-ny，調用Matlab的abs(x)函數，用以表示移動的絕對距離。此時算法函數可以表示為

F(n)=g(SL×cosθ)+h(abs(dx-nx)+abs(dy-ny))

(9)

3.2 有障礙節點模型

本文提出的改進算法核心思路就是在碰到障礙或飛行受限區時，分別從該位置分為左右兩支緊貼障礙或受限區邊緣前進，直到完全繞過障礙或受限區繼續前進或者兩條分支分別按既定原則繼續前進，最終到達目的地為止，因此稱為繞爬算法。

如圖3中所示，當前位置在左下角，黑色區域的兩個節點是小尺度雷暴云團區域，也就是障礙節點。飛機需要從其兩側繞飛，也就是藍色箭頭1和2代表的路線。當右側和右上均有障礙節點(黑色區域)阻擋無法探索時，能夠繼續探索的節點相對當前位置來說只剩三個方向(淺藍色箭頭所指方向)，深藍色箭頭代表了緊貼障礙節點的繞爬節點，1和2分別代表從遇到節點開始向左向右的兩個繞爬分支。

圖3 有障礙節點的前進

如果兩個繞爬分支繞過障礙節點后匯合，定義為完全繞爬的情況。還有一種情況是兩個繞爬分支沒有任何在一個節點匯合，分別獨立繼續探索，這種定義為非完全繞爬。針對兩種不同的情況，在算法步驟中給出兩種解決辦法，保證探索過程繼續順利進行。

4 算法設計

在進行算法實際編程前，對一些概念和方式進行梳理和補充：

A)自由節點：在整個路徑規劃過程中，從當前位置向前探索的、不受障礙覆蓋的地圖柵格被標記為自由節點，起始探索節點就是最初的自由節點，同時也是原點。

這一概念相當于A*算法中的開放節點。相對而言，不是自由節點的稱之為障礙節點或邊界節點，也就是本文所討論的被強對流天氣覆蓋的需要飛機繞飛的區域(下文將障礙節點和邊界節點視為同一種節點不再詳細區分)；

B)自由探索：物體一直朝向終點前進的情況下，如果下一步至少存在一個柵格不是障礙節點，也就是可以從當前位置繼續向前能夠正常進入下一個自由節點探索，這個過程稱之為自由探索；該過程等價于基于性能的導航方式下的實際飛行過程。

C)繞爬節點：在物體朝向終點前進的情況下，如果當前位置的前進方向上下一個柵格是障礙節點，則嘗試繞過障礙節點，遵循先右后左原則繼續探索，繞爬過程中所有自由節點均標記為繞爬節點，直到繞爬過程結束。在實際飛行過程中如果前方航線上存在雷暴云團，分別從左右兩側對路徑進行探索再決定繞飛方向。

4.1 算法技術路線圖

算法從起點開始，先將起點柵格作為當前節點對下一前進方向的柵格進行判斷：如果是障礙節點，選擇否。然后以障礙節點為邊界，從當前節點位置分出左右分支繼續運行，原則為先右后左原則，也就是將向左的分支先掛起到程序后臺，首先運行向右分支的判斷，用循環語句重復對下一前進方向柵格的判斷過程，直到向右分支恢復為自由節點。然后運行向左分支的判斷，仍然使用循環語句進行判斷，直到向左分支也恢復為自由節點或完成完全繞爬過程。若兩個分支匯合，則完全繞爬過程結束，重新重復整個過程，直到到達終點；若兩個分支未匯合，則兩個分支分別繼續探索，重復整個運算過程，直到到達邊界或終點結束。

圖4 技術路線

算法的具體步驟如下：

1)開始，將起點標記為最初的自由節點，從當前位置出發向終點進行探索；

2)在向終點探索的過程中判斷下一格柵格是否為自由節點，

2.1)下一柵格是自由節點，正常前進，步長為一步，將該點標記為自由節點，繼續；

2.2)下一柵格不是自由節點，以下一柵格為障礙節點，從該點向左右分出兩個繞爬分支，將兩個分支的起始探索節點標記為自由節點，再次進行判斷，分別嘗試繞過障礙節點。

2.2.1)若可以繼續探索，將這兩個起始探索節點標記為兩個繞爬的探索節點；

2.2.2)若不能繼續探索，返回上一自由節點；

2.3)若某一繞爬探索節點出現五方向前進均不是自由節點的情況，返回繞爬探索節點的上一個自由節點并暫停，另一繞爬分支繼續探索，若該分支也出現同樣情況，則繼續上一自由節點的探索并將本次探索節點全部標記為障礙節點。

3)兩個繞爬分支繞過障礙后可能出現交匯的情況，稱為完全繞爬成功，繞過障礙后，選擇探索節點更少的分支為合理路徑，從匯合點又成為自由節點繼續向前；

4)判斷兩個繞爬分支的長度，當一個分支A先于另一分支B遇到下一個障礙時，A分支分為A1分支和A2分支繼續尋路，B分支繼續尋路，直到分支匯合或再遇到障礙繼續分支，直到某分支到達目標，同時停止所有分支尋路；

5)自由探索的同時也需要判斷下一柵格是否為終點，若是，則尋路成功，結束探索過程，選擇探索過的節點構成完整路徑；若不是，返回步驟2，重復步驟2-5，直到條件“是”達成；

6)到達目標各自后檢查路徑能否繼續優化：在每一次遇到的障礙節點的分支處與下一個分支處重復尋路過程，若移動更短，則用新的路徑替代原有路徑，若相同，則停止。

4.2 算法仿真

使用Windows10系統的C++語言對繞爬算法按步驟編寫語句并進行仿真，如圖5所示，算法運行的空間環境邊界設置為32×32，其有效空間環境為30×30的正方形區域。選取起點坐標(3，3)，用左下角綠色方塊表示；終點坐標(29，22)，用右上角紅色方塊表示。左側及下方黑色方塊代表空間環境的左下邊界，在整個空間環境中設置7處障礙區域，用來代表飛機在飛行過程中可能遇到的雷暴或其它強對流天氣障礙。如圖5中黑色長條方塊區域所示。對算法運行結果計數，分別表示當前分支的路徑長度，黃色分支被標記為最優路徑作為運算結果。

為體現繞爬算法的有效性，另外使用同一計算機下的Matlab軟件對相同條件下的A*算法進行仿真，如圖6所示。其中紅色點代表空間環境的邊界和障礙區域，綠色代表探索過但是并不是最優路徑的節點。

對比兩種算法所運行的過程和結果如下。

圖5 繞爬算法運行結果

圖6 A*算法運行結果

兩種算法的步長和可探索空間總節點如表1所示。

表1 算法結果對比

5 總結

在給定仿真環境中，繞爬算法和A*算法的仿真結果對比可以很明顯的看出：1.A*算法空間環境共900格節點，除去障礙節點71格，完成路徑規劃共需探索808格節點；2.繞爬算法空間環境及障礙節點數同上，但完成路徑規劃僅需探索175格節點。3.雖然算法的仿真環境相較于實際情況可能復雜度更高，但算法效率的高下十分清楚，并且從圖中可以看出繞爬算法對障礙具有良好的貼邊繞障能力，對航路危險天氣繞飛有實際意義。4.隨著不同運行環境下仿真次數的增加，可以得出的結論為，環境空間越大，繞爬算法相對于A*算法的效率優勢就越明顯；障礙物越多，雖然A*算法自身效果會越來越好，但是其效率仍然遠遠不及繞爬算法。

近年來許多對A*算法的改進都停留在減少全向搜索節點數量方面，但是在一個固定的環境空間中，對所有柵格進行獨立探索是十分浪費的，隨著環境空間的增大，運算次數會較大幅度增加。本文針對這一點先對底層結構中的節點篩選，判斷柵格是否可以被選作當前節點的下一步，然后再從這些節點判斷有哪些是應該被選擇的路徑規劃節點。這樣大大減少了需要進行判別運算的節點，提高算法效率。但是繞爬算法仍然存在一些問題：比如完全繞爬與bresenham算法在優先級上的順序會影響路徑規劃的結果，兩者的優先級應根據不同情況實際判斷，未來深入研究的重點在于如何對運算結果分析并優化。