移动机器人路径规划中A^(*)算法的改进研究

Improvement of A^(*)Algorithm in Path Planning of Mobile Robot

为解决传统A^(*)算法在路径搜索过程中存在冗余节点过多、搜索效率不高、路径转折角度过大的问题,提出一种改进的A^(*)算法来规划最优路径。将A^(*)算法的搜索邻域增加到24个,以获得更加精确和宽阔的搜索视野;引入角度搜索算法,剔除了路径搜索过程中的不必要节点,使搜索过程更具有目标导向性;通过当前点与目标点的相对位置对启发函数进行指数衰减的加权,用于处理搜索速度与路径长度之间的关系;平滑所得路径,减少了路径折弯数和折弯角度,使得机器人运动更加平稳。结果表明:改进的A^(*)算法相较于A^(*)算法,在复杂与简单环境中搜索速度分别提升29.16%~65.82%和41.87%~64.71%,路径折弯数分别减少27.27%~63.64%和59.09%~62.12%,相较于D*算法在寻路速度、遍历节点及路径折弯数量方面都有较大提升,将改进A^(*)算法在真实环境中进行实验,验证了其具有较好性能及路径规划能力。

To solve the problems of excessively redundant nodes,low search efficiency,and excessive path turning angle in the path search of the traditional A^(*)algorithm,an improved A^(*)algorithm is proposed to plan the optimal path.First,the amount of search neighborhood of the A^(*)algorithm is increased to 24 to obtain a more accurate and comprehensive search field.Second,the angle search algorithm is introduced,eliminating the unnecessary nodes in the path search and making the search more target-oriented.Third,the heuristic function is weighted by the exponential attenuation through the relative position of the current point and the target point,to deal with the relationship between the search speed and the path length.Finally,the obtained path is smoothed to reduce the number of path bends and the bending angle,making the robot move more smoothly.The results show that,compared with the search speed of the original A^(*)algorithm,that of the improved one is increased by 29.16%~65.82%in a complex environment and by 41.87%~64.71%in a simple environment,and the number of path bends is reduced by 27.27%~63.64%and 59.09%~62.12%.Compared to the D^(*)algorithm,there are significant improvements in pathfinding speed,traversing nodes,and the number of path bends.Furthermore,experiments on the improved A^(*)algorithm are conducted in the real environment to verify its better performance and path planning ability.