規則網格數字高程模型中基于距離與坡度的路徑規劃算法

張潤蓮，張 鑫，張楚蕓，奚玉昂

(1.桂林電子科技大學 廣西密碼學與信息安全重點實驗室,廣西 桂林 541004； 2.廣西高校云計算與復雜系統重點實驗室, 廣西 桂林 541004；3.重慶電子工程職業學院 電子與物聯網學院, 重慶 401331)(*通信作者電子郵箱zhangrl@guet.edu.cn)

0 引言

路徑規劃是指移動物體基于特定環境，從起點到終點搜索一條符合要求的路徑。經典的路徑規劃算法或尋路算法主要有蟻群算法、遺傳算法、Dijistra算法、A*算法、人工勢場法和神經網絡等。數字高程模型(Digital Elevation Model, DEM)實現了對區域地形表面的數字化表達，是新一代的地形圖。在DEM中進行路徑規劃，道路中的各要素都需要通過計算去發掘，尋路算法需要進行海量的運算，效率低下。

A*尋路算法[1]是一種啟發式路徑搜索算法，具有運算效率高、搜索空間小的優點，被廣泛應用于游戲地圖尋路、行軍路線規劃、車輛越野路徑規劃、日志模型的校準等方面, 如: 針對柵格地圖，文獻[2]通過對A*算法的啟發性函數改進，提高了四向移動機器人對路徑的搜索速度和平滑度；文獻[3]基于多種權重加速對柵格圖的啟發式搜索；文獻[4]針對路網，在A*算法基礎上，通過權值調整，在多個搜索結果中選擇出最短路徑；Anisyah等[5]則將A*算法與導航網格的尋路策略相結合，優化船舶的行駛路徑；文獻[6]基于A*算法進行多徑尋由，將路徑相似度目標與啟發式方法相結合，降低搜索次數；文獻[7]將A*算法應用到無線傳感器網絡，通過優化的最短路徑進行數據轉發，降低了網絡的能力消耗。

目前，學者們已將A*算法應用到針對DEM數據的路徑規劃中: 文獻[8]采用移動窗口和貪婪準則改進A*算法，以在DEM數據中搜索出可達的路徑; 文獻[9]基于DEM數據，通過計算各柵格的坡度、粗糙度、起伏度識別地形，并采用滑動窗及增量式A*改進算法進行路徑規劃; 文獻[10]利用小波變換進行DEM數據地形處理，以A*算法尋找最短路徑; 文獻[11]基于DEM數據，將坡度、地表要素等對車輛、步兵行進速度的影響納入A*算法評價函數的指標，篩選行駛路線; 文獻[12]基于3D針對多邊形導航網絡提出了一種基于多級k-路分割算法的分層方法，并以A*算法進行搜索，提高搜索效率; 文獻[13]在火星車自主導航中，通過對于DEM數據的處理，采用A*尋路算法進行路徑搜索。

現有針對野外場景中DEM數據的路徑規劃，更多地是考慮通過對DEM數據的處理，直接應用經典的算法如A*算法或通過局部的算法調整再應用; 然而，將A*算法應用于DEM數據進行路徑規劃，在野外場景中需要考慮如下問題：1) DEM數據中蘊含了多種刻畫地形的地形因子信息，如坡度、坡向、地形起伏度等，在路徑規劃中，選擇哪些地形因子進行評估有待研究；2) DEM數據的分辨率直接影響評價函數的計算結果，因此需要評價函數能夠自適應DEM數據的分辨率變化；3) DEM數據隨路徑規劃的區域面積或分辨率的增加呈指數級增長，這使得A*算法的效率急劇下降。

針對上述問題，本文提出一種規則網格DEM數據下基于距離與坡度的改進A*算法(Improved A*algorithm based on Distance and Slope in regular grid DEM data, IA-DS)，以距離和坡度作為指標構造新的評價函數進行路徑搜索，以地表障礙評判路徑的可通行性；根據場景的DEM實際數據，計算評價函數的參數，使得評價函數能夠具有分辨率的自適應性；并通過權重的動態調整，提高算法搜索的效率。

1 IA-DS算法的完備性函數設計

A*算法的評價函數為f(n)=g(n)+h(n)，其中:g(n)是搜索路徑起點到當前迭代點的代價，決定了A*算法能否找到滿足條件的路徑，被稱為完備性函數；h(n)是當前迭代點到終點的估計代價，決定了A*算法的搜索效率，是算法的啟發性函數。完備性函數g(n)和啟發性函數h(n)共同決定了最終的評價結果。在DEM中，地形的不同會影響人員或車輛的行動，主要地形要素包括坡度、高差與高程、地表障礙等。坡度越大，行動越困難；地表障礙則表明路徑難通行。

1.1 基于指數函數的完備性函數設計

在路徑搜索過程中，距離影響通行時間，坡度決定通行難度，這兩者直接影響路徑搜索的結果。針對規則網格DEM數據，在路徑規劃中，本文以距離和坡度評估、選擇通行的節點，并以之構造新的評價函數進行路徑選擇。距離和坡度量綱不同，取值范圍也相差較大，通常坡度取值范圍為[0, 90]；距離則隨起點和終點的不同，其取值范圍變化較大。因此，以距離函數和坡度函數構造新的完備性函數g(n)進行評價可以有效避免兩者不同量綱和取值范圍帶來的影響。

在實際應用中，為保證人員或車輛的通行不受影響，需要根據實際情況，設置一個坡度閾值，并在閾值制約下進行路徑搜索。在這樣的背景下，坡度值可能遠小于距離值，坡度和距離對評價結果的影響可能失衡，導致最終的評價結果不合理。假設坡度閾值為S0，為維持距離函數與坡度函數對評價結果影響的平衡性，g(n)中的距離函數與坡度函數需要具備如下性質[14]：

1)當當前坡度大于等于S0時，坡度函數值急劇增加，且大于距離函數值，此時g(n)主要受坡度大小的影響；

2)當當前坡度小于S0時，坡度函數值增長緩慢，其值小于距離函數值，此時g(n)值主要受距離大小的影響。這符合尋路中的距離要求，并最終選擇距離最小的節點。

指數函數能滿足距離函數與坡度函數的上述性質, 因此，采用指數函數構造坡度函數。在基于規則網格的DEM數據中，距離的計算實際上是指空間路徑距離的計算，依據節點間的高程差和平面距離計算得到，因此，以空間路徑的計算構造距離函數，則構造的完備性函數g(n)如下：

g(n)=D(n,n-1)+esg(n)

(1)

其中:n為當前節點，sg(n)表示當前節點n的坡度。由于在路徑搜索中，算法依次對每一個經過的節點進行評估和篩選，故空間路徑的計算僅考慮相鄰兩點的距離計算，D(n,n-1)表示當前節點n與相鄰節點n-1的空間路徑距離。

對于當前節點n的坡度sg(n)，計算公式如下：

(2)

其中:fx、fy分別為當前節點東西方向和南北方向的高程變化率。在規則網格的DEM數據中，通常采用圖1所示的以中心點周圍3×3的移動窗格計算fx、fy。

圖1 移動窗格

fx、fy的計算方法有二階差分、三階不帶權差分、簡單差分等算法，本文采用文獻[15]中提出的三階不帶權差分模型的坡度計算方法，具體如下：

(3)

其中:zi為圖1中的相應窗格編號節點的高程值；g為網格間距，是規則網格DEM數據中一個單元格長度，單位為米，其隨著DEM數據分辨率的不同而不同。分辨率越高，g越小，其將影響坡度的計算結果。

空間路徑的距離計算，依據節點間的高程差和平面距離。設n和n-1為DEM數據中的兩個相鄰節點，其以經度和緯度標注的大地坐標分別為(Xn,Yn)、(Xn-1,Yn-1)，兩個節點的高程值分別以H(n)、H(n-1)表示，地球半徑常數R=6 371 393 m，以L(n,n-1)表示兩個節點間的平面距離，依據文獻[16]，有：

L(n,n-1)=

(4)

基于兩節點高程差和平面距離，D(n,n-1)計算如下：

D(n,n-1)=

(5)

DEM數據分辨率的變化同樣影響空間距離的計算結果。分辨率越高，g越小，|Xn-Xn-1|越小，L(n,n-1)和D(n,n-1)相應減小。

上述計算方法表明，分辨率的變化直接影響g(n)的代價值，最終影響IA-DS算法的評價結果。在實際應用場景中，DEM數據的分辨率各不相同。為獲得更好的路徑搜索結果，需要設計的算法在尋路過程中能夠自適應分辨率的變化。

1.2 g(n)的DEM分辨率自適應優化方法

在指數函數ex中，當變量x=10時，其值接近20 000。對于g(n)來說，此時坡度函數值將遠大于距離函數值，這會破壞距離函數與坡度函數對g(n)影響的平衡性。

在指數函數中，底數的變化可以影響函數的值。為維持在坡度動態變化時滿足距離函數和坡度函數的平衡性，并適應實際的DEM數據分辨率需求，本節將通過如下方法搜索一個實數a來替換指數函數的底數e。

先以實數a代替指數函數的底數e，g(n)變換如下：

g(n)=D(n,n-1)+asg(n)

(6)

為保證實數a滿足距離和坡度函數的平衡性，在距離盡可能小、坡度盡可能大的情況下，建立一個距離與坡度的關聯表達式如下：

D(n,n-1)=m×asg(n)

(7)

其中:m為系數，調整坡度與距離的比例；在D(n,n-1)與sg(n)不變的情況下，隨著m的加大，a將減小。在m=10時，D(n,n-1)遠大于asg(n)，此時a已盡可能小，其在坡度變化時，對g(n)的影響也將盡可能降低，這將有利于維持距離函數與坡度函數對評價結果的影響。此時，令m=10；坡度取坡度閾值S0；距離則取平面路徑單位距離，其小于等于對應的空間路徑單位距離。

為保證實數a適應不同環境DEM數據分辨率的變化，需要搜索的實數a與實際環境的DEM數據相關聯。根據上述對距離的取值，以D0表示平面路徑單位的平均距離，則式(7)變換如下：

D0=10×aS0

(8)

平面路徑單位只包含了南北、東西方向(N,W)與對角線方向(NW)，其示意圖如圖2所示。

圖2 平面路徑單位示意圖

在規則網格中，東西與南北方向上的平面路徑單位距離相等，而對角線方向則相互之間相等。因此，D0的計算就是求南北或東西方向(N,W)與對角線方向(NW)的平面單位路徑距離的均值，即D0=[(|N|+|NW|)]/2, 其中：N、W、NW均為方向矢量。

將實數a代入式(6)，此時，在g(n)中，D(n,n-1)、sg(n)與a都受DEM數據分辨率的影響。此時，g(n)能夠自適應DEM數據分辨率，且滿足距離與坡度對評價結果的平衡性。

1.3 路徑的可通行性評估

式(6)基于對距離和坡度的計算，實現了從起點到終點可達路徑的選擇，但在野外實際場景中，還需要考慮各地表要素對路徑通行性的影響，如坡度、地形起伏度、地表障礙等。地形起伏度為海拔高度差，可以通過高程差來表示。在DEM數據中，因高程差對路徑的影響與坡度的影響一致，而在路徑搜索過程中設置了坡度閾值S0，坡度超過S0的節點的g(n)代價值都較高，被排除在選擇路徑之外，因此，路徑的可通行性主要通過地表障礙來評估。

在此，采用模擬地表障礙的方法進行評估。在所選擇的數字地圖區域中，模擬湖泊、河流和沼澤等不可通行的地表障礙，在對應的DEM數據中，提取地表障礙標識及其坐標。在路徑選擇中，根據圖1所示的移動窗格，對周邊節點先判斷是否為地表障礙，若是則將其直接加入到Closed列表中，否則計算各節點的代價。

2 IA-DS算法的啟發性函數設計

完備性函數g(n)的設計保證了在距離和坡度相互約束下搜索到合適的路徑，并適應實際應用環境的分辨率變化。與g(n)一樣，h(n)函數同樣基于距離和坡度構造。

以n表示當前節點，end為終點；D(n,end)表示當前節點到終點的距離；L(n,end)為當前節點與終點的平面距離；sh(n,end)表示當前節點到終點的坡度；H(n)、H(end)表示當前點與終點的高程。在路徑搜索過程中，隨著搜索向終點靠近，D(n,end)的值逐步降低，此時，sh(n,end)可有效調整h(n)的大小，避免算法效率過低。新構造的啟發性函數h(n)如下：

h(n)=D(n,end)+ash(n,end)

(9)

其中:D(n,end)以式(5)進行計算；a為g(n)中所計算的實數；sh(n,end)的計算公式為sh(n,end)=arctan(|H(n)-H(end)|/L(n,end))。

3 基于權值動態調整的IA-DS優化方法

基于上述構造的g(n)和h(n)，IA-DS算法評價函數如下：

(10)

式(10)能夠搜索到合適的路徑，但隨著DEM數據分辨率的提高或搜索路徑距離的增加，h(n)可能會逐步降低，IA-DS算法的效率將逐步下降。

從起點開始逐步向終點逼近的搜索過程中，g(n)值和h(n)值是動態變化的。為維持兩個函數值對評價結果影響的平衡，提高搜索效率，需要實現權值的動態調整。在此，先列出幾個相關概念。

定義1 搜索深度。搜索深度即搜索距離，是當前節點與起點的曼哈頓距離。該距離越大，則當前點離起點越遠，即搜索深度越深。以SD(n)表示當前節點n與起點的搜索深度，(X0,Y0)、(Xn,Yn)分別為起點和當前節點在DEM數據中的坐標，則SD(n)=|Xn-X0|+|Yn-Y0|。

以L表示起點與終點的曼哈頓距離，則L=|Xe-X0|+|Ye-Y0|，其中(Xe,Ye)為終點的坐標。

定義2 DEM數據橫縱距離。DEM數據橫縱距離是指在規則網格DEM數據所對應的區域中，在X和Y方向上的曼哈頓距離之和。以DEMXY表示DEM數據橫縱距離，以(XLB,YLB)、(XRB,YRB)、(XRU,YRU)、(XLU,YLU)分別表示DEM數據對應區域的左下角點、右下角點、右上角點、左上角點的坐標，則：DEMXY=|XRB-XLB|+|YLU-YLB|。

由于搜索路徑的起點與終點位于DEM數據對應的區域內部，因此，起點與終點的曼哈頓距離L與DEM數據橫縱距離DEMXY滿足關系：L≤DEMXY。

在IA-DS算法運行初始時期，因搜索深度小,h(n)值較小，為加快搜索速度，可加大h(n)的權值，提高h(n)對評估結果的影響；而隨著搜索深度的增加，可逐步降低h(n)的權值，直到兩個函數的權值相等，則g(n)和h(n)對評估結果的影響趨于平衡，使其能找到合適的路徑，并具有較好的搜索效率。為維持權值的動態變化并滿足上述初始時的搜索效率要求，需要設置一個初始權值q0和一個權值增量Δq，它們的取值范圍為[0,1]，為保證IA-DS算法運行初始時h(n)具有較高的初始權值，并考慮到起點到終點的路徑越長，其權值也應與距離有關，令q0∈[b,c]，則q0計算方法如下：

q0=b+(c-b)×(L/DEMXY)

(11)

其中:b、c為初始權值的范圍下界和上界，L為起點與終點的曼哈頓距離，DEMXY為DEM數據橫縱距離。

隨著搜索深度的增加，需要以Δq逐步降低q0，維持h(n)和g(n)對IA-DS算法的平衡，則Δq計算公式如下：

Δq=(c-b)×(SD(n)/L)

(12)

其中SD(n)為當前節點n的搜索深度。

將q0與Δq代入式(10)中進行權值調整，則IA-DS算法評估函數如下：

(13)

4 實驗及結果分析

4.1 實驗環境

本文采用Java語言實現提出的IA-DS算法，并在World Wind平臺上進行測試。測試計算機硬件配置為Intel Core i5 2430 2.4 GHz，內存4 GB，操作系統為64位Windows 7。

實驗主要測試IA-DS算法的有效性及其在不同DEM數據分辨率下的搜索時間。在有效性方面，測試了IA-DS算法在指定坡度下路徑搜索的成功率，并在相同條件下與文獻[8]進行了對比測試。在上述實驗中，以機器人野外搜索為背景，設定坡度閾值為20度；坡度與距離的比例系數m設置為10；為保證初始權值較大，設b為0.5，c為0.9。

4.2 實驗數據準備

在World Wind平臺上選取了一塊1 000 km2的矩形區域，從區域的左下角起，依次以分辨率0.002°、0.001°、0.000 5°的間隔采樣，提取出該區域的高程數據，保存成文件，形成同一區域三種不同分辨率的DEM數據文件。在區域面積固定的條件下，間隔越低，網格個數越多，網格間的距離越短。三種不同分辨率的DEM數據情況如表1所示。

表1 不同分辨率的DEM數據量

在上述所選擇的區域，模擬地表障礙，并將其與原始DEM數據疊加，疊加后的該區域高程渲染圖如圖3所示，其中，左上方粗樹枝狀為疊加的地表障礙，深色紋路狀的區域為高層值較大區域，其他區域為較平坦區域。

圖3 所選擇區域疊加地表障礙的高程數據渲染圖

4.3 實驗測試及分析

4.3.1 有效性測試

基于上述選擇區域的DEM數據，在地表障礙的附近，設置搜索的起點和終點。在S0為20°時，按照式(13)，在3種不同分辨率DEM數據中多次進行路徑搜索，IA-DS算法搜索結果如圖4所示。

圖4 IA-DS在不同分辨率下的搜索路徑示意圖

圖4的搜索結果表明，IA-DS算法能夠在坡度約束下搜索到從起點到終點的合適路徑。多次搜索，包括在不同計算機上進行搜索，所搜索的路徑節點一致，而搜索的具體信息如表2所示。

表2 動態權值IA-DS算法運行結果

由表2數據可知，隨著分辨率的變化，所計算的底數a和初始權值都相應變化，表明IA-DS算法具有分辨率的自適應性。同時，分辨率越高，DEM數據量急劇增加，算法搜索的時間開銷也激增。在搜索過程中，IA-DS算法能夠遵循坡度的限制，搜索到合適的路徑。

4.3.2 算法效率測試

實驗1 IA-DS算法采用動態權值與未采用動態權值對比測試。

相對于表2,按照式(13)基于動態權值IA-DS算法的測試結果，在同樣的坡度閾值和相同的起點與終點下，對比測試了按照式(10)未采用動態權值的IA-DS算法進行路徑搜索的結果數據如表3所示。

對比表2和表3的結果可知，基于動態權值IA-DS算法，其通過權值的動態調整，隨分辨率的提高，搜索的路徑點數量減少，搜索時間較未采用動態權值的IA-DS算法大幅降低，這表明了權值的動態調整有效提高了算法的效率。

表3 未采用動態權值IA-DS算法測試結果

實驗2 不同算法的對比測試。

在同樣的環境下，對比測試了本文基于動態權值的IA-DS算法和文獻[8]算法進行路徑搜索的結果。在文獻[8]中，其本身并未考慮坡度的限制。因此，在測試中，先測試不對文獻[8]進行坡度限制的測試結果。從測試結果中發現，其坡度極大值近40°。此時，對本文的IA-DS算法，設置坡度閾值S0為40°，兩種算法的測試結果如表4所示。

在上述測試中，坡度閾值的變化，引起IA-DS算法中底數a的變化。兩種算法在同樣坡度限制下的對比測試結果表明，IA-DS算法具有更好的搜索效率。

進一步地，對文獻[8]增加坡度的限制，測試兩個算法均在坡度閾值為20°時的搜索結果，見表5所示。

表4和表5的搜索結果對比表明，在增加或提高了坡度約束后，IA-DS算法與文獻[8]的搜索效率都急劇降低，但IA-DS算法通過距離與坡度的約束及動態權值提高啟發性函數的影響，其效率優于文獻[8]，主要原因在于，雖然兩種算法都是對A*算法的改進，兩種算法的時間復雜度一致；但因兩者計算方法的區別，兩種算法所走路徑有所區別，文獻[8]在尋路過程中覆蓋的范圍更大，其搜索效率相對要低些。

表4 在S0=40°時兩個算法的對比測試結果

表5 在S0=20°時兩個算法的對比測試結果

5 結語

針對規則網格DEM數據，本文提出一種基于A*算法的改進方法。該方法以距離和坡度作為指標，設計新的完備性函數和啟發性函數，并以地表障礙評判路徑的可通行性；函數中的參數，根據實際場景的DEM數據來計算，使得設計的評價函數能夠自適應DEM數據分辨率的變化；通過權重的動態變化，調整啟發性函數的權值，提高算法搜索的效率。實驗測試結果表明了本文算法的有效性，它能夠自適應DEM數據的分辨率變化，并在坡度約束下搜索到合適的路徑。將來的工作中，考慮對基于搜索深度動態權值調整策略作優化，提高算法的效率，并調整搜索路徑的偏差。