一種基於規則網格DEM數據的路徑規劃新方法與流程

2023-10-09 01:29:54 4

本發明涉及路徑規劃技術領域，具體是災害救援中一種基於規則網格dem數據的路徑規劃新方法。

背景技術：

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

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

在路徑規劃或尋路算法中，針對拓撲網絡模型，真實道路中的交叉點、通暢程度、長寬、連通性等屬性信息簡潔、直觀地以拓撲結構中的節點、長度、權值等要素表述，故尋路算法運算量小，效率高，更易於找到最優解；在dem中，上述各要素都需要通過計算去發掘，尋路算法需要進行海量的運算，效率低下，且有可能找不到最優解。然而，dem實現了對區域地形表面的數位化表達，是新一代的地形圖，其應用領域已遍及地形圖應用所涉及的各個行業。

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

技術實現要素：

針對災害救援中的路徑規劃需求，本發明提出一種基於規則網格dem數據的路徑規劃新方法。該方法針對災害救援中救援人員、車輛和設備的運送對路徑的坡度和距離需求，通過評估和約束dem數據中的坡度、距離和dem解析度的影響，設計新的針對dem數據的a*算法(本發明稱該算法為da*算法)評估函數，其在指定的坡度下儘可能地減少距離，提高算法效率和有效性，降低救援抵達時間，提高救援成功率。

實現本發明目的的技術方案是：

一種基於規則網格dem數據的路徑規劃新方法，包括如下步驟：

(1)da*算法中基於指數函數構建新的完備性函數g(n)；

在災害救援中，首先需要能夠搜索到一條從起點到終點的正確路徑。因此，對da*評估函數的設計中，先針對災害救援對坡度和距離的路徑需求，基於dem數據，以坡度和距離設計da*算法新的完備性函數g(n)，具體如下：

g(n)＝d(n)+p(s(n))(1)

其中，n為當前點，d(n)是以當前點與上一點的距離的函數，s(n)為當前點的坡度，p(s(n))是以當前點坡度為參數的函數。

在da*算法的路徑搜索過程中，在每一個搜索點，都會有多個符合條件的點，而在路徑優化時，選擇評價函數值最小的點，其它點將被丟棄，因此d(n)僅需考慮當前點與上一點的距離關係。在基於規則網格的dem數據中，距離的計算需要通過對空間路徑的計算來獲取。

在車輛行駛中，若坡度過大，將會影響救援車輛和救援設備的通行。根據救援車輛和救援設備的需求，設置一個坡度閾值s0，並在閾值制約下進行路徑搜索。為體現距離與坡度的相互影響，獲取合理的代價值，在g(n)中，需要構建一個以坡度為參數的函數，使得當坡度大於等於坡度閾值s0時，該函數的值急劇增加，且其值大於距離函數值；否則，該函數值增長緩慢，其值小於距離函數值。在初等函數中，滿足此變化規律的是指數函數。

將指數函數引入坡度函數，將空間路徑的計算引入距離函數，並以不同權重調整距離函數和坡度函數對完備性函數的影響，則g(n)的新函數構造如下：

g(n)＝q×dg(n,n-1)+(1-q)×esg(n)(2)

其中，q為調整距離函數與坡度函數的權重，dg(n,n-1)為當前點n與其上一點n-1的空間路徑單元距離，sg(n)是當前點n的坡度。

所述空間路徑的距離計算，以點間的高程差和平面距離計算，dg(n,n-1)計算公式為：

其中，h(n)為當前點的高程，h(n-1)為上一點的高程；l(n,n-1)是平面路徑單元距離，其是空間路徑在平面上的投影，受dem數據解析度的影響。dem的解析度是指dem最小單元格的長度，解析度數值越小，解析度越高，刻畫的地形程度越精確，l(n,n-1)越小。

利用大地坐標，l(n,n-1)的計算公式如下：

其中，(xn,yn)、(xn-1,yn-1)分別為當前點n與上一點n-1的大地坐標，x、y分別為從dem數據中所獲取相關點的經度和緯度值；r＝6371393米，為地球半徑。

所述當前點n的坡度sg(n)計算公式為：

其中，fx、fy分別為當前點東西方向的高程變化率和南北方向的高程變化率。在規則網格的dem數據中，通常以中心點周圍3×3的移動窗格計算fx、fy；fx、fy的計算方法有二階差分、三階不帶權差分、簡單差分等算法，本發明採用李天文等人(李天文,劉學軍,陳正江,湯國安,李軍鋒.規則格網dem坡度坡向算法的比較分析[j].乾旱區地理.2004,27(3):398-404.)提出的三階不帶權差分模型的坡度計算方法，具體如下：

其中，zi為窗格編號，g為窗格間距，是規則網格dem數據中一個單元格的長度，單位為米，其隨著dem數據解析度的不同而不同。

(2)基於dem解析度自適應的完備性函數優化；

對於公式(2)中的指數函數esg(n)，在變量sg(n)為10時，其值接近20000。此時，坡度函數值將遠大於距離函數值。若通過調整權重q調整距離和坡度對完備性函數值的影響，會帶來主觀性影響。本發明將通過調整底數，實現坡度對指數函數值的影響。

以實數a替換公式(2)中的指數函數esg(n)的底數e，則g(n)變換如下：

g(n)＝dg(n,n-1)+asg(n)(7)

為保證引入底數a後能夠平衡距離和坡度的影響，建立一個距離與坡度的關聯表達式如下：

dg(n,n-1)＝masg(n)(8)

其中，m為調整距離與坡度的比例係數；

在距離儘可能小，坡度儘可能大的情況下，若公式(8)成立，則a在公式(7)能夠平衡距離與坡度對g(n)的影響；

在公式(8)中，坡度取坡度閾值s0；令m＝10，坡度函數值遠大於距離函數值距離；距離則取平面路徑單位的距離，其小於等於對應的空間路徑單位距離，以d0表示平面路徑單位的平均距離，則公式(8)變換如下：

平面路徑單位只包含了南北、東西方向與對角線方向在規則網格中，東西與南北方向上的平面路徑單位距離相等，而對角線方向則相互之間相等，因此，d0的計算方法就是求南北或東西方向與對角線方向的平面單位路徑距離的均值，即：(解析度不同，平面路徑單位距離不同，d0的值也不同)；

針對實際的規則網格dem數據，任取一個點都可以計算出相應dem數據解析度下對應的d0值，則：將a代入公式(7)，此時，公式(3)計算的距離、公式(5)計算的坡度和底數a，都隨實際環境的dem數據變化而變化，從而使得完備性函數g(n)實現dem數據解析度的自適應性。

(3)路徑的可通行性評估

公式(7)基於對距離和坡度的計算，實現了從起點到終點可達路徑的選擇。在實際應用中，還要考慮地表要素對路徑通行性的影響。利用公式(7)進行路徑搜索的過程中，因設置了坡度閾值s0，坡度超過s0的節點的g(n)代價值都較高，被排除在選擇路徑之外，而高程差對路徑的影響與坡度的影響一致。因此，本發明以地表障礙評估路徑的可通行性。

在地表要素中，將湖泊、河流和沼澤等不可通行的地表要素當作地表障礙。針對所選擇數字地圖區域的地表要素數據，將地表障礙對應坐標的節點標註為地表障礙。在路徑選擇中，先判斷相鄰節點是否為地表障礙，若是則直接加入到da*算法關閉列表，否則根據公式(7)計算各節點的代價。

(4)構造da*算法的新啟發性函數h(n)；

為保持與完備性函數g(n)的一致性，基於距離和坡度的約束關係，構造da*算法的新啟發性函數h(n)如下：

h(n)＝dh(n,end)+ash(n,end)(10)

其中，dh(n,end)為當前點與終點的距離，其計算公式同公式(3)，h(n)、h(end)分別為當前點與終點的高程；dh(n,end)中的l(n,end)計算採用公式(4)；sh(n,end)表示當前點到終點的坡度，其計算公式為：

其中，l(n,end)計算同樣採用公式(4)。

(5)基於權重動態調整的da*尋路新算法優化；

基於公式(7)和公式(10)，da*算法評價函數如下：

公式(12)使得da*算法能夠在距離與坡度約束下找到合適的路徑，但隨著dem數據解析度的提高或搜索路徑距離的增加，da*算法的效率逐步降低。

在數字地圖中，描述dem數據的基本信息包括解析度、採樣點坐標和高程。在進行路徑搜索前，需要先提取對應區域塊中的dem數據，而路徑搜索則在提取的dem數據中進行。

搜索深度描述路徑搜索的程度，是從起點到終點行進的距離，即搜索距離，以當前點與起點的曼哈頓距離計算。

以sd(n)表示當前點n與起點的搜索深度，則sd(n)＝|xn-x0|+|yn-y0|，其中(x0,y0)為起點坐標，(xn,yn)為當前點坐標，該距離越大，則當前點離起點越遠，即搜索深度越深；

以l表示起點與終點的曼哈頓距離，則有l＝|xe-x0|+|ye-y0|，其中(x0,y0)為起點的坐標，(xe,ye)為終點的坐標。

針對提取路徑搜索區域的規則網格dem數據，以dem數據橫縱距離定義其在x和y方向上的曼哈頓距離之和。以demxy表示dem數據橫縱距離，以(xlb,ylb)表示dem數據區域中左下角點的坐標，以(xrb,yrb)表示右下角點的坐標，以(xru,yru)表示右上角點的坐標，以(xlu,ylu)表示左上角點的坐標，則：demxy＝|xrb-xlb|+|ylu-ylb|；

由於搜索路徑的起點與終點位於dem數據對應的區域內部，因此，起點與終點的曼哈頓距離l與dem數據橫縱距離demxy滿足關係：l≤demxy。

在da*算法中，較大的h(n)值會提高啟發性部分對算法的影響。因此，本發明通過調整da*算法中g(n)和h(n)的權重，進一步提高公式(12)da*算法的效率。

以q1、q2分別表示da*算法中g(n)和h(n)的權重，且q1+q2＝1，則有：

f(n)＝q1×g(n)+q2×h(n)(13)

在從起點開始進行搜索時，數據計算量大，為提高搜索效率，需要加大對h(n)的權重；而隨著搜索深度的增加，g(n)值逐步增大，h(n)值逐步減少，為避免過大的權重影響搜索的正確性，逐步降低對h(n)的權值，直到g(n)和h(n)的權重相等，即q1＝q2，維持權重影響的平衡。對g(n)和h(n)的權重動態調整，將有效提高所設計算法在整個搜索過程中的高效性，並通過距離與坡度的約束，搜索到合適的路徑。

以q0表示初始權重，且q0∈[0.5,0.9]，考慮到起點到終點的路徑越長，數據量越大，初始權重也需要相應加大，則令：

其中，l為起點與終點的曼哈頓距離，demxy為dem數據橫縱距離。

以δq表示隨著搜索深度的增加，權重變化的增量，令：

其中，l為起點與終點的曼哈頓距離，sd(n)為當前點n的搜索深度；

基於初始權重q0與權重增量δq，令q2＝q0-δq；q1＝1-q0+δq；

將權重信息代入公式(13)，則新的路徑規劃da*算法的評估函數如下：

(6)在實際環境中，基於dem數據和設置的坡度閾值，計算出算法中的各個參數後，根據公式(16)可以快速搜索出一條從起點到終點的合適路線。

本發明的有益效果是：針對災害救援，提出一種基於規則網格dem數據的路徑規劃新方法，該方法以距離與坡度作為評估關係設計da*尋路新算法，算法能夠在坡度的約束下搜索一條從救援點到受災點的合適路線；該路徑搜索方法適用於所有基於規則網格的dem數據，其可以在電子地圖沒有標註路線，或電子地圖失效如電子地圖系統失效或其所標註的路線被破壞，或電子地圖所標註的路線不合適如坡度超出出行要求時發揮作用；其根據dem實際環境數據進行算法的參數計算，算法具有解析度的自適應性，能夠較好地適應在不同解析度環境下的路徑搜索；算法能夠在路徑搜索過程中，通過權重的動態調整，提高了路徑搜索的效率；該方法通過坡度閾值的調整，也同樣適用於其它各種需要進行路徑搜索的場景，具有應用的廣泛性。

附圖說明

圖1為本發明路徑規劃新方法的流程圖；

圖2為實施例中以當前點為中心點的一個包含3×3個單元格的移動窗格；

圖3為實施例中平面路徑單位示意圖。

具體實施方式

以下結合實施例和附圖對本發明內容做進一步闡述，但不是對本發明的限定。

實施例

如圖1所示，本發明針對災害救援提出了一種基於規則網格dem數據的路徑規劃新方法，具體包括如下步驟：

s1：先進行數據提取並處理；

s1-1：區域選擇，在數字地球中，將救援點設置為起點，將受災點設置為終點；根據起點和終點選擇一塊儘可能小但包含了起點和終點矩形區域；

s1-2：從數字地球中提取所選區域的dem數據；

s1-3：提取所選區域地表障礙並標註。

s2：進行參數計算；

s2-1：設置一個不影響救援車輛和救援設備行駛速度的坡度閾值s0；並標註起點和終點，獲取起點和終點的相關信息，包括坐標值、經緯度、高程值等；

s2-2：從dem數據中獲取單元格即窗格間距g；

s2-3：以圖3所示的平面路徑單位示意圖，根據平面路徑單位的南北或東西方向與對角線方向計算平面單位路徑距離的均值d0，即：

s2-4：根據坡度函數底數公式計算底數a；

s2-5：計算起點與終點的曼哈頓距離l，l＝|xe-x0|+|ye-y0|，其中(x0,y0)為起點坐標，(xe,ye)為終點坐標；

s2-6：計算dem數據橫縱距離demxy，demxy＝|xrb-xlb|+|ylu-ylb|，其中(xlb,ylb)表示dem數據區域中左下角點的坐標，(xrb,yrb)表示右下角點的坐標，(xru,yru)表示右上角點的坐標，(xlu,ylu)表示左上角點的坐標；

s2-7：計算初始權重q0；

s3：構建新的完備性函數g(n)；

s3-1：利用大地坐標，獲取l(n,n-1)計算公式如下：

其中，(xn,yn)、(xn-1,yn-1)分別為當前點n與上一點n-1的大地坐標，x、y分別為從dem數據中所獲取相關點的經度和緯度值；r＝6371393米，為地球半徑；

s3-2：以點間的高程差和平面距離計算空間路徑的距離dg(n,n-1)，其計算公式為：

其中，h(n)為當前點的高程，h(n-1)為上一點的高程；l(n,n-1)是平面路徑單元距離，其是空間路徑在平面上的投影，受dem數據解析度的影響；

s3-3：根據圖2所顯示的以當前點為中心點的一個包含3×3個單元格的移動窗格，計算高程變化率，其方法如下：

其中，fx、fy分別為當前點東西方向的高程變化率和南北方向的高程變化率；zi為圖2中所示的窗格編號；g為窗格間距。

s3-4：當前點n的坡度s(n)計算公式為：

s3-5：構造具有自適應解析度的完備性函數g(n)，其評估函數如下：

g(n)＝dg(n,n-1)+asg(n)

s4：構造新啟發性函數h(n)；

s4-1：採用步驟s3-2的dg(n,n-1)公式建立距離函數dh(n,end)，其中，n、end分別為當前點與終點；

s4-2：以sh(n,end)表示當前點到終點的坡度，其計算公式為：

其中，l(n,end)計算採用步驟s3-1的l(n,n-1)公式，h(n)、h(end)為當前點與終點的高程；

s4-3：構造新啟發性函數h(n)如下：

h(n)＝dh(n,end)+ash(n,end)

s5：構造新的da*算法評價函數f(n)，其函數表示如下：

s6：基於新的da*算法的路徑搜索；

s6-1：讀取起點坐標，設為當前節點；

s6-2：將當前節點周邊8個節點放入open列表；

s6-3：判斷周邊節點是否有終點，如有則轉s6-11結束，否則轉s6-4；

s6-4：計算當前節點的搜索深度sd(n)，sd(n)＝|xn-x0|+|yn-y0|，其中(x0,y0)為起點的坐標，(xn,yn)為當前點的坐標；

根據當前節點搜索深度，計算其權重增量δq，計算方法如下：

s6-5：判斷周邊節點是否為地表障礙；

s6-6：判斷周邊節點是否為地表障礙，若是地表障礙，該節點不可通行，將其加入到closed列表，轉s6-8；否則轉s6-7；

s6-7：根據f(n)函數，計算當前點到非地表障礙周邊節點的代價值；

s6-8：周邊節點計算是否結束，若未結束，轉s6-6；否則轉s6-9；

s6-9：排序，查找代價值最小的周邊節點；

s6-10：設置該節點的父節點為當前節點，並將其移入closed列表，轉s6-2；

s6-11：路徑搜索結束。

通過上述方法可以快速搜索出一條從起點到終點的合適災害救援的路線。