基于改进A*算法的移动机器人路径规划

Mobile Robot Path Planning Based on an Improved A* Algorithm

为了解决较大场景下A*寻路算法存在的内存开销大、计算时间长等问题,本文在A*算法的基础上,结合跳点搜索算法,提出一种改进的A*算法.该算法通过筛选跳点进行扩展,直到生成最终路径,扩展过程中使用跳点代替A*算法中大量可能被添加到OpenList和ClosedList的不必要节点,从而减少计算量.为了验证改进A*算法的有效性,分别在不同尺寸的2维栅格地图中进行仿真,仿真结果表明,相比A*算法,改进A*算法在寻路过程中扩展更少的节点,寻路速度更快,且加速效果随环境地图的增大更加明显.最后将改进A*算法应用于移动机器人Turtlebot2进行对比实验.实验结果表明,在生成相同路径的基础上,改进A*算法的寻路速度较A*算法提高了约200%,能够满足移动机器人路径规划的要求.

Aiming at the problems of A* algorithm in the large scene, such as large memory overhead and long computation time, an improved A* algorithm is proposed based on A* algorithm and jump point search algorithm. The algorithm expands by selecting jump points until the final path is generated. During the expansion process, a lot of unnecessary nodes in A*algorithm which are added to OpenList and ClosedList can be replaced by jump points to reduce computation. In order to prove the validity of the improved A* algorithm, the simulation is carried out in 2 D grid map of different sizes. The simulation result shows that the improved A* algorithm expands fewer nodes in the pathfinding process, and the pathfinding speed is faster. The acceleration effect becomes more apparent with the increase of environment map. Finally, the improved A* algorithm is implemented on the mobile robot Turtlebot2 to conduct comparative experiments. The experimental result shows that the improved A* algorithm can speed up by about 200% compared with the A* algorithm when generating the same path, and it can meet the requirements of path planning for mobile robots.