A Fast Large-Scale Path Planning Method on Lunar DEM Using Distributed Tile Pyramid Strategy

Abstract

In lunar exploration missions, path planning for lunar rovers using digital elevation models (DEMs) is currently a hot topic in academic research. However, research on path planning using large-scale DEMs has rarely been discussed, owing to the low time efficiency of existing algorithms. Therefore, in this article, we propose a fast path-planning method using a distributed tile pyramid strategy and an improved A* algorithm. The proposed method consists of three main steps. First, the tile pyramid is generated for the large lunar DEM and stored in Hadoop distributed file system. Second, a distributed path-planning strategy based on tile pyramid (DPPS-TP) is used to accelerate path-planning tasks on large-scale lunar DEMs using Spark and Hadoop. Finally, an improved A* algorithm was proposed to improve the speed of the path-planning task in each tile. The method was tested using lunar DEM images. Experimental results demonstrate that: in a single-machine serial strategy using source DEM generated by the Chang'e-2 CCD stereo camera, the proposed A* algorithm for open list and closed list with random access feature (OC-RA-A* algorithm) is 3.59 times faster than the traditional A* algorithm in long-distance path planning tasks and compared to the distributed parallel computation strategy using source DEM generated by the Chang'e-2 CCD stereo camera, the proposed DPPS-TP based on tile pyramid DEM is 113.66 times faster in the long-range path planning task.

Keywords

• A star
• distributed computing
• hadoop distributed file system (HDFS)
• path planning
• spark
• tile-pyramid