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

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

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

1 基于六角格網(wǎng)的越野路徑規(guī)劃研究

1.1 六角格網(wǎng)地形量化的優(yōu)勢

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

1.2 基于六角格網(wǎng)的越野路徑規(guī)劃數(shù)據(jù)結(jié)構(gòu)設計

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

表1 六角格網(wǎng)格元的數(shù)據(jù)結(jié)構(gòu)設計

根據(jù)對六角格網(wǎng)格邊量化過程的分析研究，設計六角格網(wǎng)格邊的數(shù)據(jù)模型如表2所示。

表2 六角格網(wǎng)格邊的數(shù)據(jù)結(jié)構(gòu)設計

1.3 六角格網(wǎng)數(shù)據(jù)在越野路徑規(guī)劃中的表達

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

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

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

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

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

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

2 啟發(fā)式A＊算法的優(yōu)化

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

2.1 估價函數(shù)的優(yōu)化方法

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

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

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

圖1 越野機動通行示意圖

2.2 優(yōu)化A*算法的流程

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

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

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

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

4）判斷當前六角格網(wǎng)格元是否為目標格元，如果是，跳至步驟7）；否則，繼續(xù)執(zhí)行。

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

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

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

圖2 優(yōu)化A＊算法流程圖

3 實驗與分析

3.1 實驗數(shù)據(jù)及預處理

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

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

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

3.2 實驗分析

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

圖3 傳統(tǒng)A＊算法越野路徑規(guī)劃結(jié)果

圖4 優(yōu)化A＊算法越野路徑規(guī)劃結(jié)果

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

表5 優(yōu)化前后的A*算法實驗結(jié)果對比

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

4 結(jié) 語

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