[發明專利]一種基于大數據平臺分布式瓦片金字塔的三維路徑規劃方法

在審

• 申請號: 202211033770.7
• 申請日: 2022-08-26
• 公開（公告）號: CN115437375A
• 公開（公告）日: 2022-12-06
• 發明（設計）人: 洪中華;涂斌;周汝雁;潘海燕;馬振玲;張云;韓彥嶺;王靜;楊樹瑚;徐利軍
• 申請（專利權）人: 上海海洋大學
• 主分類號: G05D1/02
• 分類號: G05D1/02;G06F16/182;G06T17/05
• 代理公司: 上海唯智贏專利代理事務所(普通合伙) 31293
• 代理人: 姜曉艷

本發明公開了一種基于大數據平臺分布式瓦片金字塔的三維路徑規劃方法，將待探索區域的大型三維地形數據DEM進行分布式瓦片金字塔處理，并將生成的分布式瓦片金字塔存儲到Hadoop分布式文件系統HDFS內；使用Spark的分布式計算集群從HDFS里由上至下讀取分布式瓦片金字塔的DEM數據，并采用由粗粒度到細粒度迭代的路徑規劃方法進行待探索區域的三維路徑規劃。本方法通過建立DEM的分布式瓦片金字塔的存儲模型以及Spark分布式處理瓦片金字塔的流程框架，提升分布式瓦片金字塔的路徑搜索效率，提高大型DEM數據的遠距離路徑規劃任務的運行速度，同時采用粗粒度到細粒度的路徑規劃，而減少路徑規劃運行時間。

技術領域

本發明屬于分布式計算的技術領域，具體涉及一種基于大數據平臺分布式瓦片金字塔的三維路徑規劃方法。

背景技術

月球車對月球的探索是人類探索太空的第一步，對月球車的路徑規劃問題一直是探月工程的研究熱點。由于現代測繪技術和傳感器硬件的快速發展，使得生成的DEM精度越來越高，數據量也越來越大，因此傳統策略對基于大型三維地形數據(DEM)進行尋路計算的時間越來越長。

路徑規劃的核心思想是在一個未知的環境里，從當前的起始位置找到一條最優的路徑到達目標位置。對大型數據進行路徑規劃的問題上，許多學者提出了不同的解決方案。這些方案可總結為：(1)通過改進原有路徑規劃算法提高路徑規劃算法的效率；(2)在將DEM數據轉換為離散點數據，并使用MapReduce或Spark運行迪杰斯特拉或A星路徑規劃算法去解決最短路徑問題。

然而通過改進原有路徑規劃算法提高路徑規劃算法的效率在大型數據上很難得到提升，受限于單臺服務器的物理硬件影響，在大型DEM數據的計算上，往往會產生內存溢出、磁盤存儲空間不足、搜索時間隨搜索數據量增大而指數性增長的問題；而通過利用MapReduce或Spark等分布式計算框架運行迪杰斯特拉或A星路徑規劃算法雖然解決了單臺服務器的物理硬件的影響，但在對DEM柵格數據進行路徑規劃任務上，將大型DEM數據簡單的轉換為離散點數據是非常耗時的操作，并且會導致分布式內存中保存著大量無用的離散點數據，從而增大計算的體量、增加計算所花費的時間。并且，將DEM數據轉換為離散數據僅僅是提高了算法的分布式計算能力，但并未考慮DEM的數據結構特性，忽略了柵格數據的鄰域特點。

發明內容

針對目前DEM柵格數據進行路徑規劃耗時耗力等技術問題，我們提出了一個基于大數據平臺分布式瓦片金字塔的三維路徑規劃方法，對于大型DEM數據的路徑規劃任務，本方法通過集群搭建的HDFS存儲框架和Spark計算框架分別解決了上述單機策略中磁盤存儲空間不足的問題和內存溢出問題，并將瓦片金字塔應用到分布式的路徑規劃任務中用以解決單機策略中搜索時間隨搜索數據量增大而指數性增長的問題和分布式策略中因大量無用離散數據導致計算時間增加的問題。

本發明提出的基于大數據平臺分布式瓦片金字塔的三維路徑規劃方法將大型三維地形數據DEM轉換為分布式瓦片金字塔存儲，通過分而治之及粗細粒度轉換的思路，利用Spark分布式計算價格和Hadoop的分布式存儲能力，來減少在大型的DEM數據上進行路徑規劃任務所花費的時間，提高了計算速度。

本發明可通過以下技術方案實現：

一種基于大數據平臺分布式瓦片金字塔的三維路徑規劃方法，將待探索區域的大型三維地形數據DEM進行分布式瓦片金字塔處理，并將生成的分布式瓦片金字塔存儲到Hadoop分布式文件系統HDFS內；使用Spark的分布式計算集群從HDFS里由上至下讀取分布式瓦片金字塔的DEM數據，并采用由粗粒度到細粒度迭代的路徑規劃方法進行待探索區域的三維路徑規劃。