• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (07): 1273-1281.

• 人工智能与数据挖掘 • 上一篇    下一篇

基于改进A*算法和动态窗口法的机器人路径规划

郭园园,袁杰,赵克刚   

  1. (新疆大学电气工程学院,新疆 乌鲁木齐 830047)
  • 收稿日期:2020-12-07 修回日期:2021-02-02 接受日期:2022-07-25 出版日期:2022-07-25 发布日期:2022-07-25
  • 基金资助:
    国家自然科学基金(61863033); 新疆维吾尔自治区天山青年计划-优秀青年人才培养项目(2019Q018)

Robot path planning based on an improved A* algorithm and an improved dynamic window method

GUO Yuan-yuan,YUAN Jie,ZHAO Ke-gang   

  1. (School of Electrical Engineering,Xinjiang University,Urumqi 830047,China)
  • Received:2020-12-07 Revised:2021-02-02 Accepted:2022-07-25 Online:2022-07-25 Published:2022-07-25

摘要: 针对移动机器人在复杂环境下(包含静态和动态环境)的路径规划效率低的问题,提出了一种改进的A*算法与动态窗口法相结合的混合算法。针对传统A*算法安全性不足的问题,采用障碍规避策略,优化节点的选择方式,增加路径的安全性;针对转折点多的问题,采用递归二分法优化策略,去除冗余节点,减少转弯次数;针对静态环境下路径平滑性不足的问题,采用动态内切圆平滑策略将折线角优化成弧度角,以增加路径的平滑性。对于传统动态窗口法的目标点附近存在障碍物时规划效果不好和容易在凹型槽类障碍物中陷入局部最优的问题,在原有的评价函数中引入了距离偏差和轨迹偏差。最后,对所提的改进A*算法和混合算法分别在静态和动态环境下与其他算法进行仿真比较。从结果可以看出,与传统混合算法相比,临时障碍环境下,路径长度和运行时间分别缩短了13.2%和65.8%;移动障碍环境下,路径长度和运行时间分别缩短了13.9%和44.9%,所提的算法提高了在复杂环境中规划路径的效率。

关键词: 移动机器人, 路径规划, 改进A*算法, 动态窗口法

Abstract: Aiming at the efficiency of path planning of mobile robots in complex environments (includ- ing static and dynamic environments), a hybrid algorithm combining an improved A* algorithm and an improved dynamic window method is proposed. Aiming at the problem of insufficient security of the traditional A* algorithm, the obstacle avoidance strategy is adopted to optimize the selection of  nodes to increase the safety of the path. Aiming at the problem of many turning points, the recursive dichotomy optimization strategy is adopted to remove redundant nodes and reduce the number of turns. Aiming at the problem of insufficient path smoothness in a static environment, the dynamic inscribed circle smoothing strategy is used to optimize the polyline angle to a radian angle to increase the smoothness of the path. In the traditional dynamic window method, when there are obstacles near the target point, the planning effect is not good and it is easy to fall into the local optimum in the concave groove obstacle. The distance deviation and trajectory deviation are introduced into the original evaluation function. Finally, the proposed improved A* algorithm and hybrid algorithm are simulated and compared with other algorithms in static and dynamic environments respectively. The results show that, compared with the traditional hybrid algorithm, the proposal reduces the path length and running time in the temporary obstacle environment by 13.2% and 65.8%, respectively, and reduces the path length and running time in the mobile obstacle environment by 13.9% and 44.9%, respectively. The proposed algorithm improves the efficiency of path planning in complex environments. 

Key words: mobile robot, path planning, improved A* algorithm, dynamic window method

中图分类号: