Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (5): 1523-1526.DOI: 10.11772/j.issn.1001-9081.2017102446

Previous Articles    

The shortest path planning for mobile robots using improved A* algorithm

WANG Wei1, PEI Dong1,2, FENG Zhang1   

  1. 1. College of Physics and Electronic Engineering, Northwest Normal University, Lanzhou Gansu 730030, China;
    2. Engineering Research Center of Gansu Province for Intelligence Information Technology and Application, Lanzhou Gansu 730030, China
  • Received:2017-10-16 Revised:2018-01-13 Online:2018-05-10 Published:2018-05-24
  • Contact: 裴东

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

王维1, 裴东1,2, 冯璋1   

  1. 1. 西北师范大学 物理与电子工程学院, 兰州 730030;
    2. 甘肃省智能信息技术与应用工程研究中心, 兰州 730030
  • 通讯作者: 裴东
  • 作者简介:王维(1991-),男,甘肃陇南人,硕士研究生,主要研究方向:机器人定位与导航、机器学习;裴东(1965-),男,甘肃兰州人,副教授,主要研究方向:模式识别、机器人控制;冯璋(1992-),男,湖南岳阳人,硕士研究生,主要研究方向:机器视觉、图像处理。

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

摘要: 针对复杂室内环境下移动机器人路径规划存在实时性差的问题,通过对Dijkstra算法、传统A*算法以及一些改进的A*算法的分析比较,提出了对A*算法的进一步改进的思路。首先对当前节点及其父节点的估计路径代价进行指数衰减的方式加权,使得A*算法在离目标点较远时能够很快地向目标点靠近,在距目标点较近时能够局部细致搜索保证目标点附近障碍物较多时目标可达;然后对生成的路径进行五次多项式平滑处理,使得路径进一步缩短且便于机器人控制。仿真结果表明,改进算法较传统A*算法时间减少93.8%,路径长度缩短17.6%、无90°转折点,使得机器人可以连续不停顿地跟踪所规划路径到达目标。在不同的场景下,对所提算法进行验证,结果表明所提算法能够适应不同的环境且有很好的实时性。

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

CLC Number: