基于改进A*算法的自主式机器人路径规划

Autonomous Mobile Robot Path Planning Based on Improved A* Algorithm

摘要: 针对传统的A*算法存在遍历子节点数量多、搜索自由度底、搜索方向夹角大所导致的路径搜索效率不高的问题进行了研究，提出一种改进的A*算法。首先增加节点数量，删除重复方向，建立16邻域搜索方式，扩大搜索角度。然后在新邻域搜索方式上，利用当前节点与目标点的方向信息局部调整搜索区间。改进启发函数和评价函数权重系数，在节点不陷入局部最优解的情况下，合理地缩小了搜索邻域。最后，在不同障碍物比例、不同栅格地图规模等16种模拟场景下进行实验。实验结果显示：改进A*算法相对于传统算法的搜索效率显著提高，极大地减少了搜索子节点的数量，提升了算法搜索的能力。

Abstract: Aiming at the traditional A* algorithm which has the problems of traversing a large number of child nodes, the bottom of the search degree of freedom, and the path search efficiency caused by the large angle of the search direction, the research is carried out, and an improved A* algorithm is proposed. Firstly, in increasing the number of nodes and deleting the repetitive directions, a 16-neighborhood search method is formed, which enlarges the search angle. Then, the search interval is locally adjusted by using the direction information between the current node and the target point on the new neighborhood search method. The weight coefficients of the heuristic function and the evaluation function are improved to reasonably narrow the search neighborhood without the node falling into the local optimal solution. Finally, experiments are conducted in 16 simulated scenarios with different obstacle scales and different raster map sizes. The experimental results show that the improved A* algorithm significantly improves the search efficiency compared with the traditional algorithm, greatly reduces the number of searching sub-nodes, and improves the searching ability of the algorithm.