Efficient Pathfinding in a Maze to overcome Challenges in Robotics and AI Using Breadth-First Search
subject: Breadth-First Search; Dijkstras; Pathfinding; Robotic Applications; Unweighted Graphs
description: 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.
creator: Biju, Abiya; Gayathri, M.P.; Jayapandian, N.; Chris, Alan; Thaleeparambil, Noeal Rajeev
source: 2025 IEEE 14th International Conference on Communication Systems and Network Technologies, CSNT 2025;pp.727-732
publisher: Institute of Electrical and Electronics Engineers Inc.
date: 01-01-2025
rights: Restricted Access; Hardcopy may be available in the library
relation: ISBN: 979-833153193-5;
language: English
type: Conference paper
coverage: 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