计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (21): 227-233.DOI: 10.3778/j.issn.1002-8331.1905-0213

• 工程与应用 • 上一篇    下一篇

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

吴鹏,桑成军,陆忠华,余双,方临阳,张屹   

  1. 1.常州大学 机械工程学院、城市轨道交通学院,江苏 常州 213164
    2.无锡职业技术学院 机械技术学院,江苏 无锡 214121
  • 出版日期:2019-11-01 发布日期:2019-10-30

Research on Mobile Robot Path Planning Based on Improved A* Algorithm

WU Peng, SANG Chengjun, LU Zhonghua, YU Shuang, FANG Linyang, ZHANG Yi   

  1. 1.School of Mechanical Engineering & School of Urban Rail Transit, Changzhou University, Changzhou, Jiangsu 213164, China
    2.Mechanical Institute of Technology, Wuxi Institute of Technology, Wuxi, Jiangsu 214121, China
  • Online:2019-11-01 Published:2019-10-30

摘要: A*算法广泛应用于移动机器人路径规划中,而传统A*算法在寻路时,普遍存在搜索时间较长、效率低下等问题,因此,采用双向搜索的方式,对传统A*算法加以改进,该算法在路径规划过程中,可同时进行正反向路径搜索,同时采用正反向搜索交替机制,保证了最终目标节点搜索在连线中点区域内相遇,从而缩短了寻路计算时间。在MATLAB平台上,针对改进后的A*算法进行仿真实验,结果证明,双向A*算法减少了规划时间,且可生成最优路径。最后,将该算法应用到基于开源机器人操作系统的Turtlebot2移动平台上,进行现场实验,实验结果表明,双向A*算法减少了寻路计算时间,从而使得路径搜索效率得到显著提升,且规划路径合理,满足路径规划要求。

关键词: 移动机器人, 路径规划, A*算法, 双向搜索, 机器人操作系统

Abstract: A* algorithm is widely used in path planning of mobile robots. However, there are many problems of the traditional A* algorithm such as long search time and low efficiency. Therefore, two-way search algorithm is presented to improve the traditional A* algorithm. The algorithm can search both positive and negative paths during the process of path planning simultaneously. The alternating mechanism of forward and backward searches can be used, and it has a good performance. The final target node is searched and meets in the midpoint area of the connection, and the calculation time of path finding can be reduced. Simulation experiments of the improved A* algorithm can be carried out on the MATLAB platform, and the result shows that the two-way A* algorithm can reduce planning time and generate the optimal path. This algorithm can be applied on Turtlebot 2 mobile platform based on open source robotic operating system. Field experiments show that the bidirectional A* algorithm can reduce the calculation time of path finding. Thus the efficiency of path searching can be improved, and the planning path is reasonable for the requirements of path planning significantly.

Key words: mobile robot, path planning, A* algorithm, bidirectional search, robot operating system