[發(fā)明專利]一種基于規(guī)則網(wǎng)格DEM數(shù)據(jù)的路徑規(guī)劃新方法

有效

• 申請?zhí)枺?/td>: 201710345987.4
• 申請日: 2017-05-17
• 公開（公告）號: CN107228668B
• 公開（公告）日: 2020-03-10
• 發(fā)明（設計）人: 張潤蓮;張鑫;張楚蕓;葉志博;武小年
• 申請（專利權(quán)）人: 桂林電子科技大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 楊雪梅

本發(fā)明公開了一種基于規(guī)則網(wǎng)格DEM數(shù)據(jù)的路徑規(guī)劃新方法，以距離和坡度作為路徑搜索的評估指標，為平衡距離與坡度的相互影響，基于空間路徑的距離函數(shù)和以指數(shù)函數(shù)構(gòu)造的坡度函數(shù)，設計DA*算法的完備性函數(shù)g(n)；以DEM數(shù)據(jù)計算函數(shù)中的參數(shù)，對新的完備性函數(shù)g(n)進行優(yōu)化，使其適應DEM數(shù)據(jù)不同分辨率的變化；基于同樣的策略和函數(shù)構(gòu)造方法，構(gòu)造DA*算法新的啟發(fā)性函數(shù)h(n)；為提高算法的搜索效率，通過對初始權(quán)值的設置，以及在搜索過程中對權(quán)值的動態(tài)調(diào)整，改變完備性函數(shù)和啟發(fā)性函數(shù)對評估結(jié)果的影響，使得構(gòu)造的新的DA*尋路算法能夠高效地搜索出合適的路徑，具有對DEM數(shù)據(jù)分辨率的自適應性，且適用于不同的應用環(huán)境。

技術領域

本發(fā)明涉及路徑規(guī)劃技術領域，具體是災害救援中一種基于規(guī)則網(wǎng)格DEM數(shù)據(jù)的路徑規(guī)劃新方法。

背景技術

災害救援是國家或社會對因遭遇各種災害而陷入困境的災民進行搶救和援助的一項社會救助制度。在救援點和受災點之間設計一條最佳的救援路徑，使得救援人員、救援車輛、救援設備以最短時間抵達受災點開展救援，是保證救援成功率的關鍵。而救援車輛和設備通常較為沉重，在坡度較高的地區(qū)，其行駛速度將受到極大的影響，而繞行則會延長距離，這些延遲了救援的速度。因此，如何在坡度和距離兩方面進行平衡，在救援點和受災點之間尋找一條最佳的路徑，縮短救援抵達的時間，是災害救援中需要解決的關鍵問題。

當前，人們通行一般會采用電子地圖選擇路線，如百度地圖、高德地圖等。電子地圖是數(shù)字地圖的一種具體表現(xiàn)，通過對數(shù)字地圖、遙感數(shù)字圖象及自行數(shù)字化采集的數(shù)據(jù)進行可視化處理后，形成數(shù)字信號和模擬信號顯示在計算機屏幕或數(shù)字設備上。電子地圖的使用有其局限性：(1)因電子地圖制作工作量大，地圖更新慢；(2)電子地圖并不完善，許多地區(qū)尚未被覆蓋；(3)自然災害也可能破壞電子地圖所標定的路線；(4)電子地圖只描述了道路的存在與否，而更詳細的信息如坡度等則沒有涉及。在這樣的條件下，采用更底層的網(wǎng)格型數(shù)字高程模型(Digital Elevation Model，DEM)數(shù)據(jù)進行路徑規(guī)劃顯得非常重要。但目前針對DEM數(shù)據(jù)的路徑規(guī)劃方法較少。

在路徑規(guī)劃或?qū)ぢ匪惴ㄖ校槍ν負渚W(wǎng)絡模型，真實道路中的交叉點、通暢程度、長寬、連通性等屬性信息簡潔、直觀地以拓撲結(jié)構(gòu)中的節(jié)點、長度、權(quán)值等要素表述，故尋路算法運算量小，效率高，更易于找到最優(yōu)解；在DEM中，上述各要素都需要通過計算去發(fā)掘，尋路算法需要進行海量的運算，效率低下，且有可能找不到最優(yōu)解。然而，DEM實現(xiàn)了對區(qū)域地形表面的數(shù)字化表達，是新一代的地形圖，其應用領域已遍及地形圖應用所涉及的各個行業(yè)。

A*算法是一種解決圖遍歷問題的啟發(fā)式路徑搜索算法，其評價函數(shù)為f(n)＝g(n)+h(n)，其中，g(n)是搜索路徑起點到當前迭代點的代價，決定了A*算法能否找到滿足條件的路徑，是A*算法的完備性部分，被稱為完備性函數(shù)；h(n)是當前迭代點到搜索路徑終點的估計代價，h(n)需要滿足條件h(n)≤h^*(n)，h^*(n)為當前點到終點的真實代價，其決定了A*算法的搜索效率，是算法的啟發(fā)性函數(shù)。A*尋路算法具有運算效率高，搜索空間小的優(yōu)點。該算法可用于拓撲網(wǎng)絡模型(如城市道路)及網(wǎng)格模型(如網(wǎng)格型數(shù)字高程模型)，被廣泛應用于游戲地圖尋路、行軍路線規(guī)劃、車輛越野路徑規(guī)劃、日志模型的校準等方面。但因DEM數(shù)據(jù)量大，A*算法在進行DEM數(shù)據(jù)處理時，需要迭代大量的點使得算法效率隨著DEM數(shù)據(jù)尺寸的增加而急劇下降。同時，DEM分辨率作為刻畫地形精確程度的一個重要指標，分辨率數(shù)值越小，分辨率越高，刻畫的地形程度越精確，而數(shù)據(jù)量也呈幾何級數(shù)增長，這也將降低A*算法的效率。為保證A*算法有解且效率高，需要針對具體的應用場景設計合適的評價函數(shù)。而目前基于DEM數(shù)據(jù)的A*尋路算法研究較少。

發(fā)明內(nèi)容