基于节点优化的改进全局路径规划A*算法

Improved global path planning A* algorithm based on node optimization

摘要:

目前越来越多的领域使用移动机器人代替人工工作。路径规划就是移动机器人正常工作的保障之一，A*算法就是一种路径规划算法。针对A*算法生成路径拐点多、路径较长的问题，提出了一种基于将搜索邻域扩大至5×5的随机数去除节点的改进A*算法。首先，将3×3的搜索邻域扩大至5×5，从而减少拐点个数，改善转折角度，去除冗余点；其次，引入一种随机数去除冗余节点的方法，该方法是通过随机连接节点判定其是否穿过障碍物来去除冗余节点，从而进一步去除A*算法路径列表的冗余点；最后，将改进的算法与A*算法在30×30的栅格地图中进行仿真比较，实验结果表明，改进的算法在多组路径中都有很好的优化效果，路径长度、运行时长和访问节点数分别平均减少了4.46%、24.83%和39.93%，从而有效改善A*算法生成拐点多、路径较长的问题。

Abstract:

Aiming at the problem that the A* algorithm generates many inflection points and long paths, an improved A* algorithm is proposed based on expanding the search neighborhood to 5x5 random numbers and removing nodes. First, the 3x3 search neighborhood is expanded to 5x5, thereby reducing the number of inflection points, improving the turning angle, and removing redundant points. Secondly, a method for removing redundant nodes with random numbers is introduced. This method removes redundant nodes by randomly connecting nodes to determine whether they pass through obstacles, thereby further removing redundant points in the path list of the A* algorithm. Finally, the improved algorithm is compared with the A* algorithm in a 30x30 grid map. The experimental results show that the improved algorithm has a good optimization effect in multiple groups of paths, and the path length, running time and access The number of nodes is reduced by 4.46%, 24.83% and 39.93% respectively on average, thus effectively improving the problem that the A* algorithm generates many inflection points and long paths.