Comprehensive Performance Analysis and Evaluation of Various Maze Solving Algorithms for Optimized Autonomous Navigation and Pathfinding

Öz

Recent advancements in technology have led to the widespread use of maze-solving algorithms in various applications, such as autonomous robots, GPS-based navigation systems, smart traffic management systems, and healthcare services. This study provides a comprehensive comparative analysis of the performance of several maze-solving algorithms, including A*, Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra, Flood Fill, Random Mouse, and Recursive Backtracker. The algorithms were evaluated based on key performance metrics such as solution speed, memory usage, and CPU consumption. The results indicate that while the DFS algorithm demonstrates the fastest solution time with minimal memory usage, it has higher CPU consumption. In contrast, the Random Mouse algorithm is the least efficient, showing the highest memory and CPU usage along with the longest solution time. The A* algorithm, although efficient in finding the shortest path, showed moderate performance in both memory and CPU usage. These findings offer valuable insights into the strengths and weaknesses of each algorithm, providing guidance for future improvements and applications in real-world scenarios. This study aims to be a valuable resource for researchers and engineers focused on enhancing the efficiency of maze-solving algorithms in various technological domains

Anahtar Kelimeler

• Autonomous systems
• maze solving algorithms
• navigation technologies
• pathfinding optimization
• performance analysis

Çeşitli Labirent Çözme Algoritmalarının Optimum Otonom Navigasyon ve Yol Bulma için Kapsamlı Performans Analizi ve Değerlendirilmesi

Öz

Teknolojideki son gelişmeler, otonom robotlar, GPS tabanlı navigasyon sistemleri, akıllı trafik yönetim sistemleri ve sağlık hizmetleri gibi çeşitli uygulamalarda labirent çözme algoritmalarının yaygın olarak kullanılmasına yol açmıştır. Bu çalışma, A*, Genişlik Öncelikli Arama (BFS), Derinlik Öncelikli Arama (DFS), Dijkstra, Flood Fill, Random Mouse ve Recursive Backtracker dahil olmak üzere çeşitli labirent çözme algoritmalarının performansının kapsamlı karşılaştırmalı bir analizini sunmaktadır. Algoritmalar, çözüm hızı, bellek kullanımı ve CPU tüketimi gibi ana performans metrikleri temelinde değerlendirilmiştir. Sonuçlar, DFS algoritmasının minimal bellek kullanımı ile en hızlı çözüm süresini gösterirken, daha yüksek CPU tüketimine sahip olduğunu göstermektedir. Buna karşılık, Random Mouse algoritması en verimsiz olup, en yüksek bellek ve CPU kullanımının yanı sıra en uzun çözüm süresini göstermektedir. A* algoritması, en kısa yolu bulmada verimli olmasına rağmen, bellek ve CPU kullanımında orta düzeyde performans göstermiştir. Bu bulgular, her bir algoritmanın güçlü ve zayıf yönlerine ilişkin değerli bilgiler sunmakta ve gerçek dünya uygulamalarında gelecekteki iyileştirmeler ve uygulamalar için rehberlik sağlamaktadır. Bu çalışma, labirent çözme algoritmalarının verimliliğini artırmayı hedefleyen araştırmacılar ve mühendisler için değerli bir kaynak olmayı amaçlamaktadır.

Anahtar Kelimeler

• Otonom sistemler
• labirent çözme algoritmaları
• navigasyon teknolojileri
• yol bulma optimizasyonu
• performans analizi

Kaynakça

1. Lumelsky VJ. A comparative study on the path length performance of maze-searching and robot motion planning algorithms. IEEE Trans Robot Autom 1991; 7(1): 57-66.
2. Alamri S, Alshehri S, Alshehri W, Alamri H, Alaklabi A, Alhmiedat T. Autonomous maze solving robotics: Algorithms and systems. Int J Mech Eng Robot Res 2021; 10(12): 668-675.
3. Kaur NKS. A review of various maze solving algorithms based on graph theory. Int J Sci Res Dev 2019; 6(12): 431-434.
4. Covaci R, Harja G, Nascu I. Autonomous Maze Solving Robot. In: IEEE Int Conf Autom Qual Test Robot; 21 May 2020. pp. 1-4.
5. Husain Z, Al Zaabi A, Hildmann H, Saffre F, Ruta D, Isakovic AF. Search and rescue in a maze-like environment with ant and dijkstra algorithms. Drones 2022; 6(10): 273.
6. Budiman JS, Laurensia M, Arthaya BM. Arthaya. Maze mapping based modified depth first search algorithm simulator for agricultural environment. In: IEEE Int Conf Mechatron Robot Syst Eng; 17 November 2021. pp. 1-6.
7. Ali SI, Duraisamy Y, Rasheed BH, Abas SM, Masood TD. Navigating Network Traffic: An Exploration of Maze Algorithm Applications in Machine Learning. Int Innov Res J Eng Technol; 2 April 2024; 9(3).
8. Olivier T. A grid-based maze approach to humanitarian logistics. PhD, North-West University, South Africa, 2021.

9. Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern; July 1968; 4(2): 100-107.
10. Duchoň F, Babinec A, Kajan M, Beňo P, Florek M, Fico T, Jurišica L. Path planning with modified a star algorithm for a mobile robot. Procedia Eng 2014. 96: 59-69.
11. Ju C, Luo Q, Yan X. Path planning using an improved a-star algorithm. In: IEEE 11th Int Conf Progn Syst Health Manage; 23 October 2020. pp. 23-26.
12. Moore EF. The shortest path through a maze. In; Proc Int Symp Theory Switch. Harvard University Press. 1959.
13. Lee CY. An algorithm for path connections and its applications. IRE Trans Electron Comput 1961; (3): 346-365.
14. Permana SH, Bintoro KY, Arifitama B, Syahputra A. Comparative analysis of pathfinding algorithms a*, dijkstra, and bfs on maze runner game. Int J Inf Syst Technol 2018; 1(2): 1.
15. Hopcroft J, Tarjan R. Algorithm 447: efficient algorithms for graph manipulation. Commun ACM 1973; 16(6): 372-378.
16. Awerbuch B. A new distributed depth-first-search algorithm. Inf Process Lett 1985; 20(3): 147-150.
17. Dijkstra EW. A note on two problems in connexion with graphs. Edsger Wybe Dijkstra: his life, work, and legacy. 2022; pp. 287-290.
18. Fredman ML, Tarjan RE. Fibonacci heaps and their uses in improved network optimization algorithms. J ACM 1987; 34(3): 596-615.
19. Johnson DB. Efficient algorithms for shortest paths in sparse networks. J ACM 1977; 24(1): 1-13.
20. Burtsev S, Kuzmin YP. An efficient flood-filling algorithm. Comput Graph 1993; 17(5): 549-561.
21. Kumar B, Tiwari UK, Kumar S, Tomer V, Kalra J. Comparison and performance evaluation of boundary fill and flood fill algorithm. Int J Innov Technol Explor Eng 2020; 8(12): 9-13.
22. Abu-Khzam FN, Langston MA, Mouawad AE, Nolan CP. A hybrid graph representation for recursive backtracking algorithms. In: Int Workshop Front Algorithmics. Springer 2010.
23. Lim TH, Ng PL. Evaluating recursive backtracking depth-first search algorithm in unknown search space for self-learning path finding robot. In: Springer Artif Intell Commun Netw: Second EAI International Conference; 19-20 December 2020. pp. 531-543.
24. Cherroun L, Boumehraz M. Path following behavior for an autonomous mobile robot using neuro-fuzzy controller. Int J Syst Assur Eng Manage 2014; (5): 352-360.
25. Yadav S, Verma KK, Mahanta S. The Maze problem solved by Micro mouse. I Int J Eng Adv Technol 2012; 2249: 8958.
26. Dehghani M, Hubálovský Š, Trojovský P. Cat and mouse based optimizer: A new nature-inspired optimization algorithm. Sensors 2021; 21(15): 5214.
27. Wang H, Lou S, Jing J, Wang Y, Liu W, Liu T. The EBS-A* algorithm: An improved A* algorithm for path planning. PloS ONE 2022; 17(2): e0263841.
28. Buluç, A, Madduri K. Parallel breadth-first search on distributed memory systems. In: Proc Int Conf High Perform Comput Netw Storage Anal 2011.
29. Sangamesvarappa V. Parallelizing Depth-First Search for Pathway Finding: A Comprehensive Investigation. Rev Intell Artif 2023; 37(4).
30. Aviram N, Shavitt Y. Optimizing Dijkstra for real-world performance. arXiv preprint arXiv:1505.05033, 2015.
31. Abu-Khzam FN, Daudjee K, Mouawad AE, Nishimura N. An easy-to-use scalable framework for parallel recursive backtracking. arXiv preprint arXiv:1312.7626, 2013.
32. Xie S, Wu P, Liu H, Yan P, Li X, Luo J, Li Q. A novel method of unmanned surface vehicle autonomous cruise. Ind Robot Int J 2016; 43(1): 121-130.
33. Mahmud MS, Sarker U, Islam MM, Sarwar H. A greedy approach in path selection for DFS based maze-map discovery algorithm for an autonomous robot. In: IEEE 15th Int Conf Comput Inf Technol 2012.
34. Foltin M. Automated maze generation and human interaction. Brno: Masaryk Univ Fac Inform 2011.
35. Pame YG, Kottawar VG, Mahajan YV. A Novel Approach to Maze Solving Algorithm. IEEE Int Conf Emerg Smart Comput Inform 2023.
36. Iloh PC. A Comprehensive and comparative study of DFS, BFS, and A* search algorithms in a solving the maze transversal problem. Int J Soc Sci Sci Stud 2022; 2(2): 482-490.
37. Sturtevant NR. Benchmarks for grid-based pathfinding. IEEE Trans Comput Intell AI Games 2012; 4(2): 144-148.
38. Li K. Maze solving robot based on graph algorithm. in AIP Conf Proc. AIP Publishing 2024.
39. Wang H, Yu Y, Yuan Q. Application of Dijkstra algorithm in robot path-planning. IEEE Second Int Conf Mechan Autom Control Eng 2011.
40. Kalisiak M, van de Panne M. RRT-blossom: RRT with a local flood-fill behavior. In: Proc IEEE Int Conf Robot Autom 2006.
41. Kondrak G, Van Beek P. A theoretical evaluation of selected backtracking algorithms. Artif Intell 1997; 89(1-2): 365-387.
42. Niemczyk, R, Zawiślak S. Review of maze solving algorithms for 2d maze and their visualisation. In: Springer Int Conf Students PhD Young Sci Eng XXI Century 2018.