A-star Algorithm & Hybrid A-star Algorithm
DOI:
https://doi.org/10.54097/jzm6r653Keywords:
A-star Algorithm; Hybrid A-star Algorithm; Trajectory smoothness; Performance.Abstract
A-star Algorithm and Hybrid A-star Algorithm are universally utilized in automatic path planning. However, based on previous research, in various scenarios, the two algorithms have potential issues in the generation of an optimized path. This essay proposes a review of previous work and conclusions to objectively assess the performance of each algorithm in various aspects, ranging from computational time, success rate, efficiency, trajectory smoothness, to versatility among diverse circumstances. These aspects are crucial in practical applications of autonomous navigation, where the balance between speed, reliability, and adaptability directly impacts system performance. After the analysis on benefits and drawbacks of each algorithm, a comprehensive conclusion is drawn that A-Star has features of wide adaptability, high efficiency and low computational speed in complex conditions, while Hybrid A-star Algorithm provides precise trajectory planning based on car limitations with smooth driving but attached with lower success rate in some conditions and additional expense on hardware. This makes Hybrid A-star more suitable for structured environments where kinematic feasibility and smooth manoeuvring are prioritized. Both algorithms face distinct issues and are recommended to be utilized in distinct fields based on the conclusion drawn. The final recommendations emphasize that algorithm selection should be scenario-dependent, considering trade-offs between performance and resource requirements.
Downloads
References
[1] G. Tang, C. Tang, C. Claramunt, X. Hu and P. Zhou. Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment. In IEEE Access, 2021, vol. 9, pp. 59196-59210.
[2] T. Kunz, U. Reiser, M. Stilman and A. Verl. Real-time path planning for a robot arm in changing environments. 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2010, pp. 5906-5911.
[3] X. Li, X. Hu, Z. Wang and Z. Du. Path Planning Based on Combinaion of Improved A-STAR Algorithm and DWA Algorithm. 2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture (AIAM), 2020, pp. 99-103.
[4] L. Schmid, M. Pantic, R. Khanna, L. Ott, R. Siegwart and J. Nieto. An Efficient Sampling-Based Method for Online Informative Path Planning in Unknown Environments. IEEE Robotics and Automation Letters, 2020, vol. 5, no. 2, pp. 1500-1507.
[5] Munir R and Lidya L 1998 Algoritma dan Pemrogaman (Bandung: Informatika)
[6] Sedighi S, Nguyen D V, Kuhnert K D. Guided hybrid A-star path planning algorithm for valet parking applications[C]. IEEE, 2019 5th international conference on control, automation and robotics (ICCAR). 2019, 570-575.
[7] Duchoň F, Babinec A, Kajan M, et al. Path planning with modified a star algorithm for a mobile robot[J]. Procedia engineering, 2014, vol 9, pp. 9-69.
[8] C. Ju, Q. Luo and X. Yan. Path Planning Using an Improved A-star Algorithm. 2020 11th International Conference on Prognostics and System Health Management (P+HM-2020 Jinan), 2020, pp. 23-26.
[9] L. Greche, M. Jazouli, N. Es-Sbai, A. Majda and A. Zarghili. Comparison between Euclidean and Manhattan distance measure for facial expressions classification. 2017 International Conference on Wireless Technologies, Embedded and Intelligent Systems (WITS), 2017, pp. 1-4.
[10] Liwei Wang, Yan Zhang and Jufu Feng. On the Euclidean distance of images. In IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, vol. 27, no. 8, pp. 1334-1339.
[11] Daniel Foead, Alifio Ghifari, Marchel Budi Kusuma, Novita Hanafiah, Eric Gunawan. A Systematic Literature Review of A* Pathfinding, Procedia Computer Science, 2021, Volume 179, pp. 507-514, ISSN 1877-0509.
[12] Oluwaseun Opeyemi Martins, Adefemi Adeyemi Adekunle, Olatayo Moses Olaniyan, Bukola Olalekan Bolaji. An Improved multi-objective a-star algorithm for path planning in a large workspace: Design, Implementation, and Evaluation. Scientific African, 2022, vol. 15, e01068, ISSN 2468-227.
[13] J. Yu, J. Hou and G. Chen. Improved Safety-First A-Star Algorithm for Autonomous Vehicles. 2020 5th International Conference on Advanced Robotics and Mechatronics (ICARM), 2020, pp. 706-710.
[14] Y. Zhou, X. Cheng, X. Lou, Z. Fang and J. Ren. Intelligent Travel Planning System based on A-star Algorithm," 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), Chongqing, China, 2020, pp. 426-430.
[15] Wayahdi M R, Ginting S H N, Syahputra D. Greedy, A-Star, and Dijkstra's algorithms in finding shortest path[J]. International Journal of Advances in Data and Information Systems, 2021, 2(1): 45-52.
[16] A. Candra, M.A. Budiman, & K. Hartanto. Dijkstra’s and A-Star in Finding the Shortest Path: a Tutorial. IEEE International Conference on Data Science, Artificial Intelligence, and Business Analytics (DATABIA), 2020, pp. 28-32,
[17] S. Mahadewi, K.R. Shylaja, & M.E. Ravinandan. Memory Based A-Star Algorithm for Path Planning of a Mobile Robot. International Journal of Science and Research (IJSR), 2014, vol. 3, issue 6, pp. 1351-1355.
[18] Z. Lin, K. Wu, R. Shen, X. Yu and S. Huang. An Efficient and Accurate A-Star Algorithm for Autonomous Vehicle Path Planning. In IEEE Transactions on Vehicular Technology, 2024, vol. 73, no. 6, pp. 9003-9008.
[19] Kumar N. Bidirectional Graph Search Techniques for Finding Shortest Path in Image Based Maze Problem (Master's thesis, Punjab Technical University). 2019, pp. 1411-1414.
[20] J. Liu, J. Yang, H. Liu, X. Tian and M. Gao. An improved ant colony algorithm for robot path planning. Soft Comput., 2017, vol. 21, no. 19, pp. 5829-5839..
[21] H. Li, Z. Chen, Z. Huang and Z. Gao. Research on Automatic Parking Path Planning Based on Bidirectional Hybrid A-Star Algorithm. 2024 11th International Forum on Electrical Engineering and Automation (IFEEA), 2024, pp. 1251-1254.
[22] H. Zheng, M. Dai, Z. Zhang, Z. Xia, G. Zhang and F. Jia. The Navigation Based on Hybrid A Star and TEB Algorithm Implemented in Obstacles Avoidance. 2023 29th International Conference on Mechatronics and Machine Vision in Practice (M2VIP), 2023, pp. 1-6.
[23] J. Ziegler, M. Werling and J. Schroder. Navigating car-like robots in unstructured environments using an obstacle sensitive cost function. 2008 IEEE Intelligent Vehicles Symposium, 2008, pp. 787-791.
[24] W. Sheng, B. Li and X. Zhong. Autonomous Parking Trajectory Planning With Tiny Passages: A Combination of Multistage Hybrid A-Star Algorithm and Numerical Optimal Control. In IEEE Access, 2021, vol. 9, pp. 102801-102810.
[25] R. Song, T. Chen, J. Pan and Y. Peng. Adaptive Path Planning for Amphibious Vehicles Based on Enhanced Hybrid A-Star Algorithm. 2024 8th International Conference on Electrical, Mechanical and Computer Engineering (ICEMCE), 2024, pp. 1584-1589.
[26] Qiu D, Li X, Yang H, Zhu X. Time-optimal global trajectory planning for autonomous valet parking: An improved hybrid A-star algorithm-based optimization control approach. International Journal of Advanced Robotic Systems. 2025, 22(2).
[27] C. Li, D. Yu, W. Lu and M. Li. Variable-curvature hybrid A-star search for AMR path planning in limited space. 2021 3rd International Symposium on Robotics & Intelligent Manufacturing Technology (ISRIMT), 2021, pp. 61-65.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Highlights in Science, Engineering and Technology
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
