LAUSR

Mazes traversal techniques are broadly classified into model-based and sensor information-based. In model-based techniques the configuration space is explicitly modeled in the form of a grid, potential field or a connectivity graph, while in sensor information-based all control decisions are based on processing the current sensor's data. A maze with no pre-model available is called unknown maze, while an imperfect maze is the one which has loops or closed circuits. Most of the traditional information-based unknown-maze traversal techniques are based on trial and error, which are time-consuming and may trap the robot in infinite loops or dead ends. To address the above issues, this paper proposed a gap-based approach for imperfect unknown mazes traversal named Follow the Nearest-to-final goal and Unvisited Gap (FNUG) for the first time. The algorithm is computationally efficient, and has the ability to deal with loops and dead ends through the revisit check. The main part of this approach is finding out gaps around the robot by analyzing the depth scans, building a coordinate system based topological map in the form of a tree. Then a heuristic selection of robot's unvisited-neighbor gap for navigation based on its Euclidean distance with the final target location. Compared to existing sensor information-based methods, our proposed algorithm not only takes into account the current sensor data, the shape and size of the robot, but also all the sub goals visited so far. This is the key factor of our algorithm that prevents the robot from falling into a dead end or trapping in a loop. To prove the effectiveness of this algorithm, simulations and physical experiments were performed using using a 2-wheeled differential mobile robot.