Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map
Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map
复制标题
利用地形数据地图进行长距离越野路径规划的改进A-Star算法
DOI：
10.3390/ijgi10110785
复制
发表时间：
2021-11-01
影响因子：
3.4
通讯作者：
Xu, Lijun
中科院分区：
文献类型：
--
作者：
Hong, Zhonghua;Sun, Pengfei;Xu, Lijun
针对长距离越野路径规划处理时间短的局限性，提出一种基于地形数据的改进A-Star算法。针对长距离越野路径规划任务，提出了一种改进的A-Star算法，该算法基于数字高程模型生成的地形数据地图，确定出发地和目的地之间的可行路径。本研究从数据结构、检索策略两个方面对算法进行了优化。首先，最小堆和二维数组的混合数据结构大大降低了算法的时间复杂度。其次，设计了一种优化的搜索策略，在搜索全局最优路径的初始阶段不检查是否到达目的地，从而提高了执行效率。为了评估所提出的算法的效率，三个不同的越野路径规划任务进行了检查短，中，长距离路径规划任务。每组任务对应三种不同的越野车，共进行了九组实验。实验结果表明，该算法的处理效率明显优于传统的A-Star算法。与传统的A-Star算法相比，改进的A-Star算法的路径规划效率至少提高了4.6倍，对于长距离越野路径规划，最大加速可达550倍。仿真结果表明，改进算法大大提高了长距离越野路径规划的效率。
To overcome the limitation of poor processing times for long-distance off-road path planning, an improved A-Star algorithm based on terrain data is proposed in this study. The improved A-Star algorithm for long-distance off-road path planning tasks was developed to identify a feasible path between the start and destination based on a terrain data map generated using a digital elevation model. This study optimised the algorithm in two aspects: data structure, retrieval strategy. First, a hybrid data structure of the minimum heap and 2D array greatly reduces the time complexity of the algorithm. Second, an optimised search strategy was designed that does not check whether the destination is reached in the initial stage of searching for the global optimal path, thus improving execution efficiency. To evaluate the efficiency of the proposed algorithm, three different off-road path planning tasks were examined for short-, medium-, and long-distance path planning tasks. Each group of tasks corresponded to three different off-road vehicles, and nine groups of experiments were conducted. The experimental results show that the processing efficiency of the proposed algorithm is significantly better than that of the conventional A-Star algorithm. Compared with the conventional A-Star algorithm, the path planning efficiency of the improved A-Star algorithm was accelerated by at least 4.6 times, and the maximum acceleration reached was 550 times for long-distance off-road path planning. The simulation results show that the efficiency of long-distance off-road path planning was greatly improved by using the improved algorithm.