Authors : Shrikar Nagarajan; Aarav Upreti; Nathanael Dhanapal; Nathan Dsouza

Volume/Issue : Volume 10 - 2025, Issue 9 - September

Google Scholar : https://tinyurl.com/y5spnnj5

Scribd : https://tinyurl.com/4zphzmcs

DOI : https://doi.org/10.38124/ijisrt/25sep776

Note : A published paper may take 4-5 working days from the publication date to appear in PlumX Metrics, Semantic Scholar, and ResearchGate.

Note : Google Scholar may take 30 to 40 days to display the article.

Abstract : Pathfinding is critical in mobile robotics for enabling autonomous navigation from a start to a goal location while avoiding obstacles. This study implements six representative pathfinding algorithms – Dijkstra, A*, Breadth-First Search (BFS), Greedy Best-First Search, Bug1, and Bug2 – and compares their performance on grid-based maps under low-cost robot constraints (limited battery and sensing) and dynamic changes (moving obstacles). We simulate a two-dimensional grid world with static and dynamic obstacles, modeling a simple wheeled robot with limited sensors and a finite battery. Each algorithm is evaluated on key metrics: path length, computation time, battery usage (proportional to distance traveled and actions taken), success rate (reaching the goal without failure), and adaptability to environmental changes. Our results show that A* consistently yields the shortest path and fastest search time in static, known environments, while BFS and Dijkstra also find optimal paths, albeit with higher computational costs. Greedy Best-First Search often finds a path quickly but can produce suboptimal or invalid paths under complex scenarios. The simple Bug algorithms (Bug1 and Bug2) are robust to unknown obstacles (requiring only local sensing) and guarantee finding a path if one exists, albeit at the expense of significantly longer detours and greater energy consumption. In dynamic scenarios (moving obstacles), global planners (A*, Dijkstra) must replan or may fail, whereas reactive Bug planners naturally cope by following obstacle boundaries. Overall, A* performs best in static settings with sufficient compute, while simpler methods or hybrid strategies may be preferable for very low-cost robots or highly dynamic settings. Our comprehensive comparison highlights the trade-offs of each algorithm and guides the choice of planning strategy based on environmental demands and resource constraints.

Keywords : Pathfinding Algorithms, Low-Cost Mobile Robots, Dynamic Environments,

References :

1. Akmandor, N. Ü., & Padır, T. (2021). Reactive navigation framework for mobile robots by heuristically evaluating pre‑sampled trajectories. arXiv preprint arXiv:2105.08145. https://doi.org/10.48550/arXiv.2105.08145
2. Fahleraz, F. (2018). A comparison of BFS, Dijkstra’s, and A algorithms for grid-based path-finding in mobile robots. Unpublished manuscript, Institut Teknologi Bandung, Indonesia.
3. Felner, A., & Kumar, R. (2011). Position paper: Dijkstra’s algorithm versus uniform cost search or a case against Dijkstra’s algorithm. Electronic Proceedings in Theoretical Computer Science, 69, 55–61.
4. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
5. Kim, T., Lim, S., Shin, G., & Yun, D. (2022). An open-source low-cost mobile robot with efficient real-time navigation architecture. Unpublished manuscript. https://www.researchgate.net/publication/358704783
6. Koenig, S., & Likhachev, M. (2002). D* Lite. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 15, No. 2, pp. 476–483). https://doi.org/10.1609/aaai.v15i2.12113
7. Kurtipek, S. (2020, April 12). Robot motion planning: Bug algorithms. Medium. https://medium.com/@sefakurtipek/robot-motion-planning-bug-algorithms-34cf5175ab39
8. LaValle, S. M. (2006). Planning algorithms. Cambridge University Press. https://planning.cs.uiuc.edu/
9. Lumelsky, V. J., & Stepanov, A. A. (1986). Path-planning strategies for point mobile automata in unknown environments. IEEE Transactions on Systems, Man, and Cybernetics, 16(6), 614–628. https://doi.org/10.1109/TSMC.1986.289289
10. McGuire, K., de Croon, G., & Tuyls, K. (2018). A comparative study of Bug algorithms for robot navigation. arXiv preprint arXiv:1808.05050. https://doi.org/10.48550/arXiv.1808.05050
11. Patel, M., & Sivaraman, D. (2021). Energy-aware path planner for mobile robots in unstructured environments. arXiv preprint arXiv:2104.01560. https://doi.org/10.48550/arXiv.2104.01560
12. Rapalski, A., & Dudzik, S. (2023). Energy consumption analysis of selected navigation algorithms for wheeled mobile robots. Energies, 16(3), 1532. https://doi.org/10.3390/en16031532
13. Russell, S., & Norvig, P. (2021). Artificial intelligence: A modern approach (4th ed.). Pearson.
14. Spektor, I., Zagirov, A., Safin, R., & Magid, E. (2024). Implementation of Bug1 and Bug2 basic path-planning algorithms for a TurtleBot 3 robot in ROS Noetic. In Proceedings of the 2024 International Conference on Artificial Life and Robotics (ICAROB) (pp. 27–32).
15. Ajeil, F. H., Ibraheem, I. K., Sahib, M. A., & Humaidi, A. J. (2018). Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm. arXiv preprint arXiv:1805.00224. https://doi.org/10.48550/arXiv.1805.00224
16. Bonilla Licea, D., Ghogho, M., & Saska, M. (2022). When robotics meets wireless communications: An introductory tutorial. arXiv preprint arXiv:2203.08903.
17. Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., & Thrun, S. (2005). Principles of robot motion: Theory, algorithms, and implementations. MIT Press.
18. Das, S. D., Bain, V., & Rakshit, P. (2018). Energy optimized robot arm path planning using differential evolution in a dynamic environment. arXiv preprint arXiv:1806.08916.
19. Fetanat, M., Haghzad, S., & Shouraki, S. B. (2019). Optimization of dynamic mobile robot path planning based on evolutionary methods. arXiv preprint arXiv:1902.03390.
20. Felner, A., Stern, R., Shimony, S. E., Boyarski, E., Goldenberg, M., & Sharon, G. (2011). Search-based optimal solvers for the multi-agent pathfinding problem: Summary and challenges. In Proceedings of the Tenth International Symposium on Abstraction, Reformulation, and Approximation (pp. 29–36). https://doi.org/10.1007/978-3-642-25462-8_4
21. Maneev, V. V., & Syryamkin, M. V. (2019). Optimizing the A search algorithm for mobile robotic devices. IOP Conference Series: Materials Science and Engineering, 516(1), 012054. https://doi.org/10.1088/1757-899X/516/1/012054
22. Siegwart, R., & Nourbakhsh, I. R. (2011). Introduction to autonomous mobile robots (2nd ed.). MIT Press.
23. Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic robotics. MIT Press.
24. Whittaker, W. C., Wilkinson, C., & Crane, J. (2009). A comparison of cell decomposition techniques for mobile robot navigation. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 2745–2750). https://doi.org/10.1109/IROS.2009.5354495
25. Wu, C., Dai, C., Gong, X., & Wang, C. C. L. (2019). Energy-efficient coverage path planning for autonomous mobile robots on 3D terrain. Robotics and Autonomous Systems, 117, 90–101. https://doi.org/10.1016/j.robot.2019.01.016
26. Zafar, M. N., & Mohanta, J. C. (2018). Methodology for path planning and optimization of mobile robots: A review. International Journal of Advanced Robotic Systems, 15(1), 1729881418771023. https://doi.org/10.1177/1729881418771023
27. Zhang, H., Zhang, Y., & Yang, T. (2020). A survey of energy-efficient motion planning for wheeled mobile robots. Industrial Robot, 47(5), 687–698. https://doi.org/10.1108/IR-04-2020-0100
28. Fahleraz, F. (2018). A comparison of BFS, Dijkstra’s and A algorithm for grid-based path-finding in mobile robots* [Unpublished manuscript]. Program Studi Teknik Informatika, Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung. https://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2017-2018/Makalah/Makalah-IF2211-2018-016.pdf
29. Ke, Y. (2023). Comparative analysis of path planning algorithms and prospects for practical application. Highlights in Science, Engineering and Technology, 52, 1–5. https://pdfs.semanticscholar.org/af2d/e2da5baec8d9b184de6e716a9c3846966ca3.pdf
30. Mohajer, B., Kiani, K., Samiei, E., & Sharifi, M. (2013). A new online random particles optimization algorithm for mobile robot path planning in dynamic environments. Mathematical Problems in Engineering, 2013, Article 491346. https://doi.org/10.1155/2013/491346