Performance Comparison of A and Dijkstra Algorithms with Bézier Curve in 2D Grid and OpenStreetMap Scenarios

Zakariah Yusuf; Sufian Mohamad; Wan Suhaifiza  Wan Ibrahim

doi:10.24191/jaeds.v5i2.94

Authors

Zakariah Yusuf Electrical Engineering Studies, Universiti Teknologi MARA, Cawangan Johor, Kampus Pasir Gudang, Masai, Johor, Malaysia
Sufian Mohamad Electrical Engineering Studies, Universiti Teknologi MARA, Cawangan Johor, Kampus Pasir Gudang, Masai, Johor, Malaysia
Wan Suhaifiza Wan Ibrahim Electrical Engineering Studies, Universiti Teknologi MARA, Cawangan Johor, Kampus Pasir Gudang, Masai, Johor, Malaysia

DOI:

https://doi.org/10.24191/jaeds.v5i2.94

Keywords:

2D Map, OpenStreetMap, Bézier Curve Smoothing, A* Algorithm, Dijkstra Algorithm

Abstract

This paper presents a comparative study of the A* and Dijkstra algorithms for path planning in both 2D grid maps and real-world OpenStreetMap (OSM) environments. The evaluation focused on three key performance metrics: computational efficiency, path smoothness, and the number of turns. Both algorithms were tested under varying obstacle densities, and Bézier curve smoothing was applied to enhance path quality. In 2D grid maps, A* consistently generated smoother paths with fewer turns, especially in complex environments. Its heuristic-based search allowed it to expand fewer nodes, resulting in faster computation times compared to Dijkstra. On the other hand, Dijkstra's algorithm, though robust and optimal, exhibited longer runtimes and produced paths with more turns due to its exhaustive search approach. In the OSM-based scenarios, both algorithms yielded paths of identical length. However, A* significantly outperformed Dijkstra in terms of runtime across most test cases, further demonstrating its computational advantage. These findings validate A*’s practical advantage of real-time applications where both efficiency and path quality are crucial. While Dijkstra remains a reliable benchmark, A* offers a balanced trade-off between speed and path quality, making it more suitable for real-world path planning applications in both structured and unstructured environments.

Downloads

Download data is not yet available.

References

M. Sadaf et al., “Connected and Automated Vehicles: Infrastructure, Applications, Security, Critical Challenges, and Future Aspects,” 2023. doi: 10.3390/technologies11050117.

Enoch Oluwademilade Sodiya, Uchenna Joseph Umoga, Olukunle Oladipupo Amoo, and Akoh Atadoga, “AI-driven warehouse automation: A comprehensive review of systems,” GSC Advanced Research and Reviews, vol. 18, no. 2, 2024, doi: 10.30574/gscarr.2024.18.2.0063.

V. Engesser, E. Rombaut, L. Vanhaverbeke, and P. Lebeau, “Autonomous Delivery Solutions for Last-Mile Logistics Operations: A Literature Review and Research Agenda”, Sustainability, 15(3), 2023. doi: 10.3390/su15032774.

J. R. Sánchez-Ibáñez, C. J. Pérez-Del-pulgar, and A. García-Cerezo, “Path planning for autonomous mobile robots: A review,” Sensors, 21(23), 2021. doi: 10.3390/s21237898.

E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer Math (Heidelb), vol. 1, no. 1, 1959, doi: 10.1007/BF01386390.

S. K. Sahoo and B. B. Choudhury, “A Review of Methodologies for Path Planning and Optimization of Mobile Robots,” Journal of Process Management and New Technologies, vol. 11, no. 1–2, 2023, doi: 10.5937/jpmnt11-45039.

A. Fitro, O. S. Bachri, A. I. Sulistio Purnomo, and I. Frendianata, “Shortest path finding in geographical information systems using node combination and dijkstra algorithm,” International Journal of Mechanical Engineering and Technology, vol. 9, no. 2, 2018.

S. Ergün, S. Z. A. Gök, T. Aydoğan, and G. W. Weber, “Performance analysis of a cooperative flow game algorithm in ad hoc networks and a comparison to Dijkstra’s algorithm,” Journal of Industrial and Management Optimization, vol. 15, no. 3, 2019, doi: 10.3934/jimo.2018086.

M. Luo, X. Hou, and J. Yang, “Surface Optimal Path Planning Using an Extended Dijkstra Algorithm,” IEEE Access, vol. 8, 2020, doi: 10.1109/ACCESS.2020.3015976.

D. Foead, A. Ghifari, M. B. Kusuma, N. Hanafiah, and E. Gunawan, “A Systematic Literature Review of A*Pathfinding,” in Procedia Computer Science, 2021. doi: 10.1016/j.procs.2021.01.034.

H. Zhang, Y. Tao, and W. Zhu, “Global Path Planning of Unmanned Surface Vehicle Based on Improved A-Star Algorithm,” Sensors, vol. 23, no. 14, 2023, doi: 10.3390/s23146647.

H. Wang, X. Zhou, J. Li, Z. Yang, and L. Cao, “Improved RRT* Algorithm for Disinfecting Robot Path Planning,” Sensors, vol. 24, no. 5, 2024, doi: 10.3390/s24051520.

S. Mondal and B. Chen, “Development of Autonomous Vehicle Motion Planning and Control Algorithms with D* Planner and Model Predictive Control,” in Lecture Notes in Networks and Systems, 2024. doi: 10.1007/978-3-031-47718-8_52.

M. Rivai, D. Hutabarat, and Z. M. Jauhar Nafis, “2D mapping using omni-directional mobile robot equipped with LiDAR,” Telkomnika (Telecommunication Computing Electronics and Control), vol. 18, no. 3, 2020, doi: 10.12928/TELKOMNIKA.v18i3.14872.

A. J. Barreto-Cubero, A. Gómez-Espinosa, J. A. Escobedo Cabello, E. Cuan-Urquizo, and S. R. Cruz-Ramírez, “Sensor data fusion for a mobile robot using neural networks,” Sensors, vol. 22, no. 1, 2022, doi: 10.3390/s22010305.

W. Li, “Synthesizing Virtual World Palace Scenes on OpenStreetMap,” in Proceedings - 2023 7th International Conference on Computer, Software and Modeling, ICCSM 2023, 2023. doi: 10.1109/ICCSM60247.2023.00021.

V. Bulut, “Path planning for autonomous ground vehicles based on quintic trigonometric Bézier curve: Path planning based on quintic trigonometric Bézier curve,” Journal of the Brazilian Society of Mechanical Sciences and Engineering, vol. 43, no. 2, 2021, doi: 10.1007/s40430-021-02826-8.

S. Blažic, G. Klancar, M. B. Loknar, and I. Škrjanc, “Warehouse Path Planning Using Low-order Bézier Curves with Minimum-Time Optimization,” in IFAC-PapersOnLine, 2023. doi: 10.1016/j.ifacol.2023.10.578.