Mobile Robot Path Planning Based on an Improved A<sup>*</sup> Algorithm

ZHAO Xiao; WANG Zheng; HUANG Chengkan; ZHAO Yanwei

doi:10.13973/j.cnki.robot.170591

Volume 40 Issue 6

Nov. 2018

Turn off MathJax

Article Contents

Abstract

References

ROBOT > 2018 > 40(6): 903-910. > DOI: 10.13973/j.cnki.robot.170591 CSTR: 32165.14.robot.170591

ZHAO Xiao, WANG Zheng, HUANG Chengkan, ZHAO Yanwei. Mobile Robot Path Planning Based on an Improved A^* Algorithm[J]. ROBOT, 2018, 40(6): 903-910. DOI: 10.13973/j.cnki.robot.170591

Citation:

ZHAO Xiao, WANG Zheng, HUANG Chengkan, ZHAO Yanwei. Mobile Robot Path Planning Based on an Improved A^* Algorithm[J]. ROBOT, 2018, 40(6): 903-910. DOI: 10.13973/j.cnki.robot.170591

Citation:

ZHAO Xiao, WANG Zheng, HUANG Chengkan, ZHAO Yanwei. Mobile Robot Path Planning Based on an Improved A^* Algorithm[J]. ROBOT, 2018, 40(6): 903-910. DOI: 10.13973/j.cnki.robot.170591

PDF (985 KB)

Mobile Robot Path Planning Based on an Improved A^* Algorithm

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

More Information

Received Date: October 26, 2017
Revised Date: March 22, 2018
Available Online: October 26, 2022
Published Date: November 14, 2018

Graphical Abstract

Abstract

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.
- mobile robot,
- path planning,
- A^* algorithm,
- jump point search

FullText(HTML)

References (19)

References

[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.

Cited By

Get Citation

PDF

XML

Article views (371) PDF downloads (835)

Mobile Robot Path Planning Based on an Improved A^* Algorithm

Abstract

References

Catalog

Related

Mobile Robot Path Planning Based on an Improved A* Algorithm

Abstract

References

Catalog

Related

Export File

Citation

Format

Content

Mobile Robot Path Planning Based on an Improved A^* Algorithm