[發明專利]一種基于規則網格DEM數據的路徑規劃新方法

有效

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

1.一種基于規則網格DEM數據的路徑規劃新方法，其特征在于，包括如下步驟：

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

針對災害救援對坡度和距離的路徑需求，基于DEM數據，以坡度和距離設計DA*算法新的完備性函數g(n)，具體如下：

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

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

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

g(n)＝q×DG(n,n-1)+(1-q)×e^sg(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數據分辨率的影響；

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

其中，(X_n,Y_n)、(X_n-1,Y_n-1)分別為當前點n與上一點n-1的大地坐標，X、Y分別為從DEM數據中所獲取相關點的經度和緯度值；R＝6371393米，為地球半徑；

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

其中，f_x、f_y分別為當前點東西方向的高程變化率和南北方向的高程變化率；在規則網格的DEM數據中，通常以中心點周圍3×3的移動窗格計算f_x、f_y；f_x、f_y的計算方法采用三階不帶權差分模型的坡度計算方法，具體如下：

其中，z_i為窗格編號，g為窗格間距，是規則網格DEM數據中一個單元格的長度，單位為米，其隨著DEM數據分辨率的不同而不同；

(2)基于DEM分辨率自適應的完備性函數優化；

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

g(n)＝DG(n,n-1)+a^sg(n) (7)

為保證引入底數a后能夠滿足距離和坡度的約束關系，建立一個距離與坡度的關聯表達式如下：

DG(n,n-1)＝ma^sg(n) (8)

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

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

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

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

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

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

針對所選擇數字地圖區域的地表要素數據，將地表障礙對應坐標的節點標注為地表障礙；在路徑選擇中，先判斷相鄰節點是否為地表障礙，若是則直接加入到DA*算法關閉列表，否則根據公式(7)計算各節點的代價；

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

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

h(n)＝DH(n,end)+a^sh(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*算法評價函數如下：

計算搜索深度，其以當前點與起點的曼哈頓距離計算，以SD(n)表示當前點n與起點的搜索深度，則SD(n)＝|X_n-X₀|+|Y_n-Y₀|，其中(X₀,Y₀)為起點坐標，(X_n,Y_n)為當前點坐標，該距離越大，則當前點離起點越遠，即搜索深度越深；

以L表示起點與終點的曼哈頓距離，則有L＝|X_e-X₀|+|Y_e-Y₀|，其中(X₀,Y₀)為起點坐標，(X_e,Y_e)為終點坐標；

以DEM_XY表示DEM數據橫縱距離，以(X_LB,Y_LB)表示DEM數據區域中左下角點的坐標，以(X_RB,Y_RB)表示右下角點的坐標，以(X_RU,Y_RU)表示右上角點的坐標，以(X_LU,Y_LU)表示左上角點的坐標，則：DEM_XY＝|X_RB-X_LB|+|Y_LU-Y_LB|；

由于搜索路徑的起點與終點位于DEM數據對應的區域內部，因此，起點與終點的曼哈頓距離L與DEM數據橫縱距離DEM_XY滿足關系：L≤DEM_XY；

調整DA*算法中g(n)和h(n)的權重，進一步提高公式(12)DA*算法的效率，以q₁、q₂分別表示DA*算法中g(n)和h(n)的權重，且q₁+q₂＝1，則有：

f(n)＝q₁×g(n)+q₂×h(n) (13)

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

其中，L為起點與終點的曼哈頓距離，DEM_XY為DEM數據橫縱距離，

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

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

基于初始權重q₀與權重增量Δq，令q₂＝q₀-Δq；q₁＝1-q₀+Δq，

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

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