An Enhancement of A* Algorithm Applied in Automated Vehicle Parking
Keywords:
A* Algorithm, Automated Vehicle Parking, Dynamic Environment, Navigation Mesh, Path-finding AlgorithmAbstract
The A* Algorithm is a path-finding algorithm that primarily uses weighted graphs and focuses on the heuristic values of nodes. However, while effective in generating a near-optimal path in a static environment, the traditional algorithm faces limitations in navigating dynamic environments, often resulting in collisions due to its inability to recognize dynamic and moving obstacles. This limitation makes it inefficient especially in complex environments with real-world scenarios. To address these limitations, an Enhanced A* Algorithm is proposed. This algorithm utilizes Navigation Mesh data structure to generate a more optimal route with local path planning and to dynamically adjust the parameters in two-dimensional non-grid environments. The performance of the algorithms was evaluated using 12 benchmarks, each corresponding to a distinct test case and levels of complexity. Then, in terms of dynamic obstacle avoidance, a comparison between the Enhanced A* Algorithm and the traditional algorithm was conducted. Statistical analyses were also performed to assess the consistency and validity of the findings. The results demonstrated that the Enhanced A* Algorithm successfully avoided all dynamic obstacles and moving objects encountered along the path in all distinct test cases. In contrast to the traditional algorithm, which achieved an average obstacle avoidance rate of 8.33%, the enhanced algorithm consistently demonstrated a 100% average obstacle avoidance rate. The enhanced algorithm outperformed the traditional A* algorithm in generating a path in a complex environment by exhibiting optimal dynamic obstacle recognition and avoidance. The Enhanced A* Algorithm is subsequently applied to autonomous vehicle parking, following standard parking restriction laws.
References
Al-Ansarry, S., Al-Darraji, S., & Honi, D. (2023). An efficient path planning in uncertainty environments using dynamic grid-based and potential field methods. Retrieved from https://www.researchgate.net/publication/372165738_An_Efficient_Path_Planning_in_Uncertainty_Environments_using_Dynamic_Grid-Based_and_Potential_Field_Methods
Berglund, T., Brodnik, A., Jonsson, H., Staffanson, M., & Soderkvist, I. (2010). Planning smooth and obstacle-avoiding B-Spline paths for autonomous mining vehicles. IEEE Transactions on Automation Science and Engineering, 7(1), 167–172. https://doi.org/10.1109/tase.2009.2015886
Dundar, Y. (2021). Dynamic path finding method and obstacle avoidance for automated guided vehicle navigation in Industry 4.0. Retrieved from https://www.sciencedirect.com/science/article/pii/S1877050921019086
Erke, S., Bin, D., Yiming, N., & Qi, Z. (2020). An improved A-Star based path planning algorithm for autonomous land vehicles. Retrieved from https://www.researchgate.net/publication/346176563_An_improved_A-Star_based_path_planning_algorithm_for_autonomous_land_vehicles
Fahleraz, F. (2018). A comparison of BFS, Dijkstra’s and A* algorithm for grid-based path-finding in mobile robots. Retrieved from https://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2017-2018/Makalah/Makalah-IF2211-2018-016.pdf
Fu, B., Chen, L., Zhou, Y., Zheng, D., Wei, Z., Dai, J., & Pan, H. (2018). An improved A* algorithm for the industrial robot path planning with high success rate and short length. Retrieved from https://www.sciencedirect.com/science/article/abs/pii/S0921889017306590
Hassan, S., Islam, N., Fahim, A., Turja, T., & Chowdhury, S. (2020). Automated parking system using graph algorithm. Retrieved from https://www.researchgate.net/publication/340081381_Automated_Parking_System_using_Graph_Algorithm
Iskandar, U., Diah, N., Ismail, M., & Abdullah, A. (2022). Comparing the efficiency of pathfinding algorithms for NPCs in platform games. Retrieved from https://www.journalppw.com/index.php/jpsp/article/view/5109/3325
Karur, K., Sharma, N., Dharmatti, C., & Siegel, J. E. (2021). A survey of path planning algorithms for mobile robots. Vehicles, 3(3), 448–468. https://doi.org/10.3390/vehicles3030027
Mac, T. T., Copot, C., Tran, D. T., & De Keyser, R. (2016). Heuristic approaches in robot path planning: A survey. Robotics and Autonomous Systems, 86, 13–28. https://doi.org/10.1016/j.robot.2016.08.001
Min, H., Xiong, X., Wang, P., & Yu, Y. (2020). Autonomous driving path planning algorithm based on improved A* algorithm in unstructured environment. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering. https://doi.org/10.1177/0954407020959741
Nadira, S., Omar, R., & Hailma, C. (2016). Potential field methods and their inherent approaches for path planning. Retrieved from https://www.researchgate.net/publication/313389747_Potential_field_methods_and_their_inherent_approaches_for_path_planning
Omonkhodion, G. (2023). A comparative study of A* and greedy best-first search algorithms in solving 8-puzzle game. International Journal of Social Sciences and Scientific Studies, 3(1), 2321–2329. Retrieved from https://ijssass.com/index.php/ijssass/article/view/157
P. Tozour. (2004). Search space representations. In S. Rabin (Ed.), AI game programming wisdom 2 (pp. 85–102). Charles River Media.
Permana, S., Bintoro, K., Arifitama, B., & Syahputra, A. (2018). Comparative analysis of pathfinding algorithms A*, Dijkstra, and BFS on maze runner game. Retrieved from https://www.researchgate.net/publication/325368698_Comparative_Analysis_of_Pathfinding_Algorithms_A_Dijkstra_and_BFS_on_Maze_Runner_Game
Rachmawati, D., & Gustin, L. (2019). Analysis of Dijkstra’s algorithm and A* algorithm in shortest path problem. Retrieved from https://iopscience.iop.org/article/10.1088/1742-6596/1566/1/012061/pdf
Ravankar, A., Ravankar, A., Kobayashi, Y., Hoshino, Y., & Peng, C.-C. (2018). Path smoothing techniques in robot navigation: State-of-the-art, current and future challenges. Sensors, 18(9), 3170. https://doi.org/10.3390/s18093170
Singh, Y., Sharma, S., Sutton, R., Hatton, D., & Khan, A. (2018). A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents. Ocean Engineering, 169, 187–201. https://doi.org/10.1016/j.oceaneng.2018.
Song, R., Liu, Y., & Bucknall, R. (2019). Smoothed A* algorithm for practical unmanned surface vehicle path planning. Retrieved from https://www.sciencedirect.com/science/article/abs/pii/S0141118718302621
Tang, G., Tang, C., Claramunt, C., Hu, X., & Zhou, P. (2021). Geometric A-Star algorithm: An improved A-Star algorithm for AGV path planning in a port environment. Retrieved from https://ieeexplore.ieee.org/document/9391698
Wang, H., Lou, S., Jing, J., Wang, Y., Liu, W., & Liu, T. (2022). The EBS-A* algorithm: An improved A* algorithm for path planning. Retrieved from https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8853577/
Wang, J., Wu, X., & Xu, Z. (2008). Potential-based obstacle avoidance in formation control. Journal of Control Theory and Applications, 6(3), 311–316. https://doi.org/10.1007/s11768-008-6222-z
Wang, X., Shi, H., & Zhang, C. (2020). Path planning for intelligent parking system based on improved ant colony optimization. Retrieved from https://ieeexplore.ieee.org/document/9052744
You, Z., Shen, K., Huang, T., Liu, Y., & Zhang, X. (2023). Application of A* algorithm based on extended neighborhood priority search in multi-scenario maps. Retrieved from https://www.mdpi.com/2079-9292/12/4/1004
Zhang, B., Li, Z., Ni, Y., & Li, Y. (2022). Research on path planning and tracking control of automatic parking system. World Electric Vehicle Journal, 13(1), 14. https://doi.org/10.3390/wevj13010014
Zhang, C., Ao, L., Yang, J., & Xie, W. (2020). An improved A* algorithm applying to path planning of games. Retrieved from https://www.researchgate.net/publication/345400800_An_Improved_A_Algorithm_Applying_to_Path_Planning_of_Games
Zhang, J., & Sun, Y. (2022). A real-time multiplayer FPS game using 3D modeling and AI machine learning. Retrieved from https://aircconline.com/csit/papers/vol12/csit121310.pdf
Zhang, J., Wu, J., & Li, Y. (2021). Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star. Retrieved from https://journals.sagepub.com/doi/pdf/10.1177/17298814211042730
Zhu, M., Xiao, C., Gu, S., Du, Z., & Wen, Y. (n.d.). A circle grid-based approach for obstacle avoidance motion planning of unmanned surface vehicles. Retrieved from https://arxiv.org/pdf/2202.04494
