基于優化A*算法的越野最短路徑規劃研究

范林林，邱德楠，曹 震，華一新

（1. 61175部隊，江蘇 南京 210049；2. 信息工程大學，河南 鄭州 450001）

啟發式A*算法是一種全局搜索算法[1]。傳統上使用A*算法尋找最短路徑是假設每一個節點的消耗是一樣的，而在研究越野環境下的機動車輛的最短路徑問題時，地形環境對車輛機動影響很大，需要對地形環境加以分析[2-4]。

1 基于六角格網的越野路徑規劃研究

1.1 六角格網地形量化的優勢

進行越野方式前進時，可選擇正三角形、正四邊形（4方向，僅邊方向；8方向，邊角方向）和正六邊形，本文采用正六邊形進行地形量化，并以此為基礎進行越野機動路徑規劃，其優勢有：①正六邊形具有一致的邊鄰近關系。②正六邊形最為緊湊[5]。在相同分辨率情況下，正六邊形的采樣密度最大，采樣精度最高，在表達地形環境時更加詳細、準確。③正六邊形具有較好的角分辨率。有利于提高地形特征提取和識別的精度。④正六邊形具有最多的邊等距方向。邊等距方向越多，越貼近實際情況并且簡化問題。

1.2 基于六角格網的越野路徑規劃數據結構設計

根據矢量地形圖的范圍生成的六角格網可以描述為具有典型的柵格模型結構，可以按照柵格模型的方式進行編碼[6]。本文研究越野路徑規劃問題，基于六角格網的越野通行模型數據結構，數據結構可隨著矢量圖層的擴展支持數據結構的擴充。具體設計如表1所示。

表1 六角格網格元的數據結構設計

根據對六角格網格邊量化過程的分析研究，設計六角格網格邊的數據模型如表2所示。

表2 六角格網格邊的數據結構設計

1.3 六角格網數據在越野路徑規劃中的表達

通過分析總結各類地形要素對越野機動車輛產生的影響，本文針對越野條件下車輛機動問題，將影響越野機動的因素劃分為6大類[7]：陸地地貌、植被、陸地水系、居民設施、陸地交通和陸地土質（如表3 所示）。該分類涵蓋了對履帶式車輛越野機動的主要影響因素。

表3 影響履帶式車輛機動的地形要素分類

本文研究采用六角格網對地形進行剖分，并進行量化處理。六角格數據在越野路徑規劃中的表達包括：六角格網格元、六角格網格邊和六角格網中垂線。

1）六角格網格元。六角格網格元主要描述面狀地表屬性、坡度和高程。具體地表屬性有森林、灌木林、居民地設施、海洋、湖泊和水庫、沼澤、砂礫土質、硬質路面和沙漠等；描述每一個格元與相鄰格元之間的坡度，并表示其大小和方向；描述六角格網中每一個格元中心點的高程。

2）六角格網格邊。六角格網格邊主要描述障礙信息，格邊描述為線狀河流要素，根據河流要素與六角格網格邊的相交情況，將河流表示為六角格網格邊。

3）六角格網中垂線。機動車輛沿六角格網中心點進行移動，根據地形通行能力，道路的優先級最高。因此，根據陸地交通要素與六角格網格邊的相交情況，描述為六角格格元中心點到道路與格邊交點所在格邊的中垂線。

2 啟發式A＊算法的優化

本文研究最短路徑問題是在起點和終點確定的前提下，尋找兩點之間的可通行路徑中時間最短的路徑。將六角格網抽象為一個有格網中心點為節點，相鄰格網中心點之間連線為弧段的網絡圖。在越野條件下，車輛移動過程描述為沿格元中心點到相鄰格元中心點的直線運動，在此過程中，需要考慮地形類型差異引起的消耗，不同類型地形對車輛的影響差別較大。通常情況下道路的機動通行移動代價消耗最低，而沼澤、沙漠等移動代價消耗較高。根據已發表文章中[8]，研究了確定越野條件下履帶式車輛在不同地形環境下的機動速度的方法，為越野路徑規劃算法研究提供了基礎。

2.1 估價函數的優化方法

啟發式A*算法中估價函數定義為f(i,j)=g(i,j)+h(i,j)，估價函數的選取在進行路徑搜索時具有重要意義，估價函數要保證路徑代價值、尋找路徑所擴展的節點數目和估計函數的計算量達到一個最佳的平衡，以使啟發能力最大[7]。

本文對啟發式A*算法的優化是針對實際消耗函數g(i,j)的優化。考慮地表屬性，坡度和高程3個約束條件對越野機動車輛速度的影響，進而影響起始格元移動至當前格元的實際消耗時間。對應啟發式A*算法的g(i,j)的優化公式如式（1）所示。

如圖1所示，格元D(i*,j*)是當前格元G(i,j)的可通行鄰接格元；g(i*,j*)是起始格元到格元D(i*,j*)的實際消耗時間；R是當前六角格網格元的尺寸。根據不同類型的車輛，V1是選定某研究類型越野機動車輛在格元D(i*,j*)中的通行速度；V2是選定某研究類型越野機動車輛在格元G(i,j)中的通行速度。

圖1 越野機動通行示意圖

2.2 優化A*算法的流程

在給定起始格元S 和目標格元E 前提下，基于越野條件下機動車輛的最短路徑求解問題，其生成最短路徑的啟發式A*算法流程為：

1）數據預處理。對大比例尺地形圖數據和數字高程模型分層處理，并采用六角格網對其進行地形量化，確定六角格網格元和格邊的屬性。建立open 表、closed表和TerrCost表，并對其進行初始化。

2）將起始六角格網格元S 放入open 表中；closed表用來存儲不需要再次考察的六角格網格元，TerrCost表用來實時檢查當前格元的相鄰格元。

3）檢查open 表是否為空，若為空，則尋找路徑失敗，退出；否則繼續執行。

4）判斷當前六角格網格元是否為目標格元，如果是，跳至步驟7）；否則，繼續執行。

5） 對照closed 表，計算格元相應的g(i,j) ，h(i,j)和f(i,j)。

6）判斷當前open 表中f(i,j)值最小的六角格格元，若為終點，則繼續執行；若否，將該格元設為當前格元，計算open 表中的g(i,j) ，h(i,j) 和f(i,j)值，并將該格元加入closed表，返回步驟4）。

7）根據closed表中格元信息以及父格元信息，由目標格元開始，根據父指針向后至起始節點，得到最終結果。優化的A*算法流程圖如圖2所示。

圖2 優化A＊算法流程圖

3 實驗與分析

3.1 實驗數據及預處理

為了滿足實驗的需求，本文采用數據為原始數據基礎上的模擬實驗數據。原始數據采用比例尺為1∶10 000 的某地地形圖和對應的數字高程模型，修改部分為：①地形圖上添加影響越野機動所涉及到的地形要素；②修改數字高程模型，為了驗證高程對越野機動的影響，模擬數據高程設置為海拔3 500 m。一方面滿足實驗對高程的需求，另一方面滿足實驗對六角格網相鄰格元間坡度的需求。

本文研究中，越野機動車輛在通行時，機動速度主要受到地表屬性、坡度和高程的影響。本文采用基于層次分析法來確定越野機動的速度[8]，根據實際調研得到層次分析法中的相關數據，得到相鄰兩格元之間的通行速度。其中，假設不考慮地形因素時，履帶式車輛的速度為60 km/h，如表4所示。

表4 面向履帶式車輛在地形要素影響下的速度表

3.2 實驗分析

論文對A*算法的優化主要是加入了地形因素的影響，包括地表屬性、坡度和高程，而傳統A*算法則不考慮地形因素的影響。首先對模擬實驗地形圖進行基于六角格網的地形量化生成六角格數據，在六角格數據圖層上選取起始格元A 和目標格元B，分別用傳統A*算法和優化后的A*算法進行越野最短路徑規劃。如圖3和圖4所示。

圖3 傳統A＊算法越野路徑規劃結果

圖4 優化A＊算法越野路徑規劃結果

上述結果看出，傳統的A*算法和優化后的A*算法進行越野條件下路徑規劃結果對比，經過專家判讀，優化A*算法更符合實際的路徑規劃方案。優化后的A*算法避開了地表屬性為水域、沼澤、灌木林、居民設施以及不能通行的格邊，找到了最短路徑，具體實驗結果如表5所示。

表5 優化前后的A*算法實驗結果對比

由表5 可知，優化A*算法與傳統A*算法結果對比：①在路徑規劃過程中，考慮地形因素的影響，導致路徑長度增大，實驗結果避開不能通行的六角格格元和格邊，找到最短路徑，提高了算法的準確度；②從最終尋找路徑時間花費上，傳統A*算法占有優勢，但對比單個格元的時間花費上，優化A*算法運行時間更短，提高了算法的運行效率。該實驗驗證了本文算法的可行性，并在此基礎上提高了算法的效率。

4 結 語

本文采用優化A*算法對履帶式車輛的越野路徑規劃問題進行了研究，通過研究地表屬性、坡度和高程對越野路徑規劃的影響，提出基于啟發式A*算法的優化方案，并設計模擬實驗，結果證明本文對A*算法的優化方案可以有效實現越野路徑規劃。下一步工作是對越野路徑規劃影響因素進一步分析與總結，進而制定更加貼合實際的分類方案，并根據實際需求研究多個約束條件綜合目標的最優路徑求解。