Mazes and Labyrinths Have Always Amused Young and Old People. Everyone Has at Least Once

Introduction

Mazes and labyrinths have always amused young and old people. Everyone has at least once been in a labyrinth. Children ask them self, “will I ever get out?”, while older people are thinking of smart ways to get out. “Is it not possible do let a robot do that work? “

It is possible. There are different methods for robots to solve a maze. Of course it can choose path randomly, but is that efficient? Probably not. What is efficient? There are a couple of algorithms for robots to solve a maze, but they are very complicated. The need the robot to be able to remember intersections and require hard programming.

But there is method that even people use in labyrinths. It is the right-hand method. It states if you keep your right hand on the wall on the right, you will be guaranteed to reach the finish. Hey! That might not be too difficult for a simple robot to do! It will only need to be able to detect walls, and adjust its direction. Let us do that!

Question of investigation

What is the most efficient way to navigate a Boe-Bot through a maze?

Hypothesis

We think that using a “follow a wall” technique will be the best solution. You will always find the exit of a maze by following the left or right wall. We will try and make a setup in which the Boe-Bot can follow the right wall but turns when it faces a wall or a 180 corner.

For example this maze can be solved using this technique:

Boe-Bot

The Boe-Bot is a simple robot that can be modified easily. It moves by using two wheels connected to two different motors and it has a third ball-shaped wheel to maintain balance. It is powered by four AA-batteries.

In this drawing we have shown the different components.

The Boe-Bot will not do anything until you tell him what to do. The robot is being programmed by using the language Pbasic. The script has to be typed in the Basic Stamp Editor on a pc, and uploaded via a COM cable to the robot. The Editor is just like notepad.

On top of the robot is an input/output breadboard. This allows you to plug in some LED lamps, sensors and much more. These are the available components of the robot:

• Two infrared sensors
• Two whiskers
• Two LED lamps
• Beep speaker

If you combine good programming with the components of the robot, you can let the robot domany different things, from detecting walls with whiskers to driving in circles or even avoid obstacles by using infrared sensors.

PBasic language

As already has been told, the Boe-Bot uses PBasic language. This language is very similar to BASIC language, one of the oldest en most known programming languages for computers.

It is easy to read, since it uses normal words such as ‘IF”, “THEN” and “ELSE”.

The main thing PBasic does, is to constantly check if something is true or a variable has a certain value and then do something. A simple example:

What the above code does is to check whether the variable A has the value 10, and if so, it gives the variable B a value of 5.

Commands:

Below are the common commands we use to program the robot.

IF A = 10 / If variable A has the value 10
THEN / Then
…….. / Do something
ENDIF / Stop checking
FOR counter = 1 to 100 / Repeat the part between FOR and NEXT 100 times
Do something
NEXT
PULSOUT 12, 650 / Turn left servo (wheel), 650 means clockwise
PULSOUT 13, 850 / Turn right servo (wheel), 850 means counter clockwise
HIGH 10 / High LED on pin 10
LOW 10 / Low LED on pin 10
FREQOUT 4, 1000, 2000 / Let speaker on pin 4 beep for 1000 ms with frequency 2000 Hz
Using infrared:
IF irDetectLeft = 0 THEN / If the left infrared LED detects something
……. / Do something
ENDIF / Stop this loop

Our script

We want to make the robot follow the right wall of the maze. So what is has to do, is to drive forward when there is a wall on the right, and make a left turn when it reaches a corner and turn right when possible. In simple language the Pbasic code has to look like this:

To detect walls, the Boe-Bot uses 2 infrared sensors. One points forward to detect walls up ahead, the other one checks whether there is a wall on the right. We chose for infrared instead of whiskers, because whiskers need a very solid maze and can only detect objects right in front or on the sides.

Explanation of the attached script

The parts in the script behind apostrophes are comments, these are just there to organize the script and do not influence the code.

This part determines what version of Pbasic is being used.

In the part [Variables] we tell the robot what variables it can use.

Then there is the main routine. The part between DO and LOOP is continuously repeated. In the code we have used so called subroutines. These are pieces of code that you can recall by using the command GOSUB. The use of subroutines makes a script more efficient and also helps organizing the script.

“GOSUB Check_Ir” means, go to the subroutine Check_Ir. In this part the robot sends a pulse from both the left and right infrared sensor. If the sensors detect a robot, the LED lamps burn.

Then this part:

Here the robot executes what we have told on the previous page. It detects whether there is a wall on the right and in front. If there is a wall in front the robot, it executes the subroutine Turn_Left, which simply makes the robot turn left. If there is a wall on the right, the robot drives forward.

When there is no wall on the right, it executes the subroutine Turn_Right. This one is a little more complicated, since it has to drive around the right wall. Therefore when the robot detects that there is no wall anymore on the right, it first drives forward, then makes a 90 degree right turn. Then again it checks whether there is wall on the right, if there is not, it makes a 90 right turn again.

The bold words in italic are the subroutines.

The maze

As the final assignment for the Boe-Bot we decided to go with a maze. Why a maze you would ask? For a couple of reasons:

• In order to navigate through a maze there need to be some intelligence. In order to have this intelligence, you must program the robot.
• A maze is a very good test method if your plans actually work. The Boe-Bot only needs to do a few basic things, and of these can be tested individually.
• You can custom build a maze to the needs (size, width, height, color and materials)

Basically there are 2 categories mazes; ones with loops and ones without loops. A maze without loops is also called a “standard” or “perfect” maze. Obviously a non perfect or a non standard maze is one with loops. We’ve chosen for the perfect maze because these are the most common mazes and solving a none perfect maze with the Boe-Bot is nearly impossible.

In order to solve a maze you need something called an algorithm. This sounds really as a complicated mathematical term but it is not. For example this is a very simple algorithm:

In order words; an algorithm is a plan, in order to solve something.

There are several ways to solve a maze. All the following methods do not use any prior knowledge of the maze it is about to solve.

1. The first way is called the “standard mouse algorithm”. Though it might sound complicated it is really not. What is comes down to is that the robot will drive straight forward for as long as possible, however if it encounters a wall it will randomly (50/50) choose to go right or left. Of course this is not a really intelligent way of solving a maze but in some time it will do.

1. The second method to solve a maze is the “wall follower”, this is also the method we are using. It is also called the “right hand” or “left hand” rule. When in a maze with both the exit and entrance are on the outer wall this will guarantee your way to the exit. The idea behind it is very simple. Try and picture a maze, if you look closely you can see that every wall is connected to the outer wall. If you would “pull” the maze apart you would end up with a square or circle. To clarify this look at the following pictures.

As you can see, by simply following either the right or left wall from the beginning will get you to the finish. Note: this only works when both the entrance and exit are on an outer wall and not in the middle.

1. The third method the solve a maze is the “Tremaux Algorithm.” This method uses line on the floor to find its way. It works as the following: the robot would navigate through the maze using infrared to avoid the wall. Though it also marks the way it came from. When arriving on a junction it will choose a non marked section, and as it is passing through this section it will also mark it. Also try and choose an unmarked path it the first rule. But what if all the paths are already marked? Take a passage that has already been marked and mark it again. The second rule is to never take a twice marked path. This will lead you to the exit, and if there isn’t one, back to the entrance.

We will not be using the method. The reason for this is because we simply do not have the right equipment to do it. The Boe-Bot can follow lines, and choose a section without a line over a section with a line. However, it cannot sense double lines nor can It use both the infrared and the lines following equipment at the same time.

Conclusion

After extensive testing we have come to a preliminary conclusion. Our initial question of investigation was: What would be the best way to navigate the Boe-Bot through a maze?

The best way to drive the Boe-Bot through a maze is using the right or left hand technique. Using the infrared detector the Boe-Bot will follow the right wall in the maze. This will eventually lead it to the exit.

We have used this setup on the Boe-Bot. As you can see sensor 1 is pointing forward and sensor 2 is pointing to the right. We have used the following commands:

• If 2 is wall + 1 is air = forward
• If 1 is air + 2 is air = turn 90 degrees right.
• If 1 is wall + 1 is wall = turn 90 degrees left.

These 3 lines in PBasic will make sure that the Boe-Bot will navigate through the maze.

Discussion

In order to get a clear view on the issues we still have to deal with they have been divided into 3 different categories namely: Script, Boe-Bot and Maze. We discuss the issues relevant to these subjects.

Maze:

Color:

Infrared sensors are very sensitive. There seem to be a difference between air, or nothing and a wall. We’ve come with a solution for this problem. We will try and paint the floor of the maze black to have a big contrast. Another option besides painting would be black paper.

Edges:

When we build the maze it was a rather quick thing to check out if it would actually work. Therefore most walls are not 90 degrees but have a minor error of about 5 to 10 degrees. This results in the Boe-Bot not driving parallel with the wall. This could lead to a potential problem; as it would turn 90 degrees when it is too far away from the wall. We could solve this by rebuilding the maze very carefully with exact 90 degree corners.

Height:

The maze is only 10-12 centimeters high. Although the infrared detectors are pointed down, it might be a potential problem. If the Boe-Bot come to close to the wall the detector might point over it, which results in a malfunction. We could solve this problem by rebuilding the maze with higher walls.

Discussion

Boe-Bot:

Fluorescent light:

Something we only found out 2 days ago. Fluorescent light can make a huge difference when it comes to interfering with the infrared sensor. The Boe-Bot uses the infrared sensor to navigate. If it interferes too much it might result in a malfunction. To solve this we simply need to move to another room without fluorescent light.

Turning angle:

The Boe-Bot does not use degrees but steps. You can calculate the steps back to degrees. However you do need to measure this. If it does not turn exactly 90 degrees it might not drive parallel to the wall which will result in a malfunction. To solve this we need to measure multiple times to make an accurate estimate as possible.

Speed:

The Boe-Bot seems to be driving a little too fast. When it is driving slowly it has got more time to turn and the infrared detectors will work better. However for some reason the values for both servo’s that are giving in the manual have quit a large error to the right. This will result in the same malfunction as with the edges. We do not have a clue how to solve this problem apart from making changes to the hardware. Therefore we will try and do it with a faster speed.

Script:

Turning left:

According to us, the Boe-Bot must turn left when facing a wall both in front and on the right. However for some reason it does not. We are not sure if it has to do something with the script or with problems stated above. We have already asked for help on the Paralaxx forums and we are questioning if it has got something to do with the maze. Currently we think it has got something to do with the maze and we will therefore try and fix that first.

Logfile
What: / Where: / Who: / Time: / When:
PWS initializing / Aula / Thomas / 4 / 17-7-2008
PWS initializing / Thuis / Nick / 2 / 21-8-2008
Studying Boe-Bot / Exo / Both / 4 / 11-9-2008
Studying Boe-Bot / Exo / Both / 2 / 18-9-2008
Studying Boe-Bot / Exo / Both / 2 / 25-9-2008
Studying Boe-Bot / Exo / Both / 4 / 2-10-2008
Installing Software / Exo / Both / 2 / 6-10-2008
Programming Boe-Bot / Exo / Both / 4 / 9-10-2008
Building Boe-Bot / Exo / Both / 12 / 22-10-2008
Pbasic/general / Exo / Both / 6 / 23-10-2008
Pbasic/Boe-Bot / Exo/rc / Both / 6 / 23-10-2008
Maze preparation / Home / Both / 2 / 24-10-2008
Pbasic / Home / Both / 2 / 25-12-2008
Maze/script / Exo / Both / 8 / 27-12-2008
Maze / Exo / Nick / 4 / 28-12-2008
Issues / Rc / Thomas / 8 / 1-12-2008
Robot fix / Exo/rc / Both / 4 / 4-12-2008
Script/paper / Exo / Both / 8 / 8-12-2008
Script / Exo / Thomas / 2 / 1-12-2008
Script / Exo/rc / Both / 4 / 11-12-2008
Script/paper / Exo / Both / 8 / 16-12-2008
Paper / Home / Both / 4 / 15-12-2008
Paper / Home / Both / 4 / 17-12-2008
Total hours: / 106

Total hours per person: 53