The Capabilities of Various Search Algorithms and Design of a Micromouse Robot

Abstract

This thesis compares the performance of four maze-solving algorithms—A*, Dijkstra’s, Flood Fill, and Recursive Depth-First Search (DFS)—for a micromouse robot. The goal of this research is to analyze the efficiencies of the four algorithms to determine which one can complete a random maze within the shortest amount of time, on average, over a set of trials. These tests were conducted with the aid of both digital simulations and physical time trials. The digital trials offer rapid testing for randomized mazes while the physical trials can assess real-world performance measures. Along with the assessment of the maze-solving algorithms, this thesis will also document the design and construction of the physical mouse following along with the specifications of the National Robotics Competition. By analyzing the results from this study, a better understanding can be gained on autonomous robot navigation and contribute toward the future pathfinding strategies of autonomous systems.