The Minotaur of the Labyrinth

Overview

Objectives/Goals The objective of this project is to find the most efficient maze solving algorithm among Random Mouse Algorithm, Right Side Rule Algorithm, and Tremaux#s Algorithm for a variety of endpoints on a maze with a fixed design. The hypotheses state that Random Mouse Algorithm will never solve the maze, Right Side Rule Algorithm will always lead the maze runner to the endpoint of the maze, and Tremaux#s Algorithm will take the most time to complete the maze. Methods/Materials For this project, a LEGO Mindstorms NXT robot is the maze runner, a thick mat is the base for the maze, and Styrofoam sheets are the walls. A laptop with the Mindstorms NXT GUI programming interface installed on it is used to program the different algorithms for the robot. Green and red sheet of paper is used to mark the entrance/starting point and the exit/endpoint respectively. Results On average, Tremaux#s Algorithm took the shortest time to traverse the maze. Right Side Rule was 35% slower and Random Mouse Algorithm was 40% slower compared to Tremaux#s Algorithm. Right Side Rule Algorithm took the least time when the endpoint was towards the right side of the maze. Maze solving time for Random Mouse Algorithm varied significantly over the many trials. Conclusions/Discussion The results did not support all hypotheses. The hypothesis that Right Side Rule Algorithm would always solve the maze was correct, but the hypothesis that Tremaux#s Algorithm would take the longest time to solve the maze was incorrect and the one that Random Mouse would never solve the maze was also incorrect. This project attained the objective of finding the most efficient maze solving algorithm which turned out to be Tremaux#s Algorithm. Earlier, in the history of mazes, people used these algorithms to solve a maze not knowing which algorithm was most efficient for their situation. This project has provided useful insights in the quest for such maze solving situations. The knowledge gained from this project could be applied to search and rescue missions where engineers could design a robot to traverse maze-like structures in inhospitable circumstances.

Competition history

• CSEF 2014 Mathematics & Software · Entry J1414

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2014 project