Comparative Analysis of Hybrid A* and RRT* Algorithms and Optimizing the RRT* Algorithm in Autonomous Maze Navigation
DOI:
https://doi.org/10.62051/041fds13Keywords:
A* algorithm; RRT* algorithm; Path planning.Abstract
The path planning problem of autonomous mobile robots is a very important problem in today's robotics field, and after decades of development, many path planning algorithms have been derived, among which the A* algorithm and the Rapidly Exploring Random Trees (RRT) algorithm are more widely used. These two methods use completely different basic principles, the A* algorithm relies on global search, while the RRT algorithm uses random search, in order to explore the advantages and disadvantages of the two algorithms, this paper mainly analyzes the principles of the A* algorithm and the RRT* algorithm and compares their performances in the maze navigation of robots. After that, the RRT* algorithm is also improved to make up for the shortcomings of the lower efficiency of the RRT* algorithm by utilizing a bidirectional search strategy, and then finally curve fitting is used to obtain a path that is more suitable for the robot's motivation. After comparative analysis, the A* algorithm is more suitable for precise path planning given a global map, and it can calculate the best path quickly. The RRT* algorithm is more suitable for the path planning problem of an unknown map, and due to the principle of stochastic search, it can make the algorithm calculate a reachable path faster.
Downloads
References
Z. He and L. Zhao, The Comparison of Four UAV Path Planning Algorithms Based on Geometry Search Algorithm, 2017 9th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, China, pp. 33-36, 2017. DOI: https://doi.org/10.1109/IHMSC.2017.123
S. Xiaoqiang, L. Zhichao, Z. Xuan and N. Xinchao, Research on Robot Path Planning Based on Improved Adaptive Ant Colony Algorithm, 2019 Chinese Control And Decision Conference (CCDC), Nanchang, China, pp. 506-510, 2019. DOI: https://doi.org/10.1109/CCDC.2019.8832668
K. Tu, S. Yang, H. Zhang and Z. Wang, Hybrid A∗ Based Motion Planning for Autonomous Vehicles in Unstructured Environment, 2019 IEEE International Symposium on Circuits and Systems (ISCAS), Sapporo, Japan, pp. 1-4, 2019. DOI: https://doi.org/10.1109/ISCAS.2019.8702779
Fda B , Aba B , Mka B , et al. Path Planning with Modified a Star Algorithm for a Mobile Robot - ScienceDirect[J]. Procedia Engineering, 96:59-69, 2014. DOI: https://doi.org/10.1016/j.proeng.2014.12.098
Q. Zhou and G. Liu, "UAV Path Planning Based on the Combination of A-star Algorithm and RRT-star Algorithm," 2022 IEEE International Conference on Unmanned Systems (ICUS), Guangzhou, China, pp. 146-151, 2022. DOI: https://doi.org/10.1109/ICUS55513.2022.9986703
X. Li, Y. Fang and W. Fu, "UAV Path Planning Based on Shuffled Frog-Leaping Algorithm and Dubins Path," 2020 39th Chinese Control Conference (CCC), Shenyang, China, pp. 3990-3995, 2020. DOI: https://doi.org/10.23919/CCC50068.2020.9188570
L. Zhao, J. Liu and J. Wang, "Path Planning of Sand Blasting Robot Based on Improved RRT Algorithm," 2019 IEEE International Conference on Mechatronics and Automation (ICMA), Tianjin, China, pp. 1901-1906, 2019. DOI: https://doi.org/10.1109/ICMA.2019.8816383
C. Li, H. Ma, J. Wang and M. Q.-H. Meng, "Bidirectional Search Strategy for Incremental Search-based Path Planning," 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Detroit, MI, USA, pp. 7311-7317, 2023. DOI: https://doi.org/10.1109/IROS55552.2023.10342039
Y. Xie, J. Yang, M. Feng, W. Huang and J. Li, "Path planning of grinding robot with force control based on B-spline curve," 2019 IEEE International Conference on Robotics and Biomimetics (ROBIO), Dali, China, pp. 2732-2736, 2019. DOI: https://doi.org/10.1109/ROBIO49542.2019.8961568
Published
Conference Proceedings Volume
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
