Abstract:

The A* algorithm is often used for path planning of two-dimensional maps, but when using it for path planning of indoor mobile robots, there are too many redundant points and inflection points, resulting in excessive memory consumption and unsmooth paths. Aiming at the above problems, an improved A* algorithm is proposed. First of all, combined with the jumping point search theory, using prior information, the selected key points are used to replace the Openlist and Closelist points in the traditional A* algorithm, which reduces the amount of calculation and improves the speed of calculation. Secondly, the reverse search strategy is used to re-plan the path, delete unnecessary turning points, and reduce the path length. Finally, the path is smoothed by a dynamic circle at the turning point to improve the smoothness of the path. In order to verify the performance of the improved A* algorithm, it is applied to simulation grid environment maps of different sizes and robots in real indoor environments. The experimental results show that in the same environment, the improved algorithm is compared with the traditional A* algorithm. The running time, path length and smoothness are all significantly improved.

Key words: A* algorithm, key point, smooth path, high efficiency

摘要：

A*算法常用于二维地图的路径规划，但是在利用其进行室内移动机器人路径规划时，存在过多的冗余点和拐点，造成了内存消耗过大和路径不平滑。针对上述问题，提出了一种改进的A*算法。结合跳跃点搜索理论，利用先验信息，用选取的关键点代替了传统A*算法中Openlist和Closelist的点，减小了计算量，提高了运算速度。运用反向搜索策略，对路径进行二次规划，删除不必要的转折点，降低了路径长度。将路径在转折点处进行动态圆平滑处理，提高了路径的平滑性。为了验证改进A*算法的性能，将其应用于不同尺寸仿真栅格环境地图和处于真实室内环境的机器人中，实验结果表明，在相同环境下，改进算法相较于传统的A*算法，在运行时间、路径长度和平滑程度上均有明显的提高。

关键词: A*算法, 关键点, 路径平滑, 高效率