規(guī)則網(wǎng)格數(shù)字高程模型中基于距離與坡度的路徑規(guī)劃算法

張潤(rùn)蓮，張 鑫，張楚蕓，奚玉昂

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

0 引言

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

A*尋路算法[1]是一種啟發(fā)式路徑搜索算法，具有運(yùn)算效率高、搜索空間小的優(yōu)點(diǎn)，被廣泛應(yīng)用于游戲地圖尋路、行軍路線規(guī)劃、車(chē)輛越野路徑規(guī)劃、日志模型的校準(zhǔn)等方面, 如: 針對(duì)柵格地圖，文獻(xiàn)[2]通過(guò)對(duì)A*算法的啟發(fā)性函數(shù)改進(jìn)，提高了四向移動(dòng)機(jī)器人對(duì)路徑的搜索速度和平滑度；文獻(xiàn)[3]基于多種權(quán)重加速對(duì)柵格圖的啟發(fā)式搜索；文獻(xiàn)[4]針對(duì)路網(wǎng)，在A*算法基礎(chǔ)上，通過(guò)權(quán)值調(diào)整，在多個(gè)搜索結(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ú)線傳感器網(wǎng)絡(luò)，通過(guò)優(yōu)化的最短路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，降低了網(wǎng)絡(luò)的能力消耗。

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

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

針對(duì)上述問(wèn)題，本文提出一種規(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)造新的評(píng)價(jià)函數(shù)進(jìn)行路徑搜索，以地表障礙評(píng)判路徑的可通行性；根據(jù)場(chǎng)景的DEM實(shí)際數(shù)據(jù)，計(jì)算評(píng)價(jià)函數(shù)的參數(shù)，使得評(píng)價(jià)函數(shù)能夠具有分辨率的自適應(yīng)性；并通過(guò)權(quán)重的動(dòng)態(tài)調(diào)整，提高算法搜索的效率。

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

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

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

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

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

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

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

指數(shù)函數(shù)能滿(mǎn)足距離函數(shù)與坡度函數(shù)的上述性質(zhì), 因此，采用指數(shù)函數(shù)構(gòu)造坡度函數(shù)。在基于規(guī)則網(wǎng)格的DEM數(shù)據(jù)中，距離的計(jì)算實(shí)際上是指空間路徑距離的計(jì)算，依據(jù)節(jié)點(diǎn)間的高程差和平面距離計(jì)算得到，因此，以空間路徑的計(jì)算構(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的坡度。由于在路徑搜索中，算法依次對(duì)每一個(gè)經(jīng)過(guò)的節(jié)點(diǎn)進(jìn)行評(píng)估和篩選，故空間路徑的計(jì)算僅考慮相鄰兩點(diǎn)的距離計(jì)算，D(n,n-1)表示當(dāng)前節(jié)點(diǎn)n與相鄰節(jié)點(diǎn)n-1的空間路徑距離。

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

(2)

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

圖1 移動(dòng)窗格

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

(3)

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

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

L(n,n-1)=

(4)

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

D(n,n-1)=

(5)

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

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

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

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

在指數(shù)函數(shù)中，底數(shù)的變化可以影響函數(shù)的值。為維持在坡度動(dòng)態(tài)變化時(shí)滿(mǎn)足距離函數(shù)和坡度函數(shù)的平衡性，并適應(yīng)實(shí)際的DEM數(shù)據(jù)分辨率需求，本節(jié)將通過(guò)如下方法搜索一個(gè)實(shí)數(shù)a來(lái)替換指數(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滿(mǎn)足距離和坡度函數(shù)的平衡性，在距離盡可能小、坡度盡可能大的情況下，建立一個(gè)距離與坡度的關(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時(shí)，D(n,n-1)遠(yuǎn)大于asg(n)，此時(shí)a已盡可能小，其在坡度變化時(shí)，對(duì)g(n)的影響也將盡可能降低，這將有利于維持距離函數(shù)與坡度函數(shù)對(duì)評(píng)價(jià)結(jié)果的影響。此時(shí)，令m=10；坡度取坡度閾值S0；距離則取平面路徑單位距離，其小于等于對(duì)應(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ù)上述對(duì)距離的取值，以D0表示平面路徑單位的平均距離，則式(7)變換如下：

D0=10×aS0

(8)

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

圖2 平面路徑單位示意圖

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

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

1.3 路徑的可通行性評(píng)估

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

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

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

完備性函數(shù)g(n)的設(shè)計(jì)保證了在距離和坡度相互約束下搜索到合適的路徑，并適應(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)的高程。在路徑搜索過(guò)程中，隨著搜索向終點(diǎn)靠近，D(n,end)的值逐步降低，此時(shí)，sh(n,end)可有效調(diào)整h(n)的大小，避免算法效率過(guò)低。新構(gòu)造的啟發(fā)性函數(shù)h(n)如下：

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

(9)

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

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

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

(10)

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

從起點(diǎn)開(kāi)始逐步向終點(diǎn)逼近的搜索過(guò)程中，g(n)值和h(n)值是動(dòng)態(tài)變化的。為維持兩個(gè)函數(shù)值對(duì)評(píng)價(jià)結(jié)果影響的平衡，提高搜索效率，需要實(shí)現(xiàn)權(quán)值的動(dòng)態(tài)調(diào)整。在此，先列出幾個(gè)相關(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ù)所對(duì)應(yīng)的區(qū)域中，在X和Y方向上的曼哈頓距離之和。以DEMXY表示DEM數(shù)據(jù)橫縱距離，以(XLB,YLB)、(XRB,YRB)、(XRU,YRU)、(XLU,YLU)分別表示DEM數(shù)據(jù)對(duì)應(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ù)對(duì)應(yīng)的區(qū)域內(nèi)部，因此，起點(diǎn)與終點(diǎn)的曼哈頓距離L與DEM數(shù)據(jù)橫縱距離DEMXY滿(mǎn)足關(guān)系：L≤DEMXY。

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

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)對(duì)IA-DS算法的平衡，則Δq計(jì)算公式如下：

Δ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算法評(píng)估函數(shù)如下：

(13)

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

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

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

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

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

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

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

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

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

4.3 實(shí)驗(yàn)測(cè)試及分析

4.3.1 有效性測(cè)試

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

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

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

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

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

4.3.2 算法效率測(cè)試

實(shí)驗(yàn)1 IA-DS算法采用動(dòng)態(tài)權(quán)值與未采用動(dòng)態(tài)權(quán)值對(duì)比測(cè)試。

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

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

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

實(shí)驗(yàn)2 不同算法的對(duì)比測(cè)試。

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

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

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

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

表4 在S0=40°時(shí)兩個(gè)算法的對(duì)比測(cè)試結(jié)果

表5 在S0=20°時(shí)兩個(gè)算法的對(duì)比測(cè)試結(jié)果

5 結(jié)語(yǔ)

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