Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (22): 295-303.DOI: 10.3778/j.issn.1002-8331.2103-0434

• Engineering and Applications • Previous Articles     Next Articles

Dynamic Path Planning Based on Bilevel Optimization A* Algorithm and Dynamic Window Method

ZHAO Wei, WU Ziying   

  1. School of Mechanical and Precision Instrument Engineering, Xi’an University of Technology, Xi’an 710048, China
  • Online:2021-11-15 Published:2021-11-16

双层优化A*算法与动态窗口法的动态路径规划

赵伟,吴子英   

  1. 西安理工大学 机械与精密仪器工程学院,西安 710048

Abstract:

To meet the needs of mobile robot’s dynamic obstacle avoidance and global optimal path planning in dynamic environment, a path planning algorithm for mobile robot based on the combination of bilevel optimization A* algorithm and dynamic window method is proposed. Based on the global path trajectory obtained by the traditional A* algorithm, firstly, through the first level of global optimization, the slope between the path nodes is calculated, and the key turning points are extracted to greatly reduce the number of path turning points; secondly, through the second level of global optimization, the path intersection is obtained by extending the path segment, and the path turning points are minimized by judging whether the intersection passes through obstacles; finally, the dynamic window method is designed, the problem that the robot is easy to fall into the “concave” and “C” shaped obstacles is solved, the safe distance is ensured, and the global optimal path is selected. The global simulation experiments of traditional A* algorithm, one-level optimization A*, two-level optimization A*, and fusion algorithm are carried out in static and dynamic two-dimensional raster maps. The experimental results show that the first level optimization A* algorithm greatly reduces the number of turning points; the second level optimization A* algorithm reduces the number of turning points to the minimum, but increases the path length by a small margin; the fusion algorithm realizes the robot’s real-time dynamic obstacle avoidance to reach the destination, and is closer to the global optimal planning while ensuring the safe distance.

Key words: path planning, dynamic window method, A* algorithm, fusion algorithm

摘要:

为满足动态环境中移动机器人既要动态避障抵到终点,又要尽可能地做到全局最优的路径规划需求,提出了一种双层优化A*算法与动态窗口法相结合的移动机器人路径规划算法。在传统A*算法求得的全局路径轨迹基础上,首先通过一层全局优化,计算路径节点间斜率,提取关键转折点,大幅度减少路径转折点数量;再通过二层全局优化,延长路径段求得路径交点,判断交点是否通过障碍物的方法,将路径转折点数降到最低;设计动态窗口法的轨迹评价函数,解决了机器人容易陷入“凹”“C”形障碍物的问题,同时保证了障碍物安全距离并选取全局最优的路径轨迹。最后分别在静态与动态的二维栅格地图中对传统A*算法、一层优化A*、二层优化A*以及融合算法进行仿真实验。实验结果表明一层优化A*算法大幅度降低了转折次数;二层优化A*算法将转折点数降到最低,但是路径长度小幅度增加;融合算法实现了机器人实时动态避障抵到终点,而且在保证安全距离的同时更加贴近全局最优规划。

关键词: 路径规划, 动态窗口法, A*算法, 融合算法