A Comprehensive and Comparative Study of Maze-Solving Techniques by Implementing Graph Theory

Solving a 3-D square maze through an autonomous robot is gaining immense popularity among the robotics aspirants. IEEE has established a set of rule for this and launched a competition named “Micromouse” where an autonomous robot or mice solves an unknown maze. Without deploying Artificial Intelligence technique it's not possible to do this task efficiently. Several algorithms which originate from graph theory (GT) and non graph theory (NGT) are currently being used to program the robot or mice. In this paper we have elucidated how graph theory can be used to solve mazes. With adequate investigation it is verified how graph theory dominates over non graph theory algorithms. The process of generating maze solving algorithm from graph theory is also explained. To compare the algorithms efficiency, they are simulated artificially and a comprehensive study is done by interpreting the statistics of interest. The simulation results lead us towards a conclusion about the nature, behavior and efficiency of these algorithms. Upon considering all the regulating factors which can alter the performance of an algorithm, some proposals have been drawn. It will be helpful to any micro mouse aspirant while choosing an algorithm to design the robot.