计算机工程与应用 ›› 2020, Vol. 56 ›› Issue (12): 125-133.DOI: 10.3778/j.issn.1002-8331.1903-0149

• 模式识别与人工智能 • 上一篇    下一篇

启发式RRT算法的AGV路径规划

杨瑶,付克昌,蒋涛,张国良,刘甲甲,孟易   

  1. 成都信息工程大学 控制工程学院,成都 610225
  • 出版日期:2020-06-15 发布日期:2020-06-09

AGV Path Planned with Heuristic RRT

YANG Yao, FU Kechang, JIANG Tao, ZHANG Guoliang, LIU Jiajia, MENG Yi   

  1. School of Control Engineering, Chengdu University of Information Technology, Chengdu 610225, China
  • Online:2020-06-15 Published:2020-06-09

摘要:

在实际应用中,B-RRT*算法规划的路径存在着转折次数多、路线不平滑、路线贴合障碍物和最大转角过大等不符合车辆运动学的问题。为了获得适用于自动导引小车(Automatic Guided Vehicle,AGV)的优化路径,通过使用Reeds-Shepp曲线进行预处理以解决车辆在目标点朝向的问题。此外,提出启发式滑动窗口采样减少B-RRT*算法随机采样所带来的误差,并将车辆运动学约束加入到重选父节点和重布随机树的过程,使用贝塞尔曲线对所规划的路径进行平滑处理。实验结果表明:在规划相同路径上,改进B-RRT*算法规划的路径能够有效地解决上述算法存在的最大转角不合理、路径靠近障碍物、路径不平滑和不符合车辆运动学等问题。

关键词: 自动导引小车, 车辆运动学模型, Reeds-Shepp曲线, 启发式滑动窗口采样, B-RRT*算法, 路径规划

Abstract:

There are many problems existed in the path planned by B-RRT* in the real using situation:(1)the planed path is not smooth with many turning points, (2)the planned path is too close to the obstacle, (3)the turning angle is too large. These problems make the path unsuitable for real vehicle kinematic application. To overcome these problems, Reeds-Shepp curve is used to pre-process the path to solve the problem of the vehicle’s orientation at the target point. Additionally, a heuristic sliding window is introduced to avoid random sampling by B-RRT* algorithm randomly. At the same time, the vehicle’s kinematic constraints are gotten by modeling for B-RRT* algorithm. The parent node has been re-selected and re-distributed randomly. The planned path is smoothed by using Bezier curvature. In conclusion, the results show that the path planned by the improved B-RRT* algorithm is more effective than the traditional one and the problems caused by B-RRT* have been solved to make it a more realistic vehicle kinematic model.

Key words: Automatic Guided Vehicle(AGV), vehicle kinematic model, Reeds-Shepp curve, heuristic sliding window sampling, B-RRT* algorithm, path planned