Maze Solving

SparkiDuino
Hard

Introduction

Solving a maze is fun and will help you build your roboticist skills up- thinking about every instruction that Sparki needs to not just wander around the maze, but actually complete it. At this point, with the things that we have already learned in the previous lessons, we can take advantage of some of Sparki’s sensors to implement some maze solving programs. To understand this lesson, it’s strongly recommended that you have learned the concepts from the Line Following and the Moving the Robot lessons first. So, let’s help Sparki get through the maze!

What You’ll Need

• Sparki.
• A maze. What we will use here is the poster in ArcBotics’ Sparki Materials Packs. You can also make your own with a white cardboard as the base, using black insulating plastic tape to “print” the walls. You can also download a ready to print maze from this link (please note that this maze can be printed in standard plotters, since it’s 90 cm wide). If you’re really into mazes, you can download that maze’s source SVG file, and modify it using the Inkscape open source vector graphics editor (or any other SVG editor of your choice).

How It Works

One of the simplest ways of solving a maze with a robot is by using the Wall Follower algorithm, also know as the left-hand rule (or right-hand rule). Forget about the robot for a while, and suppose that you are a person inside a maze. Finding the exit could be done just by keeping one of your hands always touching a wall.  And by “always”, we really mean always here. It might take you a while and you might wind up taking all the wrong paths in the maze before getting to the end but by keeping your left hand on the wall of the maze you wind up taking every single left hand turn (sometimes turning around completely) and, as long as you keep taking steps forward, eventually you’ll get to the end of the maze.  Take a look to the following animation, where the red point represents the person: Do you see the trick? It’s important to stick with either the left hand rule or the right hand rule and never switch between them in the middle of the maze. One will get Sparki through the maze faster, but you’ll never know which one unless you’ve seen the maze before. Let’s think about this. What do we have on our Sparki to imitate this behavior in a printed maze? The line following infrared sensors! So, how do we implement the “Left Hand” algorithm with Sparki ? The first thing to do is to ensure that Sparki really understands the lines that he is “viewing” with the infrared sensors. And to do that, we will need to use all of our line and edge sensors. Let’s remember what sensors we have: Soon we’ll see how to use these infrared sensors in our maze solving problem. First, let’s talk a bit about geometry…

The Main Idea

At a higher level, the Wall Follower algorithm consists of these four simple steps:
1. If you can turn left, do it.
2. Else (if you can’t turn left), if you can continue going straight, just go straight.
3. Else (if you can’t do either of the previous steps), if you can turn right, do it.
4. If you reached a dead end, turn back by turning around (in either direction) 180 degrees.
But it is not always that simple for a real robot. For example, even just going straight may be a problem for the robot if it’s positioned anything other than perfectly straight with respect to the black lines that make up the maze walls. Also- detecting some parts of the maze may use more than one sensor, as we will see in the next couple steps. Read on to begin your maze solving adventures!

Going Straight

Next we need to create some code that makes Sparki move straight ahead down a corridor. After we get our function for moving straight ahead set up we’ll back up and create the code that tells Sparki when to move straight ahead, as well as some code to display what Sparki is doing on the LCD display. Ok. Pseudo-code time! There are a bunch of parts to this code-
• Declaring some variables or “flags” to help Sparki go straight.
• Adding code to the sensor function to test to see if Sparki found a wall.
• Setting the variables to true or false.
• Adding an “if” statement that makes Sparki actually move in the loop.
• An “else” statement to stop Sparki if it didn’t find a wall.
So, let’s make a boolean variable and set it to false at the beginning. (If you don’t set it to anything it’s automatically considered to be false.) Ok. Now we need to add a little bit of code to our sensorReading function to see if there is a wall beneath the Edge Left Sensor. But wait! This will set foundLWall to true once and then foundLWall will always be true, no matter what! (This happens with sensors a lot.) We need to make sure we set the variable to false before we check it. Now to use the variable inside the loop( ) function! You should also feel pretty comfortable with “if” statements by now. One of the tricky things about this code is the “else” statement after it, the rest of the code inside of the loop( ) function will go inside of it! Also, you might be used to seeing a single conditional or question with two equals signs, greater than or equal signs or even a not equal sign (!=) inside of these parenthesis. By placing just the boolean variable name inside of these parenthesis we are still asking a yes or no question, but the answer is simply the value of the boolean variable. Try this code out now, Sparki should calibrate and then start marching straight ahead until the wall on its left side ends.

Sparki Lost the Wall or Came to a Branch in the Maze

Sometimes Sparki will lose the wall, so we really only want Sparki to move forward when there is a wall underneath the Edge Left Sensor. We already took care of that. But, if Sparki doesn’t detect a wall underneath the Edge Left Sensor then that may mean that there is a turn in the maze Sparki needs to take. (Remember, Sparki will always turn left if it can in our algorithm.) It’s time for… you guessed it, pseudo-code. Here are the steps we want to take for staying with the wall or finding the two different types of left hand turn that Sparki might take. (Remember, there’s a 90° left hand turn and a 180° left hand turn, these are different and will require different code for each.) We’ll put all of this code inside of a function called something like wallFinder( ). 1. Check the Edge Left Sensor, if there is no wall underneath it Sparki needs to turn off the straight( ) function and begin a wall finding function. 2. First, assume we just lost the wall somehow and try this pseudo-code- If there is no line underneath the Edge Left Sensor move forward and to the right a little trying to find the line again. If Sparki doesn’t find the wall again that way, back up exactly the same amount in the same direction to get back to where Sparki started searching and try the same thing again, only this time moving forward and to the left. If that doesn’t result in Sparki finding the wall then have Sparki move back to the starting position. If it did result in Sparki finding the wall, Sparki still needs to make sure it is pointed forward again so it doesn’t immediately lose the wall again. 3. So, Sparki didn’t find the wall, that means Sparki is probably at a left hand turn of some sort. To test for a 90° turn we’ll try this pseudo-code- Have Sparki move forward until the wheels are at the last place Sparki knows there was a wall. Now have Sparki turn to the left 90° and check the sensors to see if there is a wall underneath the Edge Left Sensor. 4. Still no wall! This means that Sparki is probably (hopefully) at a 180° turn. Sparki has already turned 90°, so Sparki just needs to turn another 90°, all the while looking for a wall. Hmmm. This pseudo-code sounds almost exactly like the code in section 3. We may be able to reuse some code for this…. 5. At this point we’ve exhausted all the possibilities we can think of for Sparki in a maze. (That’s not exactly true, what about a dead end in a maze? We’ll get to that later.) But often, between code errors and the unpredictability of the real world, situations like this will pop up. Always have a backup plan. There are a couple different options for Sparki now- Sparki can start its wall finding code all over again, it can do something like beep, or Sparki can just sit there waiting for a human to pick it up and help it out. Variables- Let’s think about the variables we’re going to need to achieve the pseudo-code above before launching into writing anything. We’re going to need a variable to keep track of how much Sparki has turned and which portion of our wallFinder code Sparki is currently using. We’ll call these variables wallFindType and turnCount. So, our first move is creating those variables- Checking Sensors- Now that we’ve got our variables we need to set these variables equal to certain values depending on what Sparki is doing. We’ll start with wallFindType. If Sparki is going straight ahead the wallFindType is zero. Then we’ll use a value of one to make Sparki start the wallFinder( ) function. (I’m also going to start adding LCD println commands to make debugging easier.)

Also, our conditional is a little different. By using two ampersands (&&) we can check two conditions to see if they are true. Only if foundLWall is false and wallFindType is zero will the code inside of the “else if” code execute.