The Autonomous Maze Solver

Search this site

763days since
Project Due Date

Tools

Project Overview


Introduction

Contents

  1. 1 Introduction
  2. 2 System Overview
    1. 2.1 Maze Solving Algorithm
    2. 2.2 Servo Controller
  3. 3 Results

    Our project is what the site title says, "The Autonomous Maze Solver."  What this means is that we are building a maze with a brain.  Our goal is to create a maze that can autonomously solve itself.
    More specifically, the maze we are building is a wood platform with wood peg and cardboard maze inner walls and wood outer walls.  This platform is mounted on top of 2 motors that can tilt the platform in 1 of 4 directions.  There is also a camera mounted high above the platform that takes pictures of the maze and sends them to a PC computer. 



    On the PC, image processing software determines the location of the walls and uses them to solve the maze given a start and stop location on the maze that are programmed in.  The maze is solved for every location the ball can be in on the maze.  The directions for how the balls should move are then sent to an 8051 micro-controller that tells the motors how to move to navigate the ball through the maze.
    In addition, on the PC, there is also a GUI that shows the user a current picture of the maze and draws the path the ball has taken on top of the maze.  There is also a GUI launcher application that gives the user several options for customizing execution of the maze solver.

System Overview

See the FDR presentation on the presentations page.

Maze Solving Algorithm

    The maze solving algorithm is based on a tree search algorithm using Breadth First as the search strategy.  More specifically, the search will search the entire maze and build a tree of all of the empty squares in the maze as nodes.  The search is maintained as a tree rather than a graph, by keeping track of explored squares.  The depth of the tree is also tracked and used to generate paths, which are stored on the maze in memory that move back towards the top of the tree, thus giving the optimal path from any location in the maze.  This solution is calculated before the maze starts moving and thus during run-time the navigation only needs to know the location of the ball, and it can look up the solution.

Servo Controller

We used an 8051 microcontroller to send PWM signals to the servos.

We also defined and implemented an application layer protocol which we used to communicate between the PC and the microcontroller.

More details can be found in the FDR presentation on the presentations page.

Results


On project expo night we put the AMS to the test... The verdict? The AMS outperformed every contestant, including Dr. Wheeler!



The AMS