Mobile Robot Path Planning Based on an Improved A* Algorithm
ZHAO Xiao1, WANG Zheng2, HUANG Chengkan1, ZHAO Yanwei1,2
1. Key Laboratory of Special Purpose Equipment and Advanced Manufacturing Technology, Ministry of Education, Zhejiang University of Technology, Hangzhou 310014, China;
2. College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China
Abstract:Aiming at the problems of A* algorithm in the large scene, such as large memory overhead and long computation time, an improved A* algorithm is proposed based on A* algorithm and jump point search algorithm. The algorithm expands by selecting jump points until the final path is generated. During the expansion process, a lot of unnecessary nodes in A* algorithm which are added to OpenList and ClosedList can be replaced by jump points to reduce computation. In order to prove the validity of the improved A* algorithm, the simulation is carried out in 2D grid map of different sizes. The simulation result shows that the improved A* algorithm expands fewer nodes in the pathfinding process, and the pathfinding speed is faster. The acceleration effect becomes more apparent with the increase of environment map. Finally, the improved A* algorithm is implemented on the mobile robot Turtlebot2 to conduct comparative experiments. The experimental result shows that the improved A* algorithm can speed up by about 200% compared with the A* algorithm when generating the same path, and it can meet the requirements of path planning for mobile robots.
[1] 曲道奎,杜振军,徐殿国,等.移动机器人路径规划方法研究[J].机器人,2008,30(2):97-101,106.Qu D K, Du Z J, Xu D G, et al. Research on path planning for a mobile robot[J]. Robot, 2008, 30(2):97-101,106.
[2] 王殿君.基于改进A* 算法的室内移动机器人路径规划[J].清华大学学报:自然科学版,2012,52(8):1085-1089.Wang D J. Indoor mobile-robot path planning based on an improved A* algorithm[J]. Journal of Tsinghua University:Science and Technology, 2012, 52(08):1085-1089.
[3] Jeddisaravi K, Alitappeh R J, Pimenta L C A, et al. Multi-objective approach for robot motion planning in search tasks[J]. Applied Intelligence, 2016, 45(2):305-321.
[4] 刘一松,魏宁,孙亚民.基于栅格法的虚拟人快速路径规划[J].计算机工程与设计,2008(5):1229-1230,1267.Liu Y S, Wei N, Sun Y M. Path planning algorithm based on grid method for virtual human[J]. Computer Engineering and Design, 2008(5):1229-1230,1267.
[5] Bakdi A, Hentout A, Boutami H, et al. Optimal path planning and execution for mobile robots using genetic algorithm and adaptive fuzzy-logic control[J]. Robotics and Autonomous Systems, 2017, 89(1):95-109.
[6] 刘建华,杨建国,刘华平,等.基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报,2015,46(9):18-27.Liu J H, Yang J G, Liu H P, et al. Robot global path planning based on ant colony optimization with artificial potential field[J]. Transactions of the Chinese Society of Agricultural Machinery, 2015, 46(9):18-27.
[7] 朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967.Zhu D Q, Yan M Z. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7):961-967.
[8] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1):269-271.
[9] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2):100-107.
[10] Stentz A. Optimal and efficient path planning for partially-known environments[C]//IEEE International Conference on Robotics and Automation. Piscataway, USA:IEEE, 2002:3310-3317.
[11] Koenig S, Likhachev M. Fast replanning for navigation in unknown terrain[J]. IEEE Transactions on Robotics, 2005, 21(3):354-363.
[12] 辛煜,梁华为,杜明博,等.一种可搜索无限个邻域的改进A* 算法[J].机器人,2014,36(5):627-633.Xin Y, Liang H W, Du M B, et al. An improved A* algorithm for searching infinite neighbourhoods[J]. Robot, 2014, 36(5):627-633.
[13] Korf R E. Depth-first iterative-deepening:An optimal admissible tree search[J]. Artificial Intelligence, 1985, 27(1):97-109.
[14] Botea A, Müller M, Schaeffer J. Near optimal hierarchical path-finding[J]. Journal of Game Development, 2004, 1:7-28.
[15] Goldberg A V, Harrelson C. Computing the shortest path:A* search meets graph theory[C]//Annual ACM-SIAM Symposium on Discrete Algorithms. New York, USA:ACM, 2005:156-165.
[16] Sturtevant N R, Felner A, Barrer M, et al. Memory-based heuristics for explicit state spaces[C]//International Joint Conference on Artificial Intelligence. USA:International Joint Conferences on Artificial Intelligence, 2009:609-614.
[17] Harabor D, Grastien A. The JPS pathfinding system[C]//5th Annual Symposium on Combinatorial Search. Menlo Park, USA:AAAI, 2012:207-208
[18] Korf R E. Real-time heuristic search[J]. Artificial Intelligence, 1990, 42(2/3):189-211.
[19] Harabor D, Grastien A. Online graph pruning for pathfinding on grid maps[C]//25th AAAI Conference on Artificial Intelligence. Menlo Park, USA:AAAI, 2011:1114-1119.