趙德群, 段建英, 陳鵬宇, 蘇晉海

(北京工業(yè)大學(xué) 信息學(xué)部, 北京 100124)

基于A*算法的三維地圖最優(yōu)路徑規(guī)劃①

趙德群, 段建英, 陳鵬宇, 蘇晉海

(北京工業(yè)大學(xué) 信息學(xué)部, 北京 100124)

研究了基于A*算法的適合人步行行走的山地環(huán)境下三維地圖最優(yōu)路徑規(guī)劃算法及實現(xiàn). 本文考慮了三維山地?zé)o路網(wǎng)信息覆蓋的條件較差環(huán)境, 對A*算法進(jìn)行改進(jìn), 并利用三維地形DEM數(shù)據(jù)計算出一條相對平緩且長度較短的三維路徑. 改進(jìn)算法對三維條件下路徑最短的評價標(biāo)準(zhǔn)由原有的空間距離累加最短改進(jìn)為先將空間等效成水平距離, 再計算距離是否最短. 同時, 本文充分考慮了搜索點周圍環(huán)境的整體坡度信息作為啟發(fā)信息, 來降低算法尋找的路徑走在陡坡上的概率. 實驗表明, 本算法最終計算出的三維最優(yōu)路徑在平緩度及路徑最短上有所改善, 基本符合人步行行走的習(xí)慣.

A*算法; 三維地圖; 山地; 最優(yōu)路徑規(guī)劃; DEM

傳統(tǒng)地圖服務(wù)已經(jīng)成為人們每天外出必須的功能,其無論是形式還是技術(shù)發(fā)展都較為成熟, 在實際中得到了廣泛應(yīng)用[1]. 其中, 路徑規(guī)劃在交通導(dǎo)航這個方向上應(yīng)用廣泛, 極大地方便了人們的外出. 然而, 現(xiàn)有的各大路徑規(guī)劃系統(tǒng)全部是在二維地圖平臺上實現(xiàn), 并且嚴(yán)重依賴于交通路網(wǎng)這些數(shù)據(jù)[2], 同時這些路網(wǎng)信息幾乎全部集中于大中城市, 對于鄉(xiāng)鎮(zhèn)以及山地等偏遠(yuǎn)地區(qū)幾乎找不到路網(wǎng)信息. 通過路網(wǎng)信息的輔助, 可以很容易的規(guī)劃處一條最優(yōu)的路徑, 但在沒有路網(wǎng)的條件下現(xiàn)在的路徑規(guī)劃算法卻毫無辦法.

在二維路網(wǎng)式路徑規(guī)劃給人們帶來便利的同時,人們對路徑規(guī)劃的要求也有所提高, 由二維轉(zhuǎn)向三維、由有路網(wǎng)轉(zhuǎn)向無路網(wǎng), 例如森林救火的行進(jìn)路線自動規(guī)劃、戈壁灘的行車路徑規(guī)劃問題, 規(guī)劃出結(jié)果的同時能在三維地圖上有更為直觀的展示.

對于三維路徑規(guī)劃問題, 目前主要的算法有蟻群算法、遺傳算法、粒子群算法、人工勢能算法、A*算法等. 文獻(xiàn)[3-5]分別對蟻群算法進(jìn)行了改進(jìn)并應(yīng)用到三維路徑規(guī)劃問題中, 取得了一定效果, 但是蟻群算法收斂速度慢、容易陷入局部最優(yōu)解的問題沒有得到有效解決; 文獻(xiàn)[6]利用遺傳算法提出了一種針對于AUV海底三維路徑規(guī)劃的解決方案, 對AUV的安全航行起到了重要的參考價值, 但算法容易出現(xiàn)早熟及穩(wěn)定性較差; 文獻(xiàn)[7,8]針對于飛行器飛行安全問題提出了基于粒子群算法的三維路徑規(guī)劃算法, 簡化了模型及參數(shù)調(diào)整的步驟, 提升了飛行器飛行的有效性, 同時該算法也出現(xiàn)了搜索過程過早結(jié)束難以找到最優(yōu)解的問題.

文獻(xiàn)[9]將啟發(fā)函數(shù)與人工勢場法相結(jié)合進(jìn)行了仿真, 仿真結(jié)果可以避開障礙物同時進(jìn)行了平滑處理, 但是算法得出的結(jié)果是否最優(yōu)難以確定. 文獻(xiàn)[10-14]分別利用A*算法并進(jìn)行改進(jìn), 在二維網(wǎng)格或者游戲地圖型中進(jìn)行仿真, 得出較為滿意的路徑, 為三維路徑規(guī)劃問題提供了參考, 但是以上算法大多采用簡單的二維或三維仿真模型進(jìn)行試驗, 數(shù)據(jù)量和復(fù)雜程度都遠(yuǎn)遠(yuǎn)低于真實地形地圖, 不具備一定的實用性.

本文針對于山地沒有路網(wǎng)覆蓋的情形, 利用A*算法并在考慮三維地形坡度問題的基礎(chǔ)上對原有算法進(jìn)行改進(jìn)和優(yōu)化, 得出一條位于三維地圖兩點之間的坡度符合人步行行進(jìn)且路徑最短的最優(yōu)路徑, 同時在三維實景地圖展示最后的規(guī)劃路徑結(jié)果, 滿足了人的視覺需求, 具有一定的實用性.

1 研究目標(biāo)

本文致力于研究出一種針對于山地, 適合人步行前進(jìn)的坡度平緩且路徑長度最短的路徑. 本文采用三維地圖模型進(jìn)行實驗以更加接近人在山區(qū)行進(jìn)的真實環(huán)境. 在給定實驗區(qū)域任意兩點的情況下, 能夠?qū)崟r計算出適合人行走的路徑, 同時顯示在三維實景地圖上. 三維實景地圖的最優(yōu)路徑規(guī)劃問題可以直觀地表示為圖1.

2 三維路徑規(guī)劃算法實現(xiàn)

2.1 數(shù)據(jù)準(zhǔn)備

三維地圖山地最優(yōu)路徑規(guī)劃的問題實質(zhì)上就是將一個已知的三維實景地圖模型進(jìn)行柵格化處理, 利用DEM(高程模型)數(shù)據(jù)將一個三維地圖降維成二維柵格地圖進(jìn)而利用二維柵格中存儲的數(shù)據(jù)進(jìn)行計算得出最優(yōu)路徑的問題.

圖1 三維路徑規(guī)劃

本文實驗所用的DEM數(shù)據(jù)由測繪無人機(jī)進(jìn)行航飛并通過后期數(shù)據(jù)處理得到grd格式的存儲文件. 本文程序運行前需要預(yù)處理將grd文件里存儲的DEM數(shù)據(jù)解析、讀出并存儲到特定形式的數(shù)據(jù)結(jié)構(gòu)中.

圖2 DEM數(shù)據(jù)映射圖

如圖2所示, 本文將一片DEM數(shù)據(jù)轉(zhuǎn)化為圖示下方的二維映射, 其中DEM數(shù)據(jù)集合可表示為:

其中D為DEM數(shù)據(jù)集合, Xmin表示整片區(qū)域最小經(jīng)度,Xmax表示最大經(jīng)度, Ymin表示最小緯度, Ymax表示最大緯度, NumCol表示DEM數(shù)據(jù)的總列數(shù), NumRow表示DEM的總行數(shù).

二維映射可以表示為一個由NumCol*NumRow個Node節(jié)點的二維數(shù)組: Data[NumCol][NumRow].

● Flag——節(jié)點標(biāo)識;

● X——節(jié)點所處二維數(shù)組的橫坐標(biāo);

● Y——節(jié)點所處二維數(shù)據(jù)的總坐標(biāo);

● Longtitude——節(jié)點經(jīng)度;

● Latitude——節(jié)點緯度;

● Elevation——節(jié)點高程;

● Value_h——節(jié)點到終點的啟發(fā)值;

● Value_g——節(jié)點到起點走過的實際值;

● Value_f——Value_h與Value_g的和;

● Parent——節(jié)點的父節(jié)點.

上式中節(jié)點標(biāo)識Flag可以表示為:

● VIABLE——節(jié)點可以通行;

● UNVIABLE——節(jié)點不適合通行;

● INOPEN——節(jié)點在開放列表(開放列表將在下節(jié)闡述)中;

● INCLOSE——節(jié)點在關(guān)閉列表(關(guān)閉列表將在下節(jié)闡述)中;

● STARTPOINT——節(jié)點為起始節(jié)點;

● DESTINATION——節(jié)點為終止節(jié)點.

2.2 基本算法介紹

A* 算法引入了估值函數(shù): , G(i)是柵格i到起始柵格的已知最短距離, 稱為代價函數(shù);H(i)是柵格i到目標(biāo)柵格的估計值[8], 稱為啟發(fā)函數(shù).

如果H(i)總是小于或等于從i到目標(biāo)的實際花費,那么A*算法就能確保找到最短路徑, H(i)的值越小,A*算法要擴(kuò)展的節(jié)點就越多, 算法就越慢[13]. 對于三維A*算法通常H(i)取歐幾里德距離作為啟發(fā)值, 由于這個啟發(fā)值通常小于柵格i和終點柵格e的實際距離, 因此能夠保證搜索的路徑距離最短, 例如文獻(xiàn)[9]和文獻(xiàn)[14]皆用到了歐幾里德距離作為啟發(fā)值. 啟發(fā)值H(i)取柵格i和終點柵格e之間的三維距離, 計算公式:

其中(Rowi, Coli)為柵格i的行列號, zi為柵格i的高程,Size為柵格的分辨率. G(i)為柵格i到起始柵格s的已知最短距離, 其計算公式為:

其中 為柵格i的父柵格i-1到起始柵格s的累積最短距離, L為柵格i到其父柵格i-1的距離, 在通常情況下L取的是兩點之間的三維空間直線距離. 對于上述算法,本文稱之為3DBA*算法.

3DBA*算法理論上能夠搜索到一條最短的路徑,比較適合于二維地圖和較為簡單的規(guī)則三維游戲地圖模型. 經(jīng)過實驗本文發(fā)現(xiàn)由真實DEM數(shù)據(jù)表示的山地區(qū)域來說, 地形較為復(fù)雜, 而3DBA*算法只考慮最短距離卻沒考慮坡度問題, 因此不能完全適用. 如圖3方框內(nèi)的路線所示, 3DBA*算法計算出來的路徑往往走在陡峭的山坡上, 這樣的路徑過于危險, 并不適合人的行走. 因此, 在3DBA*算法的基礎(chǔ)上, 本文從距離最短和坡度較緩兩方面因素入手提出一種改進(jìn)型A*算法, 適合于三維山地地形, 適合于人行走同時路徑較短, 本文稱之為3DA*算法. 本文將在下一節(jié)詳細(xì)描述3DA*算法的實現(xiàn)方法.

圖3 3DBA*算法危險路徑

2.3 改進(jìn)算法(3DA*)的實現(xiàn)

2.3.1 坡面與水平地面距離的等效

文獻(xiàn)[15]中Chyi-Rong等人兼顧坡度及體能消耗等多種因素并在多處山地環(huán)境下進(jìn)行親身測試得出人在山地步行行走的速度與坡度的關(guān)系如下所示:

式中V為人的步行速度, slope為地形坡度的正切值

由式(6)可以推出: V0=4/3(坡度為0時速度)

由式(6)和V0=4/3可以推出在坡度為slope的山地上行走單位距離S與等效水平地面距離S0的比值為:

由式(6)可以看出, 在坡上行走的速度隨坡度增大減小, 坡度增大的同時也會增加體能的消耗[10]. 再由式(7)可以發(fā)現(xiàn)利用式(5)所表達(dá)的空間距離評價已走路徑是否為最短并不科學(xué), 因為在坡面上行走單位距離并不等于相同的水平距離, 在坡面上行走較為困難, 實際等效成的水平距離要大于相對應(yīng)的坡面距離. 本文提出, 評價路徑最短的標(biāo)準(zhǔn)可以將式(5)坡面上行走的坡面距離由式(7)先等效成水平距離, 再判斷距離是否最短.

2.3.2 改進(jìn)算法描述

式(8)只是在考慮了坡度影響人行走速度的情況下提出的新的評價山地地形最短路徑的標(biāo)準(zhǔn), 一定程度上影響了算法尋找出的路徑, 使路徑坡度總體變緩, 但是實驗結(jié)果發(fā)現(xiàn)在不改變2.2節(jié)所述3DBA*算法啟發(fā)函數(shù)h(n)的情況下, 算法尋找出的路徑仍然存在2.2節(jié)提出的路徑走在陡坡上的問題. 因此本文對啟發(fā)函數(shù)h(n)進(jìn)行了改進(jìn):

式(9)中n代表當(dāng)前被遍歷的地圖節(jié)點, e代表終點節(jié)點,圖4中Center代表當(dāng)前正在處理的節(jié)點, Center的周圍節(jié)點(圖4中A～H節(jié)點)代表待遍歷的節(jié)點. 式(9)中其他符號表示如下所述.

圖4 處理節(jié)點Center與遍歷節(jié)點A-F

dln-e表示A～H中的被遍歷到的節(jié)點n與終點e的水平距離; dln-e表示A～H中的被遍歷到的節(jié)點n與終點e的高度差值;表示A～H中的被遍歷到的節(jié)點n與終點e的坡度正切值表示A～H中的被遍歷到的節(jié)點n與當(dāng)前處理節(jié)點Center的坡度正切值(如).

需要注意的是如果式slopen的值大于0.35時, 本文將此節(jié)點的Flag置為UNVIABLE.

2.3.3 實現(xiàn)步驟

算法需要建立兩個列表來存儲節(jié)點數(shù)據(jù), 一個為“開啟列表”, 本文稱之為OpenList, 用來存儲等待檢查的節(jié)點; 另一個為“關(guān)閉列表”, 本文稱之為CloseList, 用來存儲不需要再次檢查的節(jié)點.

以下為算法的流程:

1) 首先初始化式(2)中存放Node節(jié)點數(shù)據(jù)的二維數(shù)組, 初始化過程中將每個Node分別根據(jù)DEM數(shù)據(jù)計算出每個Node對應(yīng)的數(shù)組坐標(biāo)、經(jīng)緯度、高度等信息, 需要說明的是如果當(dāng)前初始化的節(jié)點是起點(Start Point)則此Node的Flag賦值為式(3)中的STARTPOINT,如果當(dāng)前初始化節(jié)點是終點(EndPoint)則此Node的Flag賦值為式(3)中的DESTINATION, 其他的節(jié)點Flag一律初始化為式(3)中的VIABLE. 從StartPoint開始執(zhí)行, 并當(dāng)做當(dāng)前需要處理的節(jié)點存入OpenList.

2) 從OpenList中取f(n)值最小的節(jié)點(如果OpenList中只有起點則為StartPoint)作為當(dāng)前待處理的節(jié)點如圖4所示Center. 遍歷Center節(jié)點周圍可以到達(dá)的8個節(jié)點(圖4中A～H), 如果發(fā)現(xiàn)這8個節(jié)點內(nèi)已經(jīng)出現(xiàn)Flag為DESTINATION的節(jié)點, 終點找到, 退出路徑搜索, 執(zhí)行步驟8.

3) 當(dāng)前被遍歷到的8個節(jié)點中的某個節(jié)點本文稱之為NewPoint, 如果NewPoint的通行狀態(tài)Flag為UNVIABLE或INCLOSE, 則代表此節(jié)點地形無法通過或這個節(jié)點已經(jīng)被存放于CloseList中, 跳過此節(jié)點, 繼續(xù)遍歷下一點; 否則, 執(zhí)行下一步. 如果周圍8個節(jié)點遍歷完畢, 執(zhí)行步驟7.

4) 如果NewPoint的Flag為VIABLE, 節(jié)點可通行,則將它放入“開啟列表” OpenList, Flag置為INOPEN, 同時將其 “父節(jié)點”置為Center, 然后執(zhí)行步驟5; 如果NewPoint已經(jīng)在開啟列表中, 跳過步驟5, 執(zhí)行步驟6.

5) 如果式(10)或式(11)計算出NewPoint的slopen的值大于0.35, 將此節(jié)點的Flag置為不可通行狀態(tài)UNVIABLE, 否則計算NewPoint的g(n)和h(n)以及f(n),之后, 將NewPoint存入OpenList, 并且OpenList中的節(jié)點總是按f(n)的值升序排列, 執(zhí)行完畢, 返回步驟3遍歷下一個節(jié)點.

6) 當(dāng)NewPoint已經(jīng)在開啟列表中時, 計算此NewPoint相對于中心節(jié)點Center的g(n)值, 如果新計算的g(n)小于之前存儲的g(n)值, 則將此節(jié)點的g(n)值更新為新計算的值, 并將此節(jié)點的父節(jié)點更改為當(dāng)前的中心節(jié)點Center, 否則, 本文將什么都不做, 返回步驟3遍歷下一個節(jié)點.

7) 將OpenList的第一個節(jié)點(f(n)最小的節(jié)點)移入CloseList, 返回2繼續(xù)執(zhí)行直到找到終點為止.

8) 由終點Node開始根據(jù)Parent節(jié)點往前追溯, 直到追溯到Parent為null的起點, 得出出一條存儲路徑的鏈表, 尋路過程結(jié)束.

3 實驗

本文利用一片大致10 km*10 km, 節(jié)點間隔5 m的DEM數(shù)據(jù), 進(jìn)行了大約50組實驗, 每一組實驗分別記錄了3DBA*算法與改進(jìn)算法3DA*算法的路徑長度、平均坡度、算法計算時間以及實驗結(jié)果的效果圖.

需要說明的是本文記錄的路徑長度是將利用式(7)將空間距離根據(jù)坡度信息等效成水平距離后得出的數(shù)據(jù), 最終本文評價所得路徑長度的標(biāo)準(zhǔn)為:

其中slopei為節(jié)點i與節(jié)點i-1之間的坡度正切值, Interval在本實驗中如果不在圖4對角節(jié)點時為5 m, 否則乘1.4為7 m.

本文記錄的路徑平均坡度就是計算得出的軌跡點串相鄰點的坡度正切值累加和再除以點數(shù)取均值得出的數(shù)據(jù), 本文評價所得路徑坡度的標(biāo)準(zhǔn)為:

本文記錄的算法計算時間即從開始搜素到搜索結(jié)束找到終點程序運行的時間.

3.1 實驗效果分析

實驗的效果圖如圖5所示, 點線代表原始3DBA*算法結(jié)果, 實線代表本文改進(jìn)的3DA*算法, 圖下方定位點代表起點, 圖上方定位點代表終點. 本文從實驗結(jié)果中任意截取了兩幅上坡的路徑(a)(b)與兩組下坡的路徑圖(c)(d), 效果圖如圖5所示.

圖5 實驗效果圖

從實驗結(jié)果效果圖直觀分析, 3DBA*的點線路徑大多沒有顧及到山坡的陡峭性, 本文的算法所得出的實線路徑相對較為平緩, 且基本避開了較為陡峭的山坡轉(zhuǎn)而尋找較為平緩且距離相對最近的路.

3.2 實驗數(shù)據(jù)分析

本文根據(jù)實驗所得的50組結(jié)果數(shù)據(jù)進(jìn)行統(tǒng)計, 將最終的結(jié)果分別按路徑從小到大的進(jìn)行顯示, 并用EXCEL軟件做出數(shù)據(jù)走向的趨勢.

(1) 算法所得路徑長度

圖6 路徑長度統(tǒng)計

由圖6可以看出, 實體曲線代表的原始算法計算出的等效水平路徑長度幾乎總是在改進(jìn)算法路勁長度的上方, 從虛線代表的各自趨勢線也可以看出, 兩種算法最終算出的路徑長度幾乎相等, 但總的趨勢是改進(jìn)算法稍優(yōu)一點.

(2)算法所得路徑平均坡度

圖7 平均坡度統(tǒng)計

由圖7可以看出, 原始算法的平均坡度除極少數(shù)情況小于改進(jìn)算法, 其他絕大部分情況明顯大于改進(jìn)算法的平均坡度, 由此也可以說明本算法尋找出的路徑明顯要平緩很多, 更適合人行走的要求.

(3) 算法搜索時間

圖8 算法時間統(tǒng)計

從圖8統(tǒng)計數(shù)據(jù)來觀察, 兩種算法的計算時間有大有小, 很難分清哪種算法用的時間少. 但是, 由于本文將數(shù)據(jù)根據(jù)路徑長度由小到大的順序重新進(jìn)行了統(tǒng)計,本文通過EXCEL軟件做出的虛線代表的趨勢線可以看出, 改進(jìn)算法在范圍較小的區(qū)域內(nèi)搜索路徑時, 搜索時間大于原始算法的搜索時間, 但隨著搜索范圍的增大,本文的改進(jìn)算法搜索的時間有小于原始算法搜索時間的趨勢. 此外, 從數(shù)據(jù)上看, 本算法尋找路徑的范圍在方圓10公里左右, 在這個范圍內(nèi)算法所用的時間基本上小于1200 ms, 在這樣復(fù)雜的地形環(huán)境下, 算法時間基本可以忍受.

4 總結(jié)

本文著眼于三維實景地圖, 并針對于地形較為復(fù)雜的山地, 在傳統(tǒng)A*最優(yōu)路徑搜索算法的基礎(chǔ)上, 經(jīng)過改進(jìn)得出一種適合于山地行走的最優(yōu)路徑搜索算法.本改進(jìn)算法通過將有坡度的路徑空間距離等效為水平距離重新定義了評價路徑長短的標(biāo)準(zhǔn), 并通過此標(biāo)準(zhǔn)記錄算法實際走過的路程, 與此同時本文充分考慮了搜索點周圍環(huán)境的整體坡度信息作為啟發(fā)信息, 來降低算法尋找的路徑走在陡坡上的概率. 通過實驗可以看出, 本文的改進(jìn)算法較之基礎(chǔ)算法, 整體坡度更為平緩, 等效為水平路徑的長度比基礎(chǔ)算法稍短, 算法運算時間隨著搜索范圍的增大有小于基礎(chǔ)算法的趨勢. 綜合以上內(nèi)容, 本文可以得出結(jié)論: 本文的算法在針對山地這一類地勢較為復(fù)雜的三維地形時能夠搜索出一條坡度適于人行走, 距離較短的路徑, 且在方圓10公里這樣的范圍內(nèi)搜索時間對于人來說能夠接受.

1張棟海, 韓麗華, 肖雄兵, 等. 導(dǎo)航地圖發(fā)展現(xiàn)狀和趨勢分析. 地理信息世界, 2013, 20(2): 20–23, 36.

2王俊. 面向智能交通的路徑規(guī)劃相關(guān)技術(shù)研究[碩士學(xué)位論文]. 南京: 南京大學(xué), 2013.

3王弋. 基于高程環(huán)境與蟻群算法的三維路徑規(guī)劃研究[碩士學(xué)位論文]. 西安: 西安工業(yè)大學(xué), 2014.

4黃玲, 胡蔚蔚. 基于改進(jìn)蟻群算法的果蔬采摘機(jī)器人三維路徑規(guī)劃. 農(nóng)機(jī)化研究, 2016, (9): 38–42.

5黃勁潮. 一種基于改進(jìn)蟻群算法的山地三維路徑規(guī)劃算法. 荊楚理工學(xué)院學(xué)報, 2014, 29(2): 40–44.

6郝燕玲, 張京娟. 基于遺傳算法的AUV三維海底路徑規(guī)劃.中國工程科學(xué), 2003, 5(11): 56–60. [doi: 10.3969/j.issn.1009-1742.2003.11.008]

7張航, 劉梓溪. 基于量子行為粒子群算法的微型飛行器三維路徑規(guī)劃. 中南大學(xué)學(xué)報(自然科學(xué)版), 2013, 44(S2): 58–62.

8李摯, 宋頂立, 張雙江, 等. 兩種改進(jìn)的最優(yōu)路徑規(guī)劃算法.北京科技大學(xué)學(xué)報, 2005, 27(3): 367–370.

9陳春梅. 無人機(jī)快速三維航跡規(guī)劃算法的研究[碩士學(xué)位論文]. 成都: 電子科技大學(xué), 2015.

10王鵬程, 夏潔. 基于特殊雙向A*搜索算法的三維航跡規(guī)劃.系統(tǒng)仿真學(xué)報, 2009, 20(增刊): 229–233.

11邱磊. 利用跳點搜索算法加速A*尋路. 蘭州理工大學(xué)學(xué)報,2015, 41(3): 102–107.

12祁悅, 趙洋, 楊帆. 一種基于A*算法的分層路徑規(guī)劃在3D游戲中的應(yīng)用研究. 電子設(shè)計工程, 2014, 22(14): 37–39,42. [doi: 10.3969/j.issn.1674-6236.2014.14.012]

13崔振興, 顧治華. 基于A*算法的游戲地圖最短路徑搜索.軟件導(dǎo)刊, 2007, (17): 145–147.

14石俊衛(wèi), 包世泰, 馮煜. 基于A*算法的山地最優(yōu)路徑分析.現(xiàn)代計算機(jī), 2013, (14): 9–11, 15.

15Chiou CR, Tsai WL, Leung YF. A GIS-dynamic segmentation approach to planning travel routes on forest trail networks in Central Taiwan. Landscape and Urban Planning, 2010, 97(4): 221–228. [doi: 10.1016/j.landurbplan.2010.06.004]

Optimal Path Planning for 3D Map Based on A*Algorithm

ZHAO De-Qun, DUAN Jian-Ying, CHEN Peng-Yu, SU Jin-Hai
(Beijing University of Technology, Department of Information, Beijing 100124, China)

The optimal path planning algorithm and implementation of 3D map based on A * algorithm in mountainous environment are studied in this paper. It considers the condition of poor coverage of 3D mountain-free network information coverage, improves the A * algorithm and uses 3D terrain DEM data to calculate a relatively smooth and short three-dimensional path. The improved algorithm can improve the shortest path evaluation criterion in threedimensional space from the original spatial distance accumulation to the shortest distance, and then calculates whether the distance is the shortest. At the same time, the global gradient information of the surroundings of the search point is considered as the heuristic information to reduce the probability that the path the algorithm looks for is steep.Experimental results show that the proposed algorithm can improve the smoothness and shortest path of the threedimensional optimal path, which accords with the walking habits of human beings.

A * algorithm; three-dimensional map; mountain; optimal path planning; DEM

趙德群,段建英,陳鵬宇,蘇晉海.基于A*算法的三維地圖最優(yōu)路徑規(guī)劃.計算機(jī)系統(tǒng)應(yīng)用,2017,26(7):146–152. http://www.c-sa.org.cn/1003-3254/5859.html

國家重大科研儀器設(shè)備研制專項(1L001790201501)

2016-11-02; 收到修改稿時間: 2016-12-08