Abstract:

Aiming at the problems of high memory occupancy and low computing efficiency of A* algorithm in large-scale environment, an improved A* algorithm is proposed. Firstly, a bidirectional search mechanism is introduced. It searches with the original starting point, the end point and the oppositecurrent point as the target point, so that the AGV path optimization has directionality. Secondly, the evaluation function is optimized. It selects the appropriate weight coefficient for the evaluation function, so as to improve the calculation efficiency of path optimization. In order to verify the effectiveness of the improved A* algorithm, it is programmed in Matlab platform and simulated in different sizes of grid map with obstacles. The simulation results show that the number of nodes traversed by the improved A* algorithm is less, the calculation efficiency is higher and the shortest path can be obtained.

Key words: bidirectional search, improved A* algorithm, path optimization

摘要：

针对大规模环境下传统A*算法路径寻优存在的内存占有率高、计算效率低下的问题，提出了一种改进A*算法。引入了双向搜索机制，以原始起点、终点和对向搜索所处的当前节点作为目标点进行搜索操作，使AGV的路径寻优具备更加合理的方向性；优化评价函数，改进了评价函数的传统计算方式，通过测试为评价函数选择了合适的权重系数，减少路径寻优过程中的冗余点，提升路径寻优的计算效率，节约内存占有率。为了验证改进A*算法的有效性，在Matlab平台中进行编程，在不同尺寸的含障碍栅格地图中进行了仿真。仿真结果表明：改进A*算法在路径寻优过程中所遍历的节点数量较少，搜索过程中的计算效率更高，并且可获得到达目标点的最短路径。

关键词: 双向搜索, 改进A*算法, 路径寻优