Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (23): 270-278.DOI: 10.3778/j.issn.1002-8331.1907-0152

Previous Articles    

Multi-frame Time Window Rotation Algorithm to Plan Storage Multiple AGV Car Path

CHEN Guangfeng, YU Lichao   

  1. School of Mechanical Engineering, Donghua University, Shanghai 201620, China
  • Online:2020-12-01 Published:2020-11-30

多帧时间窗轮换算法规划仓储多AGV小车路径

陈广锋,余立潮   

  1. 东华大学 机械工程学院,上海 201620

Abstract:

Aiming at the path planning problem of multi-AGV cars in storage environment, a multi-frame time window rotation algorithm is proposed. The proposed algorithm uses the A* pathfinding algorithm to perform global path planning, and obtains the set of discrete points of the initial path of the multi-AGV car. By setting the multi-frame time window switching threshold in the warehouse environment intersection, the global path point set of the car is discretized into a multi-frame small form, and the convex target feature optimal target obstacle function is established in each small form.  Introducing and the kinematics of the car and anti-collision optimal hyperplane constraints, the various constraints of the car are parameterized into a polynomial B-spline curve form, and the step size is updated by the Newton iterative fusion retrospective straight line method to solve the polynomial B-spline curve control point of the next frame time window. Finally, experimental tests show that the path planning of the multi-AGV car is realized with all constraints.

Key words: multi-Automated Guided Vehicle(AGV), path planning, optimal hyperplane constraint, multi-frame time window rotation, B-spline curve

摘要:

针对在仓储环境中多AGV小车的路径规划问题,提出一种基于多帧时间窗轮换算法。所提算法运用A*寻路算法进行全局路径规划,得到多AGV小车的初始路径离散点的集合。通过在仓储环境岔路口设置多帧时间窗切换阈值,将小车的全局路径点集离散成多帧小窗体,在每个小窗体建立凸集特征最优目标障碍函数,引入小车的运动学约束和防碰撞最优超平面约束,将小车的各种约束参数化为多项式B样条曲线形式,采用牛顿迭代融合回溯直线法更新步长,解决下一帧时间窗多项式B样条曲线控制点的更新问题。最后通过实验测试表明,在满足所有约束的情况下实现多AGV小车的路径规划。

关键词: 多自动引导车辆(AGV), 路径规划, 最优超平面约束, 多帧时间窗轮换, B样条曲线