Maze Solving Robot
In this tutorial, I’ll show you how to build a maze solving robot, step by step. In case you don’t know what maze solving robot is, it is an autonomous mobile robot that is able to navigate inside a maze and has the intelligence to find the exit of the maze. In a line maze contest, robots travel as quickly as possible along the lines from a designated start to the goal, keeping track of the intersections that they pass along the way. Robots are given several chances to run the maze, so that they can follow the fastest possible path after learning about all of the dead ends.
If you already did the line following robot then you already know a lot. We will use that robot (so we’ll omit ckt diagram) and just change the code a little bit.
How maze solving is done:
One of the most common methods for solving a maze is called the wall follower rule which can use the right-hand rule or the left-hand rule. Put one hand on the wall inside the maze and start walking. If the maze is simply connected and has no loops, then you will always get to the end of the maze. See this Wikipedia page for a more detailed explanation of maze solving algorithms.
Suppose you are in a maze with a number of hallways. There are many dead ends and you can't see beyond the next corner. If the maze has no islands, or areas in the maze that are not connected to any of the walls in your vicinity, then the left-hand rule will always get you to the end of the maze. Do this...
- Place your left hand on the wall.
- Begin walking forward
- At every intersection, and throughout the maze, keeps your left hand touching the wall on your left.
- Eventually, you will reach the end of the maze. You will probably not go the shortest and most direct way, but you will get there.
Some example of the mazes:
In order to solve the maze, the robot needs to traverse the maze twice.
- In the first run, it goes down some number of dead-ends, but records these as “bad” paths so that they can be avoided on the second run.
- Next, bot will follow the correct line.
So there will be two infinity loop in main function. 1st one helps the robot explore whole maze including wrong turns, dead ends. Then it will memorize those. Next time when it starts again from the beginning it won’t do any wrong moves i.e. it will reach the end faster.
But there is lot to discuss. This robot follows like a Line Following Robot but it will take account for intersections. That is the most important thing.
The first step for me was to put myself in the robot's place. I did this by picturing myself walking around a room with only a black line below me, and only the ability to look straight down through a limited rectangle. From this viewpoint, in the maze below, there are only eight possibilities, or eight ways the robot can come up on an intersection.
So the task becomes "How do I develop a set of behaviors so the robot reacts correctly at each intersection?"
The Five Sensors
Since the robot will have five sensors (from line following), we next need to establish how they work and how I can develop the algorithm for the eight possibilities above. We also need to be talking about the same thing in the descriptions below.
As you know from line following robot, a one indicates that this sensor senses black just below it and a zero means that the sensor senses or "sees" white just below it.
Using this logic, here are a few combinations of patterns for this robot only:
11100 / 11000 = Robot gotten to a left hand turn (or Straight above and Left)
00111 / 00011 = Robot gotten to a right hand turn (or Straight above and Right)
11111 / 01110 = Robot is at a T intersection, 4-way, or the end of the maze.
Notice that several of these combinations have more than one possibility!! For example, when I get to a T intersection, all of my sensors see black. When I get to a "Four-Way" intersection all of my sensors see black. When I get to the end of the maze, all of my sensors see black. So, I will need a way to differentiate between these three so I can select the correct behavior.
So, the first steps in the programming algorithm seem to be deciding how to handle these eight possible intersections above.
1) Dead End
The easiest of the eight above is the dead end. Notice that this is the only time in the maze that the robot sensors will all be zeros:
0 0 0 0 0 = No black line; must have run off the line at dead end.
In this case, the behavior is simple; Do a 180 degree turn and go back the way you came.
2) Right only / Straight or Right
Right only and Straight or Right intersections both present the same pattern initially.
0 0 1 1 1 / 0 0 0 1 1
How do we find out which??? All you have to do is move the robot forward for 1-2 seconds. This will guarantee that the robot has passed over the line i.e. cross the 00111. What will the sensors see when robot past the intersection? There are only two choices. Either the robot will see all zeros (0 0 0 0 0) if it is the Right Turn Only, and something else if it just encountered a Straight or Right intersection. So the pseudo code for these two intersections is:
If pattern = "00111" then
Go forward for 1-2 sec
pattern = readSensors()
if pattern = "00000" then
go right turn
3) Straight or Left and Left Turn Only
Left only and Straight or Left intersections both present the same pattern initially.
1 1 1 0 0 / 1 1 0 0 0
How do we find out which intersection this is??? Once again, we go forward for 1-2 seconds and now the robot sees either all zeros for Left Only and something else if it is the left or Straight intersection. Because this is a left-hand rule robot, the robot ALWAYS prefers a left turn in a Straight or Left situation, so the pattern 1 1 1 0 0 will always trigger a left turn. So no need to tense. Whenever this comes just turn left. If this was a right-hand rule robot, we would develop pseudo code similar to that above to decide what to do.
4) "T" Intersection, 4-Way or End of Maze
All three of these show an all ones pattern:
- Left or Right "T"
- Four Way
- End of Maze
...will all detect 1 1 1 1 1 initially.
Now, after go forward, there are three possibilities:
1 1 1 1 1 = End of Maze = STOP
0 0 0 0 0 = T Intersection, go left
0 0 1 0 0 = Four-Way = go left
Following the Line
The robot, most of the time, will be involved in one of the following behaviors:
- Following the line, looking for the next intersection.
- At an intersection, deciding what type of intersection it is.
- At an intersection, making a turn.
These steps continue looping over and over until the robot senses the end of the maze. As the robot actually spends most of its time following the line between intersections, that is cover in the line following robot. To see the patterns that develops while the robot is following the line, are:
Any robot that hopes to solve a maze must somehow keep track of where it has been and then perform some algorithm to decide on how to eliminate travel down unproductive pathways. This section talks about how to store, and later modify all of the turns made while traversing the maze.
Let's start with a simple maze and some definitions so we are speaking the same language. Here is a simple maze. The robot is at the start and is required to find the "End of Maze".
First, we will traverse the maze in English, then transform our English words to an abbreviated code that will be easy to store.
Left-Hand Rule and Right-Hand Rule Defined
Mazes of this type are best solved by using either the left or right-hand rule. We will do the LEFT HAND RULE. Look at the black lines in the maze above and pretend you are a very teeny-tiny person and the black line represents a passageway that is walled in. First, you place your left hand on the wall at the starting point. Then you start walking, keeping your left hand touching the wall to your left. Whenever you reach an intersection, keep your hand on the wall and make the turn. With this algorithm, here is your path through the maze above.
- Walk down the first path to Intersection A, and go Straight.
- Walk to the end of the path at Dead-End B. Keeping your left hand on the wall forces you to do a U-Turn.
- Return to Intersection A and go Left.
- Continue to Intersection C and go Left.
- Take a mandatory Right turn towards Dead-End D
- At dead-end D, make a U-Turn
- Return to Intersection C and turn Left.
- Continue to dead-end E and make a U-Turn.
- Return again to Intersection C and go Left.
- Make a mandatory Left turn and go towards Intersection F.
- Continue to Intersection F and go Left.
- Reach the end of the maze at H.
Notice that Dead-End G is never reached using the left hand rule.
Compress the path
Now, most microprocessors have extremely limited memory, so storing the actions using words or phrases like "Go Left", "Go Straight" take up too much storage. Since there are only four possible actions, and they all start with a different letter, lets reduce the actions to:
- L = Left Turn
- R = Right Turn
- U = U-Turn
- S = Go Straight
The entire trip described above can be reduced to this string:
Now, if you look at the maze, you can deduce that the "correct" path to complete the maze in the shortest time is: RRLL, so somehow, after (or during) the first trip through the maze, the sequence of turns needs to be converted from SULLRULLULLL to RRLL. That algorithm is explained in great detail in next point.
Developing the algorithm
Fig-2: The robot takes off! At the first intersection, the robot senses a “Straight or Right” intersection. The left hand rule requires that the robot go straight.
Fig-3: The robot continues straight and stores the turn taken “S” in memory.
Fig-4: The robot runs off the path (Pattern = “00000”) & the correct behavior by take a U-Turn. After the U-Turn, record the turn taken “U” in memory.
Let’s stop here for a moment and discuss an important point…
In this maze, every dead-end encountered means that the robot has taken a wrong turn! The best/shortest path through it never includes going down a dead-end path. So a dead-end can always be said to tell us: The previous action/turn was not correct and needs to be changed. We can’t be sure how we got here or the correct way to modify the previous turn until we return to the previous intersection. Let’s continue with the example to develop the algorithm…
When the robot gets back to the first intersection, it will go left. The left hand rule calls for a left turn, so take a left and record the turn. We recorded “SUL”, but we know (because of the “U”) that we should have not gone down that path. What could the robot have done to avoid going down the dead-end path? Instead of “SUL”, the robot should have done “R”. So, our first general rule is: Anywhere the stored path ends with “Straight-U-Left” (SUL), we replace it with “Right” (R). So, delete the “SUL” in memory. And replace “SUL” with “R”. This tells the robot, next time through the maze, to take a right turn at the first intersection.
The next intersection is a “Four-Way” Intersection. The left hand rule requires a left hand turn, so turn left and record an “L”. The intersection coming up, the “Right-Only” has a special characteristic that needs explaining, so we will detour for a bit. The whole point of the maze algorithm is to eliminate bad turns. This “turn” has no choice, so a “bad” turn cannot be made. Since the robot can never go any direction but one, there is not even a need to record this turn in the maze path. So, in the maze, this will be treated as non-existent. The robot will take the correct turn as indicated by the left hand rule, but will never record this turn. So, the robot will turn right and record nothing in memory.
Next, the robot will encounter a dead-end, do a U-turn and record a “U”. And we know from before, that the “U” tells us we just made a bad turn and need to return to the intersection we just came from.
Returning to the intersection, we see left turn coming, so record the “L” and since we just came down a bad path, examine the path.
So, the robot, getting from point A to point B, did “LUL” which we know to be bad. What would the robot do next time to avoid this? Next time, we want to go straight, so we can replace the “LUL” with “S” for Straight.
We now have two “Replacement Rules”:
- Replace “SUL” with “R”.
- Replace “LUL” with “S”.
Once again, we are coming up on a dead-end, so we know that a Replacement Rule is coming soon. Do a 180 degree turn and record the “U”.
As we return to the intersection, we will take a left turn and record it.
As we return to the intersection, we will take a left turn and record it. By now, you may be catching on to the answer to the question? How do we know when it is time to invoke the Replacement Rule? ----Whenever there is a “U”!
We got here with "SUL", so the correct path next time will be to take a right turn, so replace "SUL" with "R". Next, left turn coming up, so take the left.
Only one more turn! The intersection coming up is a “Straight-Left” and the left hand rule will have the robot turn left and record an “L”.
So, turn left and record an “L”. So, we reach the end of the maze with RRL in memory, ready to take the next run. On the next run, the “RRL” will properly guide the robot to the finish using the shortest possible path.
So far we get:
SUL = R
LUS = R
LUL = S
There is another combination.
RUL = U (this is exceptional. For this see below example)
I have not covered every possibility.
This is a “Teach you how to fish” tutorial. NOT a “Give you the fish” Tutorial.
Have fun developing the source code for this algorithm.