• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2017-07-19 12:27:20趙德群段建英陳鵬宇蘇晉海
    計算機系統(tǒng)應用 2017年7期
    關(guān)鍵詞:柵格坡度距離

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

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

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

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

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

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

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

    傳統(tǒng)地圖服務已經(jīng)成為人們每天外出必須的功能,其無論是形式還是技術(shù)發(fā)展都較為成熟, 在實際中得到了廣泛應用[1]. 其中, 路徑規(guī)劃在交通導航這個方向上應用廣泛, 極大地方便了人們的外出. 然而, 現(xiàn)有的各大路徑規(guī)劃系統(tǒng)全部是在二維地圖平臺上實現(xiàn), 并且嚴重依賴于交通路網(wǎng)這些數(shù)據(jù)[2], 同時這些路網(wǎng)信息幾乎全部集中于大中城市, 對于鄉(xiāng)鎮(zhè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), 例如森林救火的行進路線自動規(guī)劃、戈壁灘的行車路徑規(guī)劃問題, 規(guī)劃出結(jié)果的同時能在三維地圖上有更為直觀的展示.

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

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

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

    1 研究目標

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

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

    2.1 數(shù)據(jù)準備

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

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

    本文實驗所用的DEM數(shù)據(jù)由測繪無人機進行航飛并通過后期數(shù)據(jù)處理得到grd格式的存儲文件. 本文程序運行前需要預處理將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é)點標識;

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

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

    ● 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é)點標識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到目標柵格的估計值[8], 稱為啟發(fā)函數(shù).

    如果H(i)總是小于或等于從i到目標的實際花費,那么A*算法就能確保找到最短路徑, H(i)的值越小,A*算法要擴展的節(jié)點就越多, 算法就越慢[13]. 對于三維A*算法通常H(i)取歐幾里德距離作為啟發(fā)值, 由于這個啟發(fā)值通常小于柵格i和終點柵格e的實際距離, 因此能夠保證搜索的路徑距離最短, 例如文獻[9]和文獻[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ū)域來說, 地形較為復雜, 而3DBA*算法只考慮最短距離卻沒考慮坡度問題, 因此不能完全適用. 如圖3方框內(nèi)的路線所示, 3DBA*算法計算出來的路徑往往走在陡峭的山坡上, 這樣的路徑過于危險, 并不適合人的行走. 因此, 在3DBA*算法的基礎(chǔ)上, 本文從距離最短和坡度較緩兩方面因素入手提出一種改進型A*算法, 適合于三維山地地形, 適合于人行走同時路徑較短, 本文稱之為3DA*算法. 本文將在下一節(jié)詳細描述3DA*算法的實現(xiàn)方法.

    圖3 3DBA*算法危險路徑

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

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

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

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

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

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

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

    2.3.2 改進算法描述

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

    式(9)中n代表當前被遍歷的地圖節(jié)點, e代表終點節(jié)點,圖4中Center代表當前正在處理的節(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與當前處理節(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對應的數(shù)組坐標、經(jīng)緯度、高度等信息, 需要說明的是如果當前初始化的節(jié)點是起點(Start Point)則此Node的Flag賦值為式(3)中的STARTPOINT,如果當前初始化節(jié)點是終點(EndPoint)則此Node的Flag賦值為式(3)中的DESTINATION, 其他的節(jié)點Flag一律初始化為式(3)中的VIABLE. 從StartPoint開始執(zhí)行, 并當做當前需要處理的節(jié)點存入OpenList.

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

    3) 當前被遍歷到的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) 當NewPoint已經(jīng)在開啟列表中時, 計算此NewPoint相對于中心節(jié)點Center的g(n)值, 如果新計算的g(n)小于之前存儲的g(n)值, 則將此節(jié)點的g(n)值更新為新計算的值, 并將此節(jié)點的父節(jié)點更改為當前的中心節(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ù), 進行了大約50組實驗, 每一組實驗分別記錄了3DBA*算法與改進算法3DA*算法的路徑長度、平均坡度、算法計算時間以及實驗結(jié)果的效果圖.

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

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

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

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

    3.1 實驗效果分析

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

    圖5 實驗效果圖

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

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

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

    (1) 算法所得路徑長度

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

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

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

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

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

    (3) 算法搜索時間

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

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

    4 總結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    14石俊衛(wèi), 包世泰, 馮煜. 基于A*算法的山地最優(yōu)路徑分析.現(xiàn)代計算機, 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ī)劃.計算機系統(tǒng)應用,2017,26(7):146–152. http://www.c-sa.org.cn/1003-3254/5859.html

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

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

    猜你喜歡
    柵格坡度距離
    基于鄰域柵格篩選的點云邊緣點提取方法*
    關(guān)于公路超高漸變段合成坡度解析與應用
    算距離
    基于圖像處理的定位器坡度計算
    電氣化鐵道(2016年4期)2016-04-16 05:59:46
    每次失敗都會距離成功更近一步
    山東青年(2016年3期)2016-02-28 14:25:55
    坡度在巖石風化層解譯中的應用
    河北遙感(2015年2期)2015-07-18 11:11:14
    CT和MR對人上脛腓關(guān)節(jié)面坡度的比較研究
    不同剖面形狀的柵格壁對柵格翼氣動特性的影響
    愛的距離
    母子健康(2015年1期)2015-02-28 11:21:33
    基于CVT排布的非周期柵格密度加權(quán)陣設(shè)計
    雷達學報(2014年4期)2014-04-23 07:43:13
    av福利片在线| 久久婷婷人人爽人人干人人爱 | 老司机深夜福利视频在线观看| 免费在线观看黄色视频的| 国产三级黄色录像| 成人特级黄色片久久久久久久| 午夜久久久久精精品| 一级,二级,三级黄色视频| 欧美黑人欧美精品刺激| 免费在线观看影片大全网站| 波多野结衣巨乳人妻| 女人被狂操c到高潮| 一级片免费观看大全| 久久天堂一区二区三区四区| 91字幕亚洲| 色婷婷久久久亚洲欧美| 最近最新中文字幕大全电影3 | 人人妻,人人澡人人爽秒播| 欧美绝顶高潮抽搐喷水| 欧美中文综合在线视频| 一边摸一边抽搐一进一小说| 免费av毛片视频| 中文亚洲av片在线观看爽| 最新美女视频免费是黄的| 麻豆国产av国片精品| 久久人妻福利社区极品人妻图片| 91成人精品电影| 免费无遮挡裸体视频| 啦啦啦韩国在线观看视频| 中出人妻视频一区二区| 久久久久九九精品影院| 国产欧美日韩精品亚洲av| 国产亚洲精品第一综合不卡| 超碰成人久久| 91大片在线观看| 色尼玛亚洲综合影院| 久久国产精品影院| 男人的好看免费观看在线视频 | 国产亚洲欧美98| 一边摸一边抽搐一进一小说| 美女高潮到喷水免费观看| 国产一区在线观看成人免费| 老熟妇仑乱视频hdxx| 国产精品98久久久久久宅男小说| 国产成人免费无遮挡视频| 黄色丝袜av网址大全| 欧美一级毛片孕妇| 国产色视频综合| 亚洲av日韩精品久久久久久密| 脱女人内裤的视频| 欧美黄色淫秽网站| 国产麻豆成人av免费视频| 国产精品美女特级片免费视频播放器 | 99久久综合精品五月天人人| 很黄的视频免费| 亚洲色图 男人天堂 中文字幕| 国产欧美日韩一区二区精品| 在线av久久热| 精品无人区乱码1区二区| 日韩高清综合在线| a在线观看视频网站| 给我免费播放毛片高清在线观看| 日本 欧美在线| 色精品久久人妻99蜜桃| 他把我摸到了高潮在线观看| 一级毛片高清免费大全| 久久国产乱子伦精品免费另类| 丝袜人妻中文字幕| 一级毛片高清免费大全| 日韩精品免费视频一区二区三区| 欧美最黄视频在线播放免费| 亚洲第一欧美日韩一区二区三区| 一区在线观看完整版| 久久久久久久久久久久大奶| 亚洲狠狠婷婷综合久久图片| 丝袜美腿诱惑在线| av有码第一页| 88av欧美| 亚洲片人在线观看| 免费看a级黄色片| 精品少妇一区二区三区视频日本电影| 亚洲精品在线美女| 99久久久亚洲精品蜜臀av| 亚洲精品中文字幕在线视频| 身体一侧抽搐| 亚洲全国av大片| av在线播放免费不卡| 男女床上黄色一级片免费看| 免费观看人在逋| 国产成人精品无人区| 亚洲国产欧美一区二区综合| av网站免费在线观看视频| 亚洲aⅴ乱码一区二区在线播放 | 人妻久久中文字幕网| 热99re8久久精品国产| 亚洲五月婷婷丁香| 色播亚洲综合网| 国产黄a三级三级三级人| 两个人免费观看高清视频| 黑人巨大精品欧美一区二区蜜桃| 久久国产精品影院| 午夜福利影视在线免费观看| 免费在线观看日本一区| 多毛熟女@视频| 亚洲欧美精品综合久久99| 在线观看日韩欧美| 久久性视频一级片| 亚洲精品中文字幕一二三四区| 亚洲久久久国产精品| 国产xxxxx性猛交| 女人被躁到高潮嗷嗷叫费观| 黑人巨大精品欧美一区二区mp4| 精品久久久精品久久久| 我的亚洲天堂| 法律面前人人平等表现在哪些方面| 可以在线观看的亚洲视频| 国产av又大| 大香蕉久久成人网| 久久精品91无色码中文字幕| 黄频高清免费视频| 91成人精品电影| 女性被躁到高潮视频| 亚洲午夜理论影院| 亚洲色图综合在线观看| 国产精品一区二区免费欧美| 91麻豆av在线| 国内精品久久久久久久电影| 国产精品久久视频播放| 亚洲狠狠婷婷综合久久图片| 1024香蕉在线观看| 精品国产一区二区三区四区第35| 欧美一区二区精品小视频在线| 国产精品免费视频内射| 乱人伦中国视频| 成人三级黄色视频| 精品国产亚洲在线| 一边摸一边抽搐一进一出视频| 麻豆一二三区av精品| 国产人伦9x9x在线观看| 狂野欧美激情性xxxx| 精品一区二区三区四区五区乱码| 国产极品粉嫩免费观看在线| 亚洲五月婷婷丁香| 国产成人精品久久二区二区免费| 一区在线观看完整版| 色播亚洲综合网| 国产av精品麻豆| 亚洲成av片中文字幕在线观看| 亚洲国产看品久久| 亚洲 国产 在线| 国产精品1区2区在线观看.| 精品高清国产在线一区| 法律面前人人平等表现在哪些方面| 美女 人体艺术 gogo| 国产精品久久视频播放| 亚洲九九香蕉| 欧美激情 高清一区二区三区| 宅男免费午夜| 他把我摸到了高潮在线观看| 18禁观看日本| 不卡av一区二区三区| 中文字幕精品免费在线观看视频| 又黄又爽又免费观看的视频| 天天躁夜夜躁狠狠躁躁| 波多野结衣av一区二区av| 亚洲片人在线观看| 丰满的人妻完整版| 精品国产美女av久久久久小说| 1024香蕉在线观看| 日本 av在线| 黄色 视频免费看| 国产高清视频在线播放一区| 精品国产超薄肉色丝袜足j| 婷婷精品国产亚洲av在线| 人人妻,人人澡人人爽秒播| 亚洲精品久久成人aⅴ小说| 欧美在线黄色| 色综合亚洲欧美另类图片| 亚洲精品粉嫩美女一区| 18禁国产床啪视频网站| 亚洲激情在线av| 88av欧美| 少妇被粗大的猛进出69影院| 国产欧美日韩精品亚洲av| 亚洲一码二码三码区别大吗| 亚洲av熟女| 久久久久久久久久久久大奶| 一级,二级,三级黄色视频| 最近最新免费中文字幕在线| 中亚洲国语对白在线视频| 1024视频免费在线观看| 青草久久国产| 69精品国产乱码久久久| 久99久视频精品免费| 99香蕉大伊视频| av福利片在线| 三级毛片av免费| 操美女的视频在线观看| 午夜精品久久久久久毛片777| 欧美乱妇无乱码| 可以在线观看的亚洲视频| 非洲黑人性xxxx精品又粗又长| 一进一出抽搐动态| 中亚洲国语对白在线视频| 好男人在线观看高清免费视频 | 国产在线观看jvid| 亚洲av成人不卡在线观看播放网| 夜夜看夜夜爽夜夜摸| 老汉色∧v一级毛片| 久久婷婷成人综合色麻豆| 日本免费一区二区三区高清不卡 | 青草久久国产| 免费在线观看黄色视频的| 日本vs欧美在线观看视频| 亚洲五月天丁香| 搡老妇女老女人老熟妇| 黑丝袜美女国产一区| 亚洲九九香蕉| av网站免费在线观看视频| 18禁裸乳无遮挡免费网站照片 | 亚洲欧美日韩无卡精品| 久久精品国产亚洲av香蕉五月| 香蕉丝袜av| 一级作爱视频免费观看| 多毛熟女@视频| 欧美性长视频在线观看| 一边摸一边做爽爽视频免费| 精品一品国产午夜福利视频| 亚洲av日韩精品久久久久久密| 亚洲精华国产精华精| 国产欧美日韩综合在线一区二区| 亚洲第一欧美日韩一区二区三区| 脱女人内裤的视频| 欧美乱色亚洲激情| 老汉色∧v一级毛片| 亚洲精品在线观看二区| 日韩欧美一区二区三区在线观看| 欧美激情极品国产一区二区三区| 一级片免费观看大全| 欧美丝袜亚洲另类 | 亚洲精品av麻豆狂野| 免费在线观看视频国产中文字幕亚洲| 亚洲专区国产一区二区| 少妇粗大呻吟视频| 纯流量卡能插随身wifi吗| 少妇被粗大的猛进出69影院| 亚洲av熟女| 三级毛片av免费| 丰满人妻熟妇乱又伦精品不卡| 欧美绝顶高潮抽搐喷水| 日本免费一区二区三区高清不卡 | tocl精华| 在线播放国产精品三级| 9191精品国产免费久久| 午夜两性在线视频| 搡老岳熟女国产| 90打野战视频偷拍视频| 日本一区二区免费在线视频| 搡老熟女国产l中国老女人| 亚洲五月色婷婷综合| 大型黄色视频在线免费观看| 久久精品国产清高在天天线| 亚洲av电影在线进入| 日韩大码丰满熟妇| 老司机午夜十八禁免费视频| 午夜成年电影在线免费观看| 黄色毛片三级朝国网站| 国语自产精品视频在线第100页| 天天躁夜夜躁狠狠躁躁| 亚洲片人在线观看| 视频区欧美日本亚洲| 一级片免费观看大全| bbb黄色大片| 亚洲天堂国产精品一区在线| 男男h啪啪无遮挡| 国产精品1区2区在线观看.| 好男人电影高清在线观看| 两个人免费观看高清视频| 女性生殖器流出的白浆| 免费人成视频x8x8入口观看| 日本一区二区免费在线视频| 亚洲国产精品久久男人天堂| 一级毛片精品| 天天一区二区日本电影三级 | 男女之事视频高清在线观看| 国产熟女午夜一区二区三区| 欧美成人免费av一区二区三区| 亚洲精品av麻豆狂野| 777久久人妻少妇嫩草av网站| www.自偷自拍.com| 亚洲片人在线观看| 国产精品日韩av在线免费观看 | 成人永久免费在线观看视频| 国产午夜福利久久久久久| av视频免费观看在线观看| 亚洲aⅴ乱码一区二区在线播放 | 亚洲成人免费电影在线观看| 在线观看一区二区三区| 丝袜美腿诱惑在线| 久久久精品国产亚洲av高清涩受| 啦啦啦观看免费观看视频高清 | 女性生殖器流出的白浆| 久久性视频一级片| www.熟女人妻精品国产| 天天一区二区日本电影三级 | 欧美色视频一区免费| 欧美中文综合在线视频| 免费在线观看视频国产中文字幕亚洲| 精品电影一区二区在线| 91精品三级在线观看| 色精品久久人妻99蜜桃| 自拍欧美九色日韩亚洲蝌蚪91| netflix在线观看网站| 欧美亚洲日本最大视频资源| 久久久水蜜桃国产精品网| av福利片在线| 成年版毛片免费区| 国产一区二区三区综合在线观看| 久久久久国产一级毛片高清牌| 国产亚洲精品久久久久久毛片| 啦啦啦 在线观看视频| 我的亚洲天堂| 亚洲成人免费电影在线观看| 久久中文字幕人妻熟女| 日本在线视频免费播放| 纯流量卡能插随身wifi吗| 黄色视频,在线免费观看| 国产成人av教育| 成人三级做爰电影| 男男h啪啪无遮挡| 亚洲精品在线美女| 国产av一区二区精品久久| 制服丝袜大香蕉在线| 国产欧美日韩综合在线一区二区| 亚洲天堂国产精品一区在线| 又紧又爽又黄一区二区| 免费av毛片视频| 99riav亚洲国产免费| 久久影院123| 日韩欧美国产一区二区入口| 久久精品国产亚洲av高清一级| 级片在线观看| 日韩国内少妇激情av| 欧美日本亚洲视频在线播放| 国产一区二区三区综合在线观看| 欧美色视频一区免费| 色av中文字幕| 女性被躁到高潮视频| 成人三级黄色视频| 丝袜美腿诱惑在线| 免费不卡黄色视频| 真人做人爱边吃奶动态| 久久久久久免费高清国产稀缺| 18禁国产床啪视频网站| 嫁个100分男人电影在线观看| 色综合欧美亚洲国产小说| 99国产精品一区二区三区| 亚洲美女黄片视频| 国产精品av久久久久免费| 99久久国产精品久久久| 成人欧美大片| 亚洲专区中文字幕在线| 亚洲精品国产精品久久久不卡| 午夜精品在线福利| 亚洲情色 制服丝袜| 激情在线观看视频在线高清| 亚洲欧美日韩无卡精品| 亚洲九九香蕉| 女人精品久久久久毛片| 日日爽夜夜爽网站| 999久久久精品免费观看国产| 99re在线观看精品视频| 久久中文字幕人妻熟女| 国产成人一区二区三区免费视频网站| 久久 成人 亚洲| 日韩精品青青久久久久久| 露出奶头的视频| 人人妻人人澡人人看| 免费一级毛片在线播放高清视频 | 亚洲九九香蕉| 首页视频小说图片口味搜索| 韩国av一区二区三区四区| 亚洲全国av大片| 90打野战视频偷拍视频| 亚洲欧美激情综合另类| 咕卡用的链子| 人人妻人人澡欧美一区二区 | 国产在线精品亚洲第一网站| 亚洲熟女毛片儿| 国产成人精品在线电影| bbb黄色大片| 亚洲av片天天在线观看| 久久人人97超碰香蕉20202| 成人亚洲精品一区在线观看| 国产成人一区二区三区免费视频网站| 亚洲av成人一区二区三| 男女午夜视频在线观看| а√天堂www在线а√下载| 色尼玛亚洲综合影院| 侵犯人妻中文字幕一二三四区| 丰满的人妻完整版| 久久久久国内视频| 国产成人av激情在线播放| 亚洲电影在线观看av| 天堂动漫精品| 一区在线观看完整版| 国产激情欧美一区二区| 日韩精品青青久久久久久| 亚洲九九香蕉| 欧美另类亚洲清纯唯美| 又紧又爽又黄一区二区| 国产精品久久久久久精品电影 | 久久久久久大精品| 黄色片一级片一级黄色片| 热re99久久国产66热| 欧美在线黄色| 最近最新免费中文字幕在线| 欧美一级a爱片免费观看看 | 两性夫妻黄色片| 国产熟女xx| 国产真人三级小视频在线观看| 国产亚洲精品久久久久5区| www国产在线视频色| 国产精品乱码一区二三区的特点 | 国产成人av教育| 国产熟女xx| av在线播放免费不卡| 免费看十八禁软件| 高清在线国产一区| 一区二区三区激情视频| 国产亚洲欧美在线一区二区| 97超级碰碰碰精品色视频在线观看| 黑人操中国人逼视频| 波多野结衣av一区二区av| 夜夜爽天天搞| 亚洲色图综合在线观看| 亚洲自拍偷在线| 一级片免费观看大全| 脱女人内裤的视频| 涩涩av久久男人的天堂| 久久精品成人免费网站| 高潮久久久久久久久久久不卡| 日韩欧美国产一区二区入口| 最近最新中文字幕大全免费视频| 9热在线视频观看99| 亚洲 国产 在线| 男女下面插进去视频免费观看| 精品第一国产精品| 日韩精品青青久久久久久| 日日干狠狠操夜夜爽| 久久久久久久久免费视频了| 人人妻人人澡欧美一区二区 | 天天一区二区日本电影三级 | 中文字幕最新亚洲高清| 日韩免费av在线播放| 黄色视频,在线免费观看| 熟女少妇亚洲综合色aaa.| 老汉色∧v一级毛片| 国产av精品麻豆| 精品久久久久久久久久免费视频| 自线自在国产av| 一个人观看的视频www高清免费观看 | 久久精品91蜜桃| 亚洲狠狠婷婷综合久久图片| 美女扒开内裤让男人捅视频| 12—13女人毛片做爰片一| 亚洲av第一区精品v没综合| 高潮久久久久久久久久久不卡| 欧美日本亚洲视频在线播放| 18禁裸乳无遮挡免费网站照片 | 国产国语露脸激情在线看| 色老头精品视频在线观看| 19禁男女啪啪无遮挡网站| 法律面前人人平等表现在哪些方面| 999精品在线视频| 母亲3免费完整高清在线观看| 日日爽夜夜爽网站| 亚洲片人在线观看| 一级作爱视频免费观看| 老司机在亚洲福利影院| 色综合站精品国产| 人妻久久中文字幕网| 男人舔女人的私密视频| 亚洲精华国产精华精| 精品卡一卡二卡四卡免费| 午夜福利,免费看| e午夜精品久久久久久久| 国产精品亚洲一级av第二区| av在线天堂中文字幕| 正在播放国产对白刺激| 午夜福利18| 国产熟女午夜一区二区三区| 免费无遮挡裸体视频| 成人免费观看视频高清| 国产人伦9x9x在线观看| 国产亚洲精品第一综合不卡| 国产色视频综合| 色老头精品视频在线观看| 久久精品人人爽人人爽视色| xxx96com| 国产又爽黄色视频| 久久精品成人免费网站| 国产熟女xx| 中文字幕人妻丝袜一区二区| 欧美日韩亚洲国产一区二区在线观看| 老熟妇仑乱视频hdxx| 99国产精品一区二区蜜桃av| 男男h啪啪无遮挡| 亚洲,欧美精品.| 少妇的丰满在线观看| 久久久久久人人人人人| 午夜免费激情av| 岛国在线观看网站| 亚洲av电影在线进入| 久久国产精品人妻蜜桃| 美女午夜性视频免费| 欧美日韩一级在线毛片| 亚洲精品一卡2卡三卡4卡5卡| 丝袜美腿诱惑在线| 日日爽夜夜爽网站| 精品国产美女av久久久久小说| 亚洲欧美精品综合久久99| 亚洲专区中文字幕在线| 亚洲五月天丁香| 亚洲专区字幕在线| 亚洲中文av在线| 黄片播放在线免费| 国产av一区二区精品久久| 大码成人一级视频| 黑人巨大精品欧美一区二区蜜桃| 国产亚洲av嫩草精品影院| 757午夜福利合集在线观看| 国产精品爽爽va在线观看网站 | av有码第一页| 97超级碰碰碰精品色视频在线观看| 亚洲精品国产区一区二| 宅男免费午夜| 18禁黄网站禁片午夜丰满| 激情视频va一区二区三区| 亚洲aⅴ乱码一区二区在线播放 | 黄色视频不卡| 精品第一国产精品| avwww免费| 亚洲第一欧美日韩一区二区三区| 日韩免费av在线播放| 91国产中文字幕| 国产精品免费视频内射| 亚洲欧美一区二区三区黑人| 亚洲国产日韩欧美精品在线观看 | 在线播放国产精品三级| 国产又爽黄色视频| 日本vs欧美在线观看视频| 亚洲专区国产一区二区| 欧美成人性av电影在线观看| 色播在线永久视频| 黄色视频不卡| 人人澡人人妻人| 男女床上黄色一级片免费看| 国产片内射在线| 久久精品国产亚洲av香蕉五月| 欧美成人免费av一区二区三区| 亚洲少妇的诱惑av| 久久这里只有精品19| 伊人久久大香线蕉亚洲五| 久9热在线精品视频| 亚洲精品中文字幕在线视频| 欧美成人一区二区免费高清观看 | 欧美日韩瑟瑟在线播放| 欧美日韩亚洲综合一区二区三区_| 在线国产一区二区在线| 免费高清在线观看日韩| 在线国产一区二区在线| 成人亚洲精品一区在线观看| 一级毛片精品| 欧美激情极品国产一区二区三区| 99精品在免费线老司机午夜| 中文字幕人妻丝袜一区二区| 亚洲在线自拍视频| 久久中文看片网| 制服人妻中文乱码| 国产欧美日韩精品亚洲av| 最近最新中文字幕大全电影3 | 成人国产综合亚洲| 午夜亚洲福利在线播放| 欧美 亚洲 国产 日韩一| 叶爱在线成人免费视频播放| av电影中文网址| 久久人妻熟女aⅴ| 超碰成人久久| 啪啪无遮挡十八禁网站| 777久久人妻少妇嫩草av网站| 亚洲国产精品成人综合色| 亚洲专区字幕在线| 91av网站免费观看| 一本大道久久a久久精品| 免费女性裸体啪啪无遮挡网站| 在线观看舔阴道视频| 俄罗斯特黄特色一大片| 中文字幕精品免费在线观看视频| 国产伦人伦偷精品视频| 欧美激情久久久久久爽电影 | 女人爽到高潮嗷嗷叫在线视频| 欧美日韩亚洲综合一区二区三区_| 757午夜福利合集在线观看| 亚洲精品久久国产高清桃花| 精品少妇一区二区三区视频日本电影| 欧美乱妇无乱码| 国产一区二区三区视频了| 午夜精品在线福利| 亚洲成人久久性| 三级毛片av免费| 国产亚洲精品第一综合不卡| 亚洲成国产人片在线观看| 久久国产精品男人的天堂亚洲| 亚洲avbb在线观看|