Computer Engineering and Applications ›› 2024, Vol. 60 ›› Issue (15): 327-335.DOI: 10.3778/j.issn.1002-8331.2310-0140

• Engineering and Applications • Previous Articles     Next Articles

Research on Indoor Service Robot Path Planning Based on Improved A* and DWA

JIANG Peihe, WANG Jing, SANG Zhongqi, LIN Lifeng   

  1. 1.School of Physics and Electronic Information, Yantai University, Yantai, Shandong 264005, China
    2.School of Electronics Engineering, Peking University, Beijing 100871, China
  • Online:2024-08-01 Published:2024-07-30

改进A*与DWA的室内服务机器人路径规划研究

姜佩贺,王敬,桑忠启,林立峰   

  1. 1.烟台大学 物理与电子信息学院,山东 烟台 264005
    2.北京大学 电子学院,北京 100871

Abstract: Considering that global planning cannot avoid dynamic obstacles and local planning may fall into local optima, a path planning algorithm based on the fusion of improved A* and DWA (dynamic window approach) using service robots is proposed. To address the drawback of slow search speed in traditional A* algorithm, the evaluation function has been optimized. Based on the motion model of the differential robot, the search neighborhood is optimized. To address the shortcomings of traditional A* algorithm with multiple broken line segments in the path, a new obstacle avoidance strategy is introduced to optimize the path with broken lines and smooth the curve. To address the shortcomings of global and local planning, the improved A* algorithm and DWA algorithm are integrated, and dynamic planning algorithms are segmented based on key nodes of the global path to ensure real-time obstacle avoidance for robots. Simulation experiments have shown that the improved A* algorithm performs better, with key nodes reduced by 75%, turning times reduced by 80%, path length reduced by 5.9%, and search time reduced by 46%. Compared to a single static algorithm, the fusion algorithm can smoothly reach the endpoint through random obstacles.

Key words: service robots, path planning, A* algorithm, dynamic window approach (DWA) algorithm, algorithm fusion

摘要: 鉴于全局规划无法规避动态障碍以及局部规划可能陷入局部最优的缺陷,提出一种基于服务机器人的改进A*与DWA(dynamic window approach)融合的路径规划算法。针对传统A*算法搜索速度较慢的缺陷,优化了评估函数;根据差速机器人运动模型,对搜索邻域进行了优化;针对传统A*算法路径折线线段多等缺陷,引入新的避障策略,对路径进行折线优化以及曲线平滑;针对全局与局部规划的缺陷,融合改进A*算法与DWA算法,根据全局路径关键节点分段应用动态规划算法,确保机器人能够实时避障。仿真实验证明,改进A*算法的性能更好,其中关键节点减少了75%,转折次数减少了80%,路径长度减少了5.9%,搜索时间减少了46%。融合算法相较于单一的静态算法,能够通过随机障碍物,顺利到达终点。

关键词: 服务机器人, 路径规划, A*算法, DWA算法, 算法融合