Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (15): 73-81.DOI: 10.3778/j.issn.1002-8331.2103-0525

Previous Articles     Next Articles

Robot Dynamic Path Planning Based on Improved A* and DWA Algorithm

LIU Jianjuan, XUE Liqi, ZHANG Huijuan, LIU Zhongpu   

  1. 1.College of Electrical Engineering, Henan University of Technology, Zhengzhou 450000, China
    2.Institute of Mechanical and Electrical Equipment and Measurement and Control Technology, Henan University of Technology, Zhengzhou 450000, China
  • Online:2021-08-01 Published:2021-07-26

融合改进A*与DWA算法的机器人动态路径规划

刘建娟,薛礼啟,张会娟,刘忠璞   

  1. 1.河南工业大学 电气工程学院,郑州 450000
    2.河南工业大学 机电设备及测控技术研究所,郑州 450000

Abstract:

Traditional A* algorithm is one of the commonly used algorithms for global path planning of mobile robot, but the algorithm has low search efficiency, many turning points in planning path, and can’t achieve dynamic path planning in the face of random dynamic obstacles in complex environment. To solve these problems, the improved A* algorithm and DWA algorithm are integrated on the basis of global optimization. The obstacle information in the environment is quantified, and the weight of heuristic function of A* algorithm is adjusted according to the information to improve the efficiency and flexibility of the algorithm. Based on the Floyd algorithm, the optimization algorithm of path nodes is designed, which can delete redundant nodes, reduce turning points and improve the path smoothness. The dynamic window evaluation function of DWA algorithm is designed based on the global optimal, which is used to distinguish known obstacles from unknown dynamic and static obstacles, and the key points of the improved A* algorithm planning path are extracted as the temporary target points of DWA algorithm. On the basis of the global optimal, the fusion of the improved A* algorithm and DWA algorithm is realized. The experimental results show that, in the complex environment, the fusion algorithm can not only ensure the global optimal path planning, but also effectively avoid the dynamic and static obstacles in the environment, and realize the dynamic path planning in the complex environment.

Key words: path planning, improved A* algorithm, DWA algorithm, fusion algorithm

摘要:

传统A*算法是移动机器人全局路径规划的常用算法之一,但是算法搜索效率低、规划路径转折点多、面对复杂环境中随机出现的动态障碍物无法实现动态路径规划。针对这些问题,在考虑全局最优的基础上将改进A*与DWA算法融合,量化环境中的障碍物信息,根据此信息调节A*算法启发函数的权重,提高算法的效率和灵活性。基于Floyd算法思想设计路径节点优化算法,删除冗余节点,减少转折,提高路径平滑度。基于全局最优设计DWA算法的动态窗口评价函数,用于区分已知障碍物和未知动态、静态障碍物,提取改进A*算法规划路径的关键点作为DWA算法的临时目标点,在全局最优的基础上实现了改进A*与DWA算法融合。实验结果表明,在复杂环境中,融合算法规划路径既能保证全局最优,又能及时有效地躲避环境中出现的动静态障碍物,实现复杂环境中的动态路径规划。

关键词: 路径规划, 改进A*算法, DWA算法, 融合算法