关键词: 移动机器人, 最短路径规划, Dijkstra算法, A^*算法, 五次多项式

Abstract: 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.

Key words: mobile robot, path planning, shortest Dijkstra algorithm, A^* algorithm, quintic polynomia