Let's Make Robots!

How To Maze Solve


UPDATE 07.27.11

I have written a maze solving simulator and embedded it online. It allows users to build a maze and have a virtual robot solve it using the left hand on the wall technique. You can then run the optimized path as well.

Watch the video to see how to operate it, but here is an outline:

  • Choose your speed by clicking in the rectangle below the label "Robot Speed". This speed is how many squares the robot will move in a second. 
  • left click on the grid to draw a maze
  • right click on a black square to make it the starting square of the maze
  • right click on an empty, grey square to make it the finishing square of the maze
  • hit "solve" to have the robot run through the maze using the left hand on the wall technique
  • after that is done, you can click "display optimized path" to have the robot run the optimized path
  • you can click restart to restart the simulation from scratch

Dont do:

  • best to see the video for this

 

Hope this is fun or educational. You should be able to download the code there if you want.

 

 


 

Well you can say I have been at maze solving for a while and just now successfully accomplished it. I am going to try and share with you what I did.

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 tutorial 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 oppurtunity to turn. If the robot comes across an oppurtunity 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 lets apply this method to a simple maze and see if you can follow it. 

The red circle will be the robot. 

 Path = L

Path = LB

Path = LBL

Path = LBLL

Path = LBLLB

Path = LBLLBS

The final path = LBLLBSR

I hope you were able to see how those moves are made using the left hand on the wall technique. 

This can be applied to any non-looping maze. 

 

 

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. 

Path = S

Path = SR

Final 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. 

Lets look at the first 3 moves in the path. These moves are "LBL". 

That move looks like this:

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). 

 

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

 

 

Some other things you may need to know when maze solving:

I ran into some trouble programming my robot because I used an array of sensors in a single line. The problem with this is that different intersections may look alike. So my robot goes forward a bit every time it detects an intersection so it can see what is after that intersection. The prime example is when there is a right turn. If you can go straight instead of turning right then you should, but the only way to know if you can go straight is to drive forward and see if the line continues on. 

You will also need a function that drives the robot in a relatively straight line. So it needs to do some line following also. That is why a maze robot generally has 4, 5, or 6 sensors. 

I used some other techniques for completing turns with out encoders, but this is getting too far away from maze solving and more into general practice. To cut it short, you will need some really good programming to keep your robot on the line well enough to read the sensors correctly and to correctly identify intersections. I hope this guide gets you started at least. 

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

HEy great tutorial, and very interesting simulator. Thanks again EZ

i found these links and i think they may be useful

http://www.astrolog.org/labyrnth/algrithm.htm#solve

http://www.astrolog.org/labyrnth/daedalus.htm

this software is about maze solving and it has too many features

A little update on the Maze Solving Simulator. To fix the issue of drawing on the edges I have simply not allowed the user to draw on the edges. 

You can also do click and drag to draw a maze. Saves your hand from a lot of clicking.

... because it doesn't

But it is still pretty cool

No it isn't. I have yet to find a good one that does without knowing a little something about the maze before hand.

to an already great tutorial.

Good tutorial Patrick. Clear and easy to understand. A similar method is used to simplify circuits using logic gates.

Hi Patrick, studying your code,I'm trying to figure out where is the  "inch" routine located in the code. Can you give me a hint?

I guess it is not a real function but is in the code. The digital writes in the leftHandWall function are what makes the robot inch forward. These I believe were 140 or 150 milliseconds long (I have changed them since to 170). There is also a 30 second one which will move the robot a hair forward so all the sensors are on the intersection. I had to add this because some times the right sensor was detecting the "T" or "4 way" intersection before the left one was able to read the intersection. This led to right turns when the robot should go left.

 

 

 

Thanks Patrick, it's the void leftHandWall() I guess. Ok then I don't want to bother and I will try to figure out. It's only for curiousity purpose. I realy admire your talent, keep up the good work my friend and thanks again. :)