改进A^(*)算法的机器人最短路径规划研究

Research on Robot Shortest Path Planning with Improved A*Algorithm

针对在规模较大的环境下,移动机器人使用传统A^(*)算法进行路径规划时存在重复往返搜索,实时性差的问题,提出一种改进的A^(*)算法。首先,对当前节点的启发函数进行改进,用曼哈顿距离和欧式距离的中值来代替原先的启发函数,使得启发函数的值更加接近真实的路径代价,接着加入当前节点父节点到目标点的启发信息,使得搜索方向在实际搜索中更有目的性地接近终点,减少了算法的遍历点数,提高了搜索效率,最后在规模较大的栅格环境中进行仿真实验。结果表明,改进的A^(*)算法相对于传统的A^(*)算法,拓展的栅格数减少了90%,算法时间平均减少了85%,并且随着地图规模的增大,路径规划的效率也能相应提高。

In order to solve the problems of repeated round-trip search and poor real-time performance when the traditional A^(*)algorithm is used for path planning of mobile robots in a large scale environment,an improved A^(*)algorithm is proposed.First of all,to improve the heuristic function of the current node,the value of Manhattan distance and Euclidean distance replaces the original inspiration function,which makes the value of the heuristic function more close to the real path cost,then joins the current node parent node to the target point of heuristic information,makes the search direction in the actual search purpose more close to the end,reduces the traverse points of the algorithm.Finally,the simulation experiment is carried out in a large grid environment.The results show that compared with the traditional A^(*)algorithm,the expanded grid number of the improved A^(*)algorithm is reduced by 90%,the average algorithm time is reduced by 85%,and the efficiency of path planning can be improved with the increase of map scale.