Efficient Pathfinding in a Maze to overcome Challenges in Robotics and AI Using Breadth-First Search
Breadth-First Search; Dijkstras; Pathfinding; Robotic Applications; Unweighted Graphs
Efficient pathfinding in a maze is a key obstacle in robotics, computer science, and artificial intelligence. The article is proposing a strategy using the Breadth-First Search (BFS) algorithm to establish the shortest path for a robot navigating from the top-left to the bottom-right corner of a maze depicted as a two-dimensional grid. The maze comprises open pathways and obstructions, signified by 0 and 1, respectively. The robot's permissible actions include up, down, left, and right, restricted by the boundaries of the grid and the position of obstacles. BFS, an approach well-suited for unweighted graphs, sequentially examines all available routes, ensuring that the first observed path to the goal is the shortest. A visited set removes redundant cell visits, reducing infinite loops and inefficient processing. The algorithm's efficiency is dramatically upgraded by harnessing a queue structure to maintain live routes and their associated steps. This approach assures effectiveness and extensiveness for grid-based navigation problems, making it especially appropriate for real-world robotic applications where minimizing traversal cost is critical. Additionally, the paper discusses the algorithm's execution, complexities, and potential upgrades for larger grids or dynamic environments. Experimental results demonstrate BFS's resilience and efficacy in solving pathfinding challenges in various maze configurations. This work contributes to developing stable navigation techniques, integral to advancing autonomous robotic navigation and related fields. 2025 IEEE.
Biju, Abiya; Gayathri, M.P.; Jayapandian, N.; Chris, Alan; Thaleeparambil, Noeal Rajeev
2025 IEEE 14th International Conference on Communication Systems and Network Technologies, CSNT 2025;pp.727-732
Institute of Electrical and Electronics Engineers Inc.
Restricted Access; Hardcopy may be available in the library
https://doi.org/10.1109/CSNT64827.2025.10968383 https://www.scopus.com/pages/publications/105004548317?origin=resultslist
Biju A., Department of CSE, Christ University, Kengeri Campus, Bangalore, India; Gayathri M.P., Department of CSE, Christ University, Kengeri Campus, Bangalore, India; Jayapandian N., Department of CSE, Christ University, Kengeri Campus, Bangalore, India; Chris A., Department of Computer Science and Engineering, Christ University, Kengeri Campus, Bangalore, India; Thaleeparambil N.R., Department of Computer Science and Engineering, Christ University, Kengeri Campus, Bangalore, India