基于扇形領域擴展的同步雙向A*算法

摘 要： 為提高航空器飛行的安全性和平滑性，解決傳統A*算法拐彎角度過大、搜索路徑節點過多等問題，提出一種基于扇形領域擴展的同步雙向A*搜索算法。首先，根據柵格圖法擴展危險區域邊界；其次，設計了基于同步雙向搜索的A*算法，動態定義正反向搜索的目標節點。針對搜索角度有限問題，提出了在5×5領域內的扇形領域擴展策略，并設計了含有雙重權重參數的評價函數以減少冗余點的產生。為驗證改進算法的有效性，選取方形和不規則形狀危險區進行仿真。結果表明改進的同步雙向搜索算法搜索的路徑更平滑；與傳統雙向A*算法的結果相比，在不同形狀的危險區域下，搜索路徑長度分別減少了1.65%、13.16%，搜索路徑節點個數減少了42.6%、46.81%，具有較強的搜索效率。

關鍵詞： 路徑規劃； 同步雙向A*算法； 扇形領域擴展； 雙重權重

中圖分類號： TP301.6"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-021-0118-05

doi：10.19734/j.issn.1001-3695.2021.06.0219

Research on synchronous bi-directional A* algorithm based on sector field expansion

Chen Wantong1a，1b， Diao Tianru1b， Jia Jiqing2， Qin Shiwei2

（1.a.Key Laboratory of Civil Aviation Flight Wide Area Surveillance amp; Safety Control Technology， b.College of Electronic Information amp; Automation，Civil Aviation University of China， Tianjin 300300， China; 2.Qingdao Air Traffic Management Station of Civil Aviation of China， Qingdao Shandong 266041， China）

Abstract： In order to improve the safety and smoothness of flight， and solve the problems of excessive turning angle and too many search path nodes in the traditional A* algorithm， this paper proposed a synchronous bi-directional A* search algorithm based on sector field expansion. Firstly， this paper extended the hazardous area boundaries based on the raster map method. Secondly， it designed the A* algorithm based on synchronous bi-directional search， which dynamically defined the target nodes for forward and reverse search. Aiming at the problem of limiting search angles， this paper proposed a sector expansion strategy in 5×5 domain， and designed an evaluation function with double weight parameters to reduce the generation of redundant points. Finally， in order to verify the effectiveness of the improved algorithm， this paper selected square and irregular shape hazard areas for simulation. The results show that the improved algorithm searches for a smoother path. Compared with the results of the traditional bi-directional A* algorithm， the length of its search path reduce by 1.65% and 13.16%， and the number of its search path nodes reduce by 42.6% and 46.81%， respectively， under different shapes of hazard areas， which has a strong search efficiency.

Key words： path planning; synchronous bi-directional A* search algorithm; sector field expansion; double weighting

0 引言

航空器飛行環境十分復雜，會受到非戰爭軍事行動［1］以及航天發射活動［2］的影響，甚至受到雷暴、強對流、風切變［3］等不確定性危險天氣因素影響，因此民航飛行安全需要考慮外部環境因素。航空器路徑規劃問題是民航飛行安全的核心內容之一，也是研究人員較為關注的熱點。其目的在于根據制定的評價指標找到一條既能滿足長度最短，又能躲避危險區的最優路徑。

近年來，國內外關于航空器路徑規劃的研究成果主要集中在機場滑行道、空中飛行安全等方面。Zhao等人［4］建立了機場地面總距離最短的飛機路徑規劃模型，采用改進的A*算法和神經搜索方法得到飛機4D軌跡，減少了飛機滑行距離、轉彎次數以及污染物排放量，但未考慮避碰次數。Li等人［5］針對機場節能減排問題，建立以總滑行時間最短為目標的飛機機場滑行路徑優化模型，采用遺傳算法對其求解，縮短了滑行時間，有效避免了滑行沖突，減少了滑行階段的污染物排放。Gao等人［6］針對中國國內航空網絡中機場的可達性問題，設計了基于Dijkstra的快速全對最短路徑算法，滿足時間和預算要求，并使用優先級隊列和二叉索引樹提高時間效率。Fallast等人［7］針對通航飛機安全著陸問題，建立了基于RTT*算法的四維搜索空間中的搜索樹，提高了算法性能。Bojorquez等人［8］提出引入安全策略的快速行進樹（FMT）算法，降低航天器路徑規劃的復雜度，尤其是FMT算法中的重采樣和碰撞避免檢測循環過程。Li等人［9］提出利用蟻群算法對直升機呼叫搜索航路進行規劃，提高呼叫搜索效率。Chen等人［10］在風險等級圖下使用制定的A*算法，生成用時最少且距離最短的飛機改航計劃，但會受成本調整的影響。Shi等人［11］提出基于LSTM-立體A*的空中交通管理輔助決策支持方法，考慮飛機動態性能，利用立體A*搜索算法提供合理路徑。

上述研究解決了航空器的路徑規劃問題，但很少有人考慮航空器周圍環境中的障礙物形狀，以及如何在路徑規劃中避開這些障礙物。A*算法是一種規劃路徑長度最短且計算速度快的全局路徑規劃算法，但其存在拐角過大、路徑不平滑等問題［12］，因此，該算法在航空器低維航跡規劃中應用較少。針對A*算法的節點遍歷過多、路徑不平滑等問題以及航空器安全性問題，本文提出基于扇形領域擴展的同步雙向A*搜索算法。首先對危險區域建模，在原有危險區的基礎上適當擴展危險區域邊界，保障航空器的正常安全行駛；然后在同步雙向搜索的基礎上，通過動態搜索目標節點來改進領域擴展數量，同時采用雙重權重，靈活改進參數值優化評價函數；最后對比傳統雙向A*算法、文獻［13，14］算法、改進同步雙向A*搜索算法，驗證基于扇形領域擴展的同步雙向A*搜索算法的有效性，且該算法路徑平滑性、路徑長度等各項指標優于其他兩種算法。

1 基于雙向搜索的改進A*算法研究

1.1 危險區擴展策略

結合航空器飛行環境、算法特性等因素，作出以下假設：a）將一架航空器抽象成一個質點，忽略航空器的尺寸大小，不考慮其速度；b）假設空中的危險區域在水平位置上的速度忽略不計，則危險區域均是靜止的；c）航空器飛行環境由三維的真實空間抽象為二維的虛擬空間。將航空器當做一個質點，不考慮其實際尺寸，可能會導致A*算法規劃后的部分路徑距離危險區域較近，在現實中存在較大安全隱患。為了解決上述問題，提出危險區擴展策略。該策略利用柵格法將原有的危險區域記為高風險區域，擴展出來的危險區域記為低風險區域。如圖1所示，黑色區域為原障礙區域（即高風險區域），灰色區域為擴展區域（即低風險區域），白色區域為安全區域。

危險區擴展方法的具體思想如下：假設高風險區域占了n個柵格，獲取高風險區域在圖中坐標位置（xi，yi），i=1，2，…，n，并依次進行遍歷。檢查與（xi，yi）相鄰的八個柵格，判斷它們是否在地圖外部或者高風險列表里。如果（xi，yi）在地圖外部或者高風險列表里，則繼續檢查其他柵格；否則，判斷（xi，yi）是否在低風險列表中，若不在，則設（xi，yi）為低風險區域。在算法設計過程中，規劃的路徑不可以穿越高風險區，并盡可能避免穿越低風險區。

應用以上思想，可以保證航空器飛行路徑與高風險區域邊界有適當的安全距離。

1.2 改進的雙向A*算法

傳統A*算法是一種啟發式搜索算法，在障礙物極少且面積極小的環境中，能夠在保證搜索效率的同時得到最短的路徑規劃。在復雜環境下的路徑規劃問題中，常常會產生冗余點過多、轉角度數過大等問題，影響路徑規劃的搜索效率，此時傳統A*算法并不一定能得到最優的路徑規劃。因此，可從搜索方向、領域擴展、評價函數這三方面對傳統A*算法進行改進，從而得到最優路徑。

1.2.1 同步雙向搜索

由于傳統A*算法是一種單向搜索算法，其思想是從起點開始搜索，直至搜索到終點為止，所以該算法遍歷的節點較多，運行效率較低。為減少算法遍歷的節點數量、提高算法的搜索效率、避免盲目搜索，本文在傳統A*算法的基礎上提出同步雙向A*算法。同步雙向A*算法的流程如圖2所示。其中，openlist1用于存放正向搜索中的待檢索節點，closelist1用于存放正向搜索中的已確定節點，openlist2用于存放反向搜索中的待檢索節點，closelist2用于存放反向搜索中的已確定節點。同步雙向A*算法從以下兩個方面進行改進：

a）采用同步雙向搜索技術，即物體沿正反兩個方向交替進行搜索。物體從起始點向目標點方向搜索的過程稱為正向搜索，反之稱為反向搜索。同步雙向搜索的好處是方便記錄當前搜索節點位置，提高搜索效率。

b）動態定義正反方向搜索的目標節點，即將正向搜索過程中的當前節點作為反向搜索的目標節點，將反向搜索過程中的當前節點作為正向搜索的目標節點。每搜索一次，目標節點更換一次。當正向搜索的當前節點的擴展節點extendNode1遇到了反向搜索的當前節點currentNode2，或者反向搜索的當前節點的擴展節點extendNode2遇到了正向搜索的當前節點currentNode1時，同步雙向搜索結束。其優點是確保正向搜索節點和反向搜索節點可以在起始節點與終止節點相連線段的中點附近相遇，提高了算法搜索效率。

1.2.2 領域擴展

傳統A*算法采用8領域的搜索方式，每次選定的當前節點的八個子節點均被遍歷一遍，搜索方向具有局限性，搜索范圍較小，搜索路徑較為曲折。若將8領域擴展為24 領域，雖然增加了16個搜索方向使搜索范圍增大，但搜索路徑更加平滑，而且24個搜索方向中存在部分無效方向，增加搜索時間、降低路徑規劃效率。針對以上問題，本文對文獻［15］提出的搜索方向方法進行改進，提出基于近似扇形領域擴展策略。在24領域擴展的基礎上，根據方向判斷和扇形擴展的原則，去掉9個由當前搜索節點到目標節點方向相反的擴展方向，使算法搜索效率進一步提高。

其中：nh2（x2）表示反向搜索當前節點x2到目標節點xend2的啟發式預估代價函數；p2（x2）表示反向搜索當前節點x2到目標節點xend2的歐氏距離函數；q2（x2）表示反向搜索當前節點x2到正向搜索當前節點x1的歐氏距離函數；v為預估代價的權重參數，可改變p2（x2）和q2（x2）在式（10）中的比例，其中v的取值為[0，+∞）。

式（6）（7）（10）（11）中的參數α和γ為評價函數提供了權重比例機制。通過實驗選取合適的參數值，以此來優化最短路徑、提高搜索效率。參數α與γ的關系如式（11）所示。

α+γ=1，0lt;αlt;1，0lt;γlt;1（11）

2 實驗結果分析

本文實驗確定同步雙向A*算法的領域擴展數量和評價函數參數，對雙向A*算法、文獻［13，14］算法和改進雙向A*算法的拐點數量、運行時間、路徑長度、遍歷節點數量進行對比，并分析這三種算法在該問題上的性能以及改進雙向A*算法的效果。

2.1 實驗環境

為評估算法的執行效率等特點，實驗設置了所需的軟件和硬件環境，如表3所示。

2.2 領域擴展數量分析

基于表3的軟件和硬件環境確定同步雙向A*算法的領域擴展數量。在單位柵格長度為10的50×50的柵格圖中，設起始節點坐標為（2，3），目標節點坐標為（48，48）;設評價函數參數u=1，v=1， α=0.5， γ=0.5。對滿足式（1）的所有領域擴展方案進行初步測試。經測試，a層擴展數量為1個、2個、7個時，尋路失敗。在成功尋路的方案中選出七組具有代表性的領域擴展數量，分別對它們進行檢驗，每組進行10次實驗，比較了同步雙向A*算法在不同領域擴展情況下的遍歷節點數量、路徑長度、路徑節點個數、拐角個數、平均運行時間。七組方案運行時間如圖5所示，比較結果如表4所示。由表4、圖5可知，a層擴展5個節點、b層擴展10個節點時，規劃的路徑長度最短、拐角數最少、路徑中包含的節點數量最少、算法遍歷節點數量最少、平均運行時間最短，運行結果如圖6所示。驗證了采用改進方案可以規劃出最優路徑。

2.3 評價函數參數分析

根據表3的實驗環境，確定同步雙向A*算法的評價函數參數。根據2.2節的結果，設當前節點的擴展情況為a層擴展5個節點，b層擴展10個節點。在起始節點坐標為（2，3），目標節點坐標為（48，48）的50×50的柵格圖中，通過設置評價函數的四個權重參數值進行測試。

a）固定α和γ的值，均設為0.5，改變u和v的值，運行結果如表5所示。由表5可知，當u與v滿足ugt;1，vgt;1時，路徑長度、拐角個數、遍歷節點個數等評價指標是相等的，搜索路徑長度明顯多于權重參數u=1，v=1時的搜索路徑長度。因此，驗證了α和γ的值均為0.5且u=v=1時，尋找的路徑最優。

b）固定u和v的值，均設為1，以0.1為單位改變α和γ的值，運行結果如表6所示。由表6可知，最優路徑可能出現在權重參數α∈（0.6，0.7）且權重參數γ∈（0.3，0.4）時。因此，以0.01為單位改變α和γ的值，再次仿真找出合適的權重參數值。仿真結果如圖7所示，運行結果如表7所示。圖中，紫色圓點表示起點，綠色圓點表示終點；黃色正方形區域表示openlist1或openlist2中的節點，綠色正方形區域表示closelist1或closelist2中的節點；紅線表示路徑軌跡；藍點表示路徑搜索經過的節點（參見電子版）。

由表7可知，當γlt;0.34且αgt;0.66時，路徑搜索失敗。綜合路徑長度、遍歷節點數量等評價指標發現，當α=0.63，γ=0.37時，尋路效果最好。

c）固定α和γ的值，設α=0.63，γ=0.37，改變u和v的值。經50次仿真發現，當u=1時，無論v取何值，各項評價指標均相等，并且尋路效果優于其他取值情況。仿真結果如圖8所示，運行結果如表8所示。

2.4 不同危險區域環境的路徑規劃測試

假設航空器飛行高度和飛行速度保持不變，航空器飛行的空域環境在50×50的網格中用白色、灰色、黑色三種顏色描述。每個單元網格邊長為10 km。設航空器起點坐標為（3，2），終點坐標為（45，25）。由2.3節分析可知，選用α=0.63，γ=0.37，u=1，v=2作為評價函數的雙重權重參數。

基于表3給出的計算機軟件和硬件環境，分別對含有不同危險區的空域環境下的路徑規劃進行仿真測試，通過比較傳統雙向A*算法、文獻［13，14］算法、改進雙向A*算法的算法運行時間、搜索路徑長度、遍歷節點個數等指標，驗證改進雙向A*算法的有效性。

2.4.1 方形危險區域

航空器在含有方形危險區的空域環境中四種算法的路徑規劃仿真結果如圖9所示，運行結果如表9所示。

由圖9和表9可知，雖然改進雙向A*在運行時間和遍歷節點個數上不占優勢，但是改進雙向A*在路徑長度、路徑節點個數方面優于其他三種算法。與傳統雙向A*相比，改進雙向A*搜索路徑長度減少了1.65%，搜索路徑節點個數減少了42.6%。從圖9可以看出，改進雙向A*規劃的路徑更為平滑，更符合航空器飛行軌跡。

2.4.2 不規則形狀的危險區域

修改航空器飛行環境，空域中危險區設為不規則形狀且與部分危險區相連。航空器在含有不規則形狀危險區的空域環境中路徑規劃仿真結果如圖10所示，運行結果如表10所示。

由圖10和表10可知，四種算法中，文獻［13］規劃的路徑曲折，搜索時間較長，不符合實際需求；文獻［14］雖拐角個數較少，但遍歷節點數量最多，搜索時間最長;改進的雙向A*規劃的路徑最短、拐角個數少、路徑節點個數最少、平均運行時間最短、路徑更為平滑。與傳統雙向A*相比，改進雙向A*搜索路徑長度減少了13.16%，搜索路徑節點個數減少了46.81%，其搜索的路徑更符合航空器飛行現狀，更能適應大面積危險區域的環境。

由上述分析可知，改進雙向A*可以在保證安全的情況下，搜索出最優路徑，具有良好的魯棒性和穩定性。

3 結束語

在危險區復雜的空域環境中，采用傳統A*算法規劃的路徑雖然是最短路徑，但是路徑較為曲折，容易產生很多冗余節點和拐點，存在安全風險。針對以上問題，本文提出一種基于扇形領域擴展的同步雙向A*搜索算法。將危險區域邊界進行適當擴展，在5×5領域內進行15領域扇形擴展，動態定義雙向目標節點，引入雙重權重參數改進評價函數未得到最優路徑。實驗結果表明，改進后的算法具有有效性，在搜索路徑節點個數、搜索路徑長度、路徑平滑性等方面都優于傳統雙向A*算法。由于空域中不僅存在靜態危險區，還存在碎片等組成的動態危險區，這些危險區對航空器飛行安全產生影響，所以下一步工作將繼續研究增加拐點平滑度的方法以及在動態危險區的空域環境中高效規劃出最優路徑的方法。

參考文獻：

[1]吳文浩，張學軍，顧博，等.基于軍民融合的全局飛行流量協同優化方法［J］.北京航空航天大學學報，2018，44（9）：1926-1932.（Wu Wenhao， Zhang Xuejun， Gu Bo， et al. A" global network flight flow assignment algorithm based on civil-military integration［J］.Journal of Beijing University of Aeronautics and Astronautics，2018，44（9）：1926-1932.）

［2]Bojorquez O J， Chen Jun. Risk level analysis for hazard area during commercial space launch［C］//Proc of the 38th IEEE/AIAA Digital Avionics Systems Conference.Piscataway，NJ：IEEE Press，2019.

［3]Zhang Hongwei， Wu Songhua， Wang Qichao， et al. Airport low-level wind shear lidar observation at Beijing Capital International Airport［J］.Infrared Physics amp; Technology，2019，96（1）：113-122.

［4]Zhao Ningning， Li Nan， Sun Yu， et al. 4D trajectory planning of aircraft taxiing considering time and fuel［J］.Mathematical Problems in Engineering，2020，2020（12）：article ID 9603968.

［5]Li Nan， Sun Yu， Yu Jian， et al. An empirical study on low emission ta-xiing path optimization of aircrafts on airport surfaces from the perspective of reducing carbon emissions［J］.Energies，2019，12（9）：1649.

［6]Gao Xiaofeng， Xianzang Yueyang， You Xiaotian， et al. Reachability for airline networks： fast algorithm for shortest path problem with time windows［J］.Theoretical Computer Science，2018，749（11）：66-79.

［7]Fallast A， Messnarz B. Automated trajectory generation and airport selection for an emergency landing procedure of a CS23 aircraft［J］.CEAS Aeronautical Journal，2017，8（9）：481-492.

［8]Bojorquez O， Dolan N， Chen J. Aircraft rerouting under risk tole-rance during space launches［C］//Proc of AIAA Scitech Forum.Reston，VA：American Institute of Aeronautics and Astronautics，2020.

［9]Li Lin， Zhou Zhiying， Han Qiang， et al. Application of ant colony algorithm to air route planning in helicopter submarine searching［J］.Journal of Physics： Conference Series，2020，1650（2）：032004.

［10]Chen Ning， Zhang Yasheng， Li Zhi， et al. An improved sampling-based approach for spacecraft proximity operation path planning in near-circular orbit［J］.IEEE Access，2020，8：41794-41804.

［11]Shi Zhiyuan， Pan Quan， Xu Min. LSTM-Cubic A*-based auxiliary decision support system in air traffic management［J］.Neurocompu-ting，2020，391（5）：167-176.

［12]高民東，張雅妮，朱凌云.應用于機器人路徑規劃的雙向時效A*算法［J］.計算機應用研究，2019，36（3）：792-795，800.（Gao Mindong， Zhang Yani， Zhu Lingyun. Bidirectional time-efficient A* algorithm for robot path planning［J］.Application Research of Computers，2019，36（3）：792-795，800.）

［13]孔繼利，張鵬坤，劉曉平.雙向搜索機制的改進A*算法研究［J］.計算機工程與應用，2021，57（8）：231-237.（Kong Jili， Zhang Pengkun， Liu Xiaoping. Research on improved A* algorithm of bidirectional search mechanism［J］.Computer Engineering and Application，2021，57（8）：231-237.）

［14]高峰，周浩，楊卓宇.基于改進A*算法的水面無人船全局路徑規劃［J］.計算機應用研究，2020，37（S1）：120-121，125.（Gao Feng， Zhou Hao， Yang Zhuoyu. Global path planning of unmanned surface vessel based on improved A* algorithm［J］.Application Research of Computers，2020，37（S1）：120-121，125.）

［15]曹毅，周軼，張亞賓.基于優化A*和DWA算法的移動機器人避障路徑規劃［J］.機床與液壓，2020，48（24）：246-252.（Cao Yi， Zhou Yi， Zhang Yabin. Path planning for obstacle avoidance of mobile robot based on optimized A* and DWA algorithm［J］.Machine Tool amp; Hydraulics，2020，48（24）：246-252.）