Course:
Autonomous Car: Maze Solving Algorithms

Have you ever solved a maze before?

Try working out this one now:

How did you do that?  

Do you know the set of steps you took?  Maybe you went down a path in your mind before you started, or maybe you just figured it out as you wrote it down!  

In the next section we will look at some of the algorithms robots like the RobotLAB Autonomous car use to get through a maze.

As you may have guessed, in this lesson we will build a maze and program the RobotLAB Autonomous car to solve it.

Here are some example mazes so you can get some ideas:

In order for your maze to work, it needs to be big enough for the robot to move around inside it.  Here’s how to make sure the car has enough space:

Take a large sheet of paper, and place the car on it.

Make sure the car is turned off, then turn the front wheels to the left as far as they will comfortably go.

Try pushing the car along with your hand.  You will see the car turn as sharply as it can.  

Hold a pen in your hand as you turn the car.  

Now you have captured how the car turns.  

Do the same on the other side.  (For my measurement, I put the pen right behind the front wheel)

Your maze will probably be sharp rather than curved, so it will be easier to make your template with sharp edges.  

An easy way to do that is to draw straight lines from the outer edges of the upper curve, and from the center of the inner curve.

The box your car came in is a good reference for how wide your path should be.

You may want to widen the part after the turn to match.

Finally, you can cut your template out and use it to draw a maze!

Remember to keep your maze simple.

There are many maze solving algorithms, and different ones work better for different robots.  Here are four of the most common ones.

Random mouse

1.  Go down a path.
2. When you reach a place where you have to turn, pick a path at random and go that way.

This algorithm can take a very long time, but it requires very little memory.  It usually works, but it is possible that this algorithm will never stop, and the mouse will never reach the end.

Here are some examples of what could happen when using the Random Mouse algorithm:

Wall Follower 

1. Choose a random starting direction.
2. At each intersection, take the right turn. At dead-ends, turn around.

This algorithm will work faster than the random mouse, but it can get stuck!

Here are some examples of what could happen when using the Wall Follower algorithm:
         

Tremaux’s algorithm

1. Pick a direction, draw a line behind you to mark where you have been.
2. When you reach a place where you have to turn and you haven't visited it before, pick a new passage at random.
3. When you hit a dead end, turn around and go back the way you came.
4. If you encounter a place you have marked once, go back the way you came (and mark your path a second time).

All passages will either be empty (haven't visited yet), marked once (gone down it exactly once), or marked twice, (gone down it and backtracked). Paths marked once will indicate a direct way back to the start.

In the last module you learned about 3 popular maze solving algorithms.  They all have their merits, but which one is the best for our purposes?  Take a look at the first two:

Random mouse

1. Go down a path.
2. When you reach a junction, pick a path at random and go that way.

Here is an example of that algorithm using Scratch:

Wall follower (can be left or right-hand)

1. Choose a random starting direction.
2. At each intersection, take the rightmost turn. At dead-ends, turn around.

Here is an example of that algorithm using Scratch:

Here is an example of that algorithm using C:

The Random Mouse is very simple, but there is a chance that it will not solve the maze.  The Wall Follower is a little harder to do, but it works much better.


Try turning the Wall Follower algorithm into an algorithm for your car! Here are some code snippets to get you started: