A Novel Approach to Maze Solving Algorithm

摘要

This research aims to address the maze discovery issue of an autonomous micro-mouse bot in an unknown maze. In this paper, An algorithm is proposed to search for unknown mazes and find the shortest path. The maze considered here is built according to the IEEE standards. To map the maze, we use a 2-Dimensional matrix to mark the visited and unvisited squares of the maze and a 2-Dimensional list is used to store the path travelled by the bot and a variable is defined which stores the current location of the bot with respect to the maze and the matrix. Our task is to discover the maze and then find the shortest distance to reach the target square in the maze. Every movement of the micro-mouse is stored in a list and this list is converted to a graph-like structure on which we apply a variant of the Breadth-first Search Algorithm to get the shortest path. But the proposed algorithm is also flexible to use other algorithms such as Depth-first search or A*. This paper presents an easy approach to the IEEE standard robot maze-solving algorithm.