基于动态加权A^(*)算法的AGV路径规划研究

Study on AGV path planning based on dynamic weighted A^(*) algorithm

在柔性车间中,针对A^(*)算法应用于自动导引车(automatic guided vehicle,AGV)进行路径规划时存在折点多、遍历节点多等问题,提出一种选择加权的A^(*)算法.首先,应用栅格法构建车间地图模型,在基于曼哈顿距离的传统A^(*)算法基础上,根据起始点和目标点确定两个权值,研究在曼哈顿距离中各分量权值的相对大小对AGV行走方向和折点数的影响.其次,对算法中估计代价函数f(n)中的实际代价函数g(n)进行重新构建来减少算法遍历节点数,以AGV预计行走时间最短为评价指标确定最优路径.通过实验仿真验证改进A^(*)算法的有效性和环境适应性,在尺寸越大、路径布局越复杂的地图中,改进A^(*)算法的优势越明显.

In the flexible workshop,a choosing weighted A^(*)algorithm is proposed in view of the problems of many vertices and many traversal nodes when the A^(*)algorithm is used in the path planning of automatic guided vehicle(AGV).Firstly,the grid method is applied to construct a workshop map model.On the basis of the traditional A^(*)algorithm based on Manhattan distance,two weights are determined according to the starting point and the target point.The influence of the relative weights of each component in the Manhattan distance on the walking direction and the number of vertices in AGV is studied.Secondly,the actual cost function g(n)in the estimated cost function f(n)in the algorithm is reconstructed to reduce the number of traversal nodes in the algorithm,and the shortest expected walking time of the AGV is used as the evaluation index to determine the optimal path.The effectiveness and environmental adaptability of the improved A^(*)algorithm are verified by the experimental simulations.In the map with larger size and more complex path layout,the advantages of the improved A^(*)algorithm are more obvious.