Maze Solving Robot




In this instructable I will be showing you how to build a maze solving robot. This is actually my 3rd attempt at making one. The first was a complete failure. The second was alright at finding the end of the maze, but it could not go back and drive the quickest path. This is my current and 3rd one. It is able to find the end of the maze and then, when put back at the start, drive the shortest path to the end of the maze without going down any dead ends. What surprises me is that it really does not mess up.

This was just a short introduction, everything else from theory, building, and programming will be explained in later steps.

Parts list:

General Parts:

  • 3 1in Spacers (Home Depot)
  • Bolts and nuts that fit the spacers (Home Depot)
  • Hook up wire (I use 22 gauge)
  • Solder
  • .100″ Female and Male headers
  • Velcro

Tools:

  • Soldering Iron
  • Philips Screw driver
  • Wire Strippers
  • Something to cut the wire with
Maze Solving Robot




Step 1: The Theory Part 1

What are the steps In maze solving?
There are basically 2 steps. The first is to drive through the maze and find the end of it. The second is to optimize that path so your robot can travel back through the maze, but do it perfectly with out going down any dead ends.

How does the robot find the end of the maze?
I use a technique called the left hand on the wall. Imagine you are in a maze and you keep your left hand on a the edge of the wall at all times. Doing this would eventually get you out of a non-looping maze. This instructable will only deal with mazes that do not loop back on themselves.

This left hand on wall algorithm can be simplified into these simple conditions:
– If you can turn left then go ahead and turn left,
– else if you can continue driving straight then drive straight,
– else if you can turn right then turn right.
– If you are at a dead end then turn around.

The robot has to make these decisions when at an intersection. An intersection is any point on the maze where you have the opportunity to turn. If the robot comes across an opportunity to turn and does not turn then this is consider going straight. Each move taken at an intersection or when turning around has to be stored.

L = left turn
R= right turn
S= going straight past a turn
B= turning around

So let us apply this method to a simple maze and see if you can follow it. View the photos to see this method in action.
The red circle will be the robot.

As you can see in the photos for this example, the final path is LBLLBSR.

Step 2: The Theory Part 2

Ok so now you have a path. In this case it is “LBLLBSR”, but how does the robot change that into the correct path? Well lets take a look at what the correct path would be. Look at the photos for the correct path.

Final correct path = SRR

So we need our path to go from LBLLBSR to the right path that is SRR. To start off we look at where we went wrong. A “B” indicates the robot turned around meaning it went down the wrong path. To optimize the path we have to get rid of the “B” by using some substitution.

Step 3: The Theory Part 3

Lets look at the first 3 moves in the path “LBLLBSR”. These moves are “LBL”.
That move looks like the photo.

Instead of turning left then turning around and turning left again, the robot should have gone straight. So we can say that LBL = S.

This substitution is what the robot uses to optimize the path. That is one example but here is the whole list:

LBR = B
LBS = R
RBL = B
SBL = R
SBS = B
LBL = S

You may not come across all of these when maze solving, but they are required when optimizing the path. Some even put “B” back into the path. This is required to further optimize the path correctly. You can figure out why for yourself or just trust me.

Lets optimize our path now that we know how to:
Path = LBLLBSR
LBL = S so our new path would be: SLBSR
We also know LBS = R so our new path would be: SRR
As you can see we got the path that we were looking for.

My robot optimizes the path as it travels. The path is stored in an array and every time it goes to store a new move, it checks to see if the previous move was a “B”, if it was then it optimizes the path. You need to know at least 3 moves to optimize the path: The move before and after the turn around (and the turn around itself).

Step 4: The Theory Part 4

Here is another example.

Using the left hand on the wall algorithm, here is the path the robot would take:
LLLBLLLRBLLBSRSRS

Now here is the process of shortening that path:
LL(LBL = S)LL(RBL = B)(LBS = R)RSRS

The new path would be:
LLSLLBRRSRS

Continue shortening it until all the “B”s are gone:
LLSL(LBR = B)RSRS

The new path would be:
LLSLBRSRS

Continue shortening it:
LLS(LBR = B)SRS

The new path would be:
LLSBSRS

Continue shortening it:
LL(SBS = B)RS

The new path would be:
LLBRS

Continue shortening it:
L(LBR = B)S

The new path would be:
LBS

The final path is:

LBS = R

Step 5: The Design

Maze Solving Robot schematic
I first want to say that your robot does not have to built in the same manner mine is. The biggest thing I see is that I designed and laser cut a chassis for my robot. I will post the AutoCAD file, but this is about all I can do. So if you are not able to laser cut the design, do not worry. As long as you have some Arduino, the same sensors, and motors then you should be able to get my code to work on your robot with minor changes. Recently I was just helping some one online who made a copy of mine without laser cut parts. The code ran on his robot with little tweaking.

You can see in the photos the design I made and the parts I used a laser cutter to make. The parts are made from acrylic that is .08″ thick. This can be found at The Home Depot.

In the third photo you can see the bottom deck in my 2 deck chassis design. The bottom deck has mounting holes in the rear to bolt the motors on, holes in the front to bolt the ball caster on, a hole to bolt the Arduino on, and 2 tabs in the front where the sensor bolts onto. The bottom deck also has 3 mounting holes that allow it to be connected to the top deck using bolts and spacers.

The top deck has a single, large hole to run wires from the battery pack that is velcroed on top to the electronics on the bottom deck. It also has 3 holes that allow it to be connected to the bottom deck.

It is a simple, compact design that allows for a simple assembly with minimal wiring.

You will see in the next steps how and where the parts fit on.

Step 6: Attaching The Motors

In this step I simply attached my motors to the top side of the bottom deck using 2 #2 bolts for each one. You can see that I have a little bit of wire attached to each motor, this is because the motors were removed from my previous maze robot. Then attach the wheels by simply pressing them onto the motor shaft. You have to line the “D” shaped shaft up with hole in the center of the wheel.
For more detail: Maze Solving Robot




This Post / Project can also be found using search terms:

  • maze solving robot using arduino uno
  • how to make a maze solving robot using arduino
  • maze solving algorithm arduino
  • maze solving robot arduino code
Clip to Evernote

Leave a Comment

(Spamcheck Enabled)

Read previous post:
USB Mouse Made Out Of A Wii Nunchuck
USB Mouse Made Out Of A Wii Nunchuck

This instructable will describe how to convert a Nintendo Wii Nunchuck controller into a USB 2-button mouse using a Teensy...

Close
Scroll to top