基于A*改进算法的四向移动机器人路径搜索研究

在由栅格法构建的环境地图中,利用A*算法进行路径搜索时存在搜索范围广、搜索速度慢、路径曲折等问题.针对栅格地图及具有四向移动机器人的特点,从搜索方向、启发函数构建、机器人加减速以及转向成本等几个方面对A*算法进行研究和改进,提出一种基于启发信息的扩展节点算法,降低偏离最佳路径节点的扩展数量.改进后的A*算法平均可降低67.1%的搜索面积、49.2%的计算时长、24.9%的路径成本及减少51.1%的转向次数,提高了路径的搜索速度和平滑度.

Research of four-way mobile robot path search based on improved A* algorithm

There are some problems in the use of the A* algorithm for path-search of the mobile robot based on a grid map, such as wide search range, calculation slow, search path twists and turns etc. For the characteristics of the four-way mobile robot which moves on the grid map, from the search range, heuristic function constructed, robot acceleration-deceleration and steering costs and other factors on the A* algorithm research and improvement, an extended node algorithm is propose. based on heuristic information, and the number of extensions nodes that deviate from the optimum path is reduced. The results show that the improved A* algorithm can reduce 67.1% of the search area, 49.2% of the computing time in average and reduce 24.9% of the average path cost, as well as decrease 51.1% steering times, and the speed and smoothness of the path-search are improved.