Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (18): 311-317.DOI: 10.3778/j.issn.1002-8331.2101-0346

• Engineering and Applications • Previous Articles     Next Articles

Research on Path Planning with Improved A* Algorithm Fusing Environmental Information and Motion Constraints

BAI Xiong, LU Jilin, LU Kuan, CHEN Pengyun, CUI Junjie, LIU Zehua   

  1. 1.School of Mechatronics Engineering, North University of China, Taiyuan 030051, China
    2.Unit 32381 of Chinese People’s Liberation Army, Beijing 100072, China
  • Online:2022-09-15 Published:2022-09-15

融合环境信息和运动约束的改进A*算法研究

白雄,鲁吉林,路宽,陈鹏云,崔俊杰,刘泽华   

  1. 1.中北大学 机电工程学院,太原 030051
    2.中国人民解放军 第32381部队,北京 100072

Abstract: The standard A* algorithm cannot consider the motion characteristics of the mobile robot and the processed path is not conducive to the motion of the mobile robot. In this study, a new improved A* algorithm is proposed to solve this problem. The heuristic function of the algorithm is improved by introducing the weight coefficient of obstacles and the global path planning is carried out. The selection of search nodes is optimized and the safe distance between obstacles and paths is set. The path of the mobile robot is optimized based on the consideration of its motion characteristics, and the simulation experiment is compared with other algorithms in different environment maps. Relevant experiments show that the planned path based on the new improved A* algorithm always keeps a certain safe distance from the obstacle. Compared with the standard A* algorithm, the time of the improved A* algorithm is reduced by 80% on average, while the path length is reduced by 2% on average, and the path corner is reduced by 82% on average. Compared with other algorithms, the improved algorithm has a great improvement in time, search nodes and smoothness. The path planning algorithm integrating robot motion characteristics can provide a new method for path planning of mobile robots.

Key words: improved A* algorithm, Floyd algorithm, mobile robot, motion constraints, path planning

摘要: 标准A*算法存在着无法考虑移动机器人运动特性及处理后的路径不利于移动机器人运动等问题。针对这一问题提出了一种新改进A*算法,通过环境信息引入障碍物权重系数来改进算法的启发函数并进行全局路径规划;优化搜索节点的选取方式和设定障碍物与路径之间的安全距离;基于对移动机器人的运动特性的考虑优化其路径,并在不同环境地图中与其他算法进行仿真实验对比分析。相关实验表明:基于新改进A*算法规划的路径始终与障碍物保持一定的安全距离;改进A*算法在时间上相比标准A*算法平均减少了80%,路径长度平均减少了2%,路径转角平均降低了82%。改进后算法相比其他算法在时间、搜索节点以及平滑度上有很大的改进,融合机器人环境信息和运动特性的规划路径算法可为移动机器人的路径规划提供一种新的方法。

关键词: 改进A*算法, Floyd算法, 移动机器人, 运动特性, 路径规划