基于改进A^(*)算法的AGV路径规划

Application of Improved A^(*)Algorithm for AGV Path Planning

提出了一种改进的A^(*)算法。首先在节点扩展环节,引入象限概念,限制当前节点只朝向目标节点所处的象限移动,有效降低了寻路过程中搜索的节点数量。其次在估价函数中考虑了AGV转向时间消耗成本、有效的搜索最短时间路径。采用索引矩阵和无序数组的混合数据结构实现对Open表和数据的管理,显著提高了算法的效率。通过仿真实验分析比较了文中算法和传统A^(*)算法的性能。仿真结果表明,文中算法能有效减少寻路过程中的搜索节点数和转向次数,提高了路径搜索效率和平滑度。

In order to solve the problems of A*algorithm in complex environment,such as large number of search nodes,long search time,large numbers of inflection points,search path twist and turns etc,an improved A^(*)algorithm is presented.Firstly,in the node expansion,the concept of quadrant is introduced to limit the movement of the current node to the quadrant where the target node is located,which effectively reduces the number of nodes searched during the pathfinding process.Secondly,the turning time costs are added into the evaluation function,so that the shortest-time path can be searched effectively.Mixed data structure of index matrix and non-priority array was applied to manage the Open list and data which significantly improved the efficiency of the algorithm.The analysis and comparison between the proposed algorithm,traditional A^(*)algorithm and another improved A*method were then given in the simulation experiments.The experiment results show that the proposed algorithm effectively re-duces the number of search nodes and turning times in the path planning,improves the path search efficiency and smoothness.