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

(1.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗室,廣西 桂林 541004； 2.廣西高校云計算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗室, 廣西 桂林 541004；3.重慶電子工程職業(yè)學(xué)院 電子與物聯(lián)網(wǎng)學(xué)院, 重慶 401331)(*通信作者電子郵箱zhangrl@guet.edu.cn)

0 引言

路徑規(guī)劃是指移動物體基于特定環(huán)境，從起點(diǎn)到終點(diǎn)搜索一條符合要求的路徑。經(jīng)典的路徑規(guī)劃算法或?qū)ぢ匪惴ㄖ饕邢伻核惴?、遺傳算法、Dijistra算法、A*算法、人工勢場法和神經(jīng)網(wǎng)絡(luò)等。數(shù)字高程模型(Digital Elevation Model, DEM)實(shí)現(xiàn)了對區(qū)域地形表面的數(shù)字化表達(dá)，是新一代的地形圖。在DEM中進(jìn)行路徑規(guī)劃，道路中的各要素都需要通過計算去發(fā)掘，尋路算法需要進(jìn)行海量的運(yùn)算，效率低下。

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

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

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

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

1 IA-DS算法的完備性函數(shù)設(shè)計

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

1.1 基于指數(shù)函數(shù)的完備性函數(shù)設(shè)計

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

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

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

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

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

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

(1)

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

對于當(dāng)前節(jié)點(diǎn)n的坡度sg(n)，計算公式如下：

(2)

其中:fx、fy分別為當(dāng)前節(jié)點(diǎn)東西方向和南北方向的高程變化率。在規(guī)則網(wǎng)格的DEM數(shù)據(jù)中，通常采用圖1所示的以中心點(diǎn)周圍3×3的移動窗格計算fx、fy。

圖1 移動窗格

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

(3)

其中:zi為圖1中的相應(yīng)窗格編號節(jié)點(diǎn)的高程值；g為網(wǎng)格間距，是規(guī)則網(wǎng)格DEM數(shù)據(jù)中一個單元格長度，單位為米，其隨著DEM數(shù)據(jù)分辨率的不同而不同。分辨率越高，g越小，其將影響坡度的計算結(jié)果。

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

L(n,n-1)=

(4)

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

D(n,n-1)=

(5)

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

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

1.2 g(n)的DEM分辨率自適應(yīng)優(yōu)化方法

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

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

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

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

(6)

為保證實(shí)數(shù)a滿足距離和坡度函數(shù)的平衡性，在距離盡可能小、坡度盡可能大的情況下，建立一個距離與坡度的關(guān)聯(lián)表達(dá)式如下：

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

(7)

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

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

D0=10×aS0

(8)

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

圖2 平面路徑單位示意圖

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

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

1.3 路徑的可通行性評估

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

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

2 IA-DS算法的啟發(fā)性函數(shù)設(shè)計

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

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

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

(9)

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

3 基于權(quán)值動態(tài)調(diào)整的IA-DS優(yōu)化方法

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

(10)

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

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

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

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

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

由于搜索路徑的起點(diǎn)與終點(diǎn)位于DEM數(shù)據(jù)對應(yīng)的區(qū)域內(nèi)部，因此，起點(diǎn)與終點(diǎn)的曼哈頓距離L與DEM數(shù)據(jù)橫縱距離DEMXY滿足關(guān)系：L≤DEMXY。

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

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

(11)

其中:b、c為初始權(quán)值的范圍下界和上界，L為起點(diǎn)與終點(diǎn)的曼哈頓距離，DEMXY為DEM數(shù)據(jù)橫縱距離。

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

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

(12)

其中SD(n)為當(dāng)前節(jié)點(diǎn)n的搜索深度。

將q0與Δq代入式(10)中進(jìn)行權(quán)值調(diào)整，則IA-DS算法評估函數(shù)如下：

(13)

4 實(shí)驗及結(jié)果分析

4.1 實(shí)驗環(huán)境

本文采用Java語言實(shí)現(xiàn)提出的IA-DS算法，并在World Wind平臺上進(jìn)行測試。測試計算機(jī)硬件配置為Intel Core i5 2430 2.4 GHz，內(nèi)存4 GB，操作系統(tǒng)為64位Windows 7。

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

4.2 實(shí)驗數(shù)據(jù)準(zhǔn)備

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

表1 不同分辨率的DEM數(shù)據(jù)量

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

圖3 所選擇區(qū)域疊加地表障礙的高程數(shù)據(jù)渲染圖

4.3 實(shí)驗測試及分析

4.3.1 有效性測試

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

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

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

表2 動態(tài)權(quán)值IA-DS算法運(yùn)行結(jié)果

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

4.3.2 算法效率測試

實(shí)驗1 IA-DS算法采用動態(tài)權(quán)值與未采用動態(tài)權(quán)值對比測試。

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

對比表2和表3的結(jié)果可知，基于動態(tài)權(quán)值IA-DS算法，其通過權(quán)值的動態(tài)調(diào)整，隨分辨率的提高，搜索的路徑點(diǎn)數(shù)量減少，搜索時間較未采用動態(tài)權(quán)值的IA-DS算法大幅降低，這表明了權(quán)值的動態(tài)調(diào)整有效提高了算法的效率。

表3 未采用動態(tài)權(quán)值IA-DS算法測試結(jié)果

實(shí)驗2 不同算法的對比測試。

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

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

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

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

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

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

5 結(jié)語

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