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

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