改进A*算法的移动机器人最短路径规划

摘要

Aiming at the poor real-time performance of mobile robot path planning in complex indoor environment,a further improvement on A * algorithm was proposed by analyzing and comparing Dijkstra algorithm,traditional A * algorithm and some improved A* algorithms.Firstly,the estimated path cost of the current node and its parent node were weighted in exponentially decreasing way.In this way,when the current code was far away from the target,the improved algorithm could search towards to the target quickly instead of searching around the start node.While the current code was near to the target,the algorithm could search the target carefully to ensure that the target was reachable.Secondly,the generated path was smoothed by quintic polynomia to further shorten the path and facilitate robot control.The simulation results show that compared with the traditional A* algorithm,the proposed algorithm can reduce the searching time by 93.8％ and reduce the path length by 17.6％ and get the path without quarter turning point,so that the robot could get to the destination along the planned path without a break.The proposed algorithm is verified in different scenarios,and the results show that the proposed algorithm can adapt to different environments and has good real-time performance.%针对复杂室内环境下移动机器人路径规划存在实时性差的问题,通过对Dijkstra算法、传统A*算法以及一些改进的A*算法的分析比较,提出了对A*算法的进一步改进的思路.首先对当前节点及其父节点的估计路径代价进行指数衰减的方式加权,使得A*算法在离目标点较远时能够很快地向目标点靠近,在距目标点较近时能够局部细致搜索保证目标点附近障碍物较多时目标可达;然后对生成的路径进行五次多项式平滑处理,使得路径进一步缩短且便于机器人控制.仿真结果表明,改进算法较传统A*算法时间减少93.8％,路径长度缩短17.6％、无90.转折点,使得机器人可以连续不停顿地跟踪所规划路径到达目标.在不同的场景下,对所提算法进行验证,结果表明所提算法能够适应不同的环境且有很好的实时性.