FNUG: Imperfect Mazes Traversal Based on Detecting and Following the Nearest-to-Final-Goal and Unvisited Gaps

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 letter proposes 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 the robot’s unvisited-neighbor gap for navigation based on its Euclidean distance from the final target location. Finally Dijkstra’s algorithm is used to find a path from robot’s location to the sub goal. 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 in this algorithm that prevents the robot from falling into a dead end or trapped in a loop. To prove the effectiveness of this algorithm, simulations and physical experiments were performed using using a 2-wheeled differential mobile robot.