Maze Solver
Python, Motion Planning
Overview
This is my implementation of the Wavefront Planner maze solving algorithm. Here, an Agent is manually moved around an M x N grid maze, and at any point can summon the Oracle to show them the path to the goal. Further, the entire interface is in a terminal and the walls of the maze are rendered off a bitmap, with unicode.
Personal Motivation
I completed this project during Northwestern’s MS in Robotics Hackathon. In a span of two weeks, we undertook various projects involving Randomly-exploring Random Trees (RRTs), computer vision, manipulation, path planning, and shell scripting in an extremely fun, gamified environment.
Wavefront Planner
A wavefront planner is a breadth-first technique for finding paths in a maze. It provides the shortest path from any starting location to a given goal. It also requires full knowledge of the maze.
-
SETUP
Fig. 1. The Goal is the red square. The robot starts at the green square and knows the full layout of the maze. [Image Source] -
FIRST STEP
Fig. 2. Start at the goal. It is 0 squares from the goal so label it 0. [Image Source] -
FIRST EXPANSION
Fig. 3. All the neighbors of the goal are a distance of 1 from the goal. (In this example the robot cannot move diagonally). [Source: Ref 1]. [Image Source] -
NEXT EXPANSION
Fig. 4. All the neighbors of the 1-distance squares are a distance of 2 from the goal. [Source: Ref 1]. [Image Source] -
SUBSEQUENT EXPANSIONS
Fig. 5. Keep expanding until every square is labeled with its distance from the goal. [Source: Ref 1]. [Image Source] -
USING THE PLAN
Fig. 6. Starting at any square (say the green one) the robot moves to the neighbor that is closest to the goal. [Source: Ref 1]. [Image Source]
Conclusion
This project fulfills its intended goal in a very pretty manner. The reason I have a separate post for this relatively short project is largely because it looks asthetically pleasing.
References