This page walks you through the steps I used to design and build a line maze robot. Each part in the list below has a link so you can travel to any desired area quickly.
I will be building this page in the order that I work on the project, which is not very sequential. So some parts are incomplete or missing. When the project is complete, I will remove this paragraph.
Microcontroller selection was easy. I just started teaching an embedded systems class where we use the Basic Stamp 2 and the Board of Education Robot (BOE-Bot), so that became the vehicle and chip of choice. The programming language for the Basic Stamp is PBASIC or Parallax-BASIC. I will be writing pseudocode and flowcharts in a generic way so those with other languages can follow along.
To properly design and understand the line maze algorithm, it is first necessary to break down the problem from the perspective of the robot. What will it see? What situations does it need to handle?
Since I wanted a hands-on experience for myself and my students, I decided to first build a line maze. I found a white board and used standard 3-4 inch electrical tape to make this maze:
Figure 1: The Line Maze
To produce this maze, I first took a large classroom white board and made a six inch margin around the edges. Then I looked for a spacing that was at least six inches and I wound up with a drawing that looked like a 4 X 9 table. I then tried to draw (hopefully interesting) paths on the lines. When the maze was decided, I placed three-quarter inch electrical tape along the selected paths to get the maze shown above.
In a previous project, I used the Fairchild QRD1114 sensor which includes the emitter and phototransistor in a very small package. I made an 8-in-line sensor array that worked great, and I would recommend this to any hobbyist that wants to add the resistors, and wire or design a PCB for the components.
For this project, I couldn't permanently wire the sensors since I needed the ability to make fine adjustments in the sensor spacing depending on how the array reacts to the line on the floor. So I decided on the Lynxmotion Single Line Detector shown here:
Figure 2: Lynxmotion Single Line Detector
The advantages are:
Mechanical talents are not my strong point, so it took several tries to manufacture a sensor mounting bracket. In testing the sensors, I discovered, as stated in the specs, that pointing the sensor straight down was not a good idea. A tilt angle would be needed to get reliable readings. The distance from the ground was also critical, so I needed a mounting bracket that allowed adjustment of the sensor tilt angle and the spacing off the floor.
I started with the sensors spaced close together. My gaol was to gradually increase the spacing until the robot, while travelling down the line would have eithe on or two sensors detecting black.
Figure 4: Sensors spaces just under 3/4 inch
I then had to realize that the robot could encounter any possible maze, not just the one I constructed, so I had to record all of the possible intersections possible in this type of maze. Here are the seven possible intersections the robot can encounter in this type of maze:
Figure 5: Seven Possibilities for Intersections
I had previous experience with mazes, so I knew the right and left-hand rules. In any maze where the goal is not isolated in an 'island', the goal can be reached by placing one hand on the wall and walking forward always keeping that hand on the wall. This algorithm will not yield the quickest or shortest solution, but will get you to the goal.
For example, using the left-hand rule in this maze...
Figure 6: Line Maze
...would have you travel like this: (Turns where you must turn right or left and have no other choice are skipped. Start in the open square at the top right and go to the blacked-in square at the bottom left.)
The right-hand rule would have been a little better because you would have gone down fewer dead end paths, but either way, the path gets you to the end.
If this maze is set up as a competition, as most are, the winner is the robot that gets through the maze the fastest in two or three attempts. The left-hand, right-haned rules as described above are fine, but in a competition, will doom you to failure! A robot, to be competative, must be able to remember all of the dead-ends and somehow not go down these paths in future attempts.
So, in a competition, your algorithm must get to the goal, but figure out how to get to the goal next time in the most direct path.
For example, the robot solving the maze above, must eventually come up with this path only:
The first mission is to create code that will allow the BOE-Bot to travel from the Start to the Finish of the maze. You can use the right-hand or left-hand rule. I will use the left-hand rule. Ignoring any 90 degree turn where there is only one possible direction to travel, the rules are summarized as follows:
So, said another way, taking all possibilities, the left-hand rule always prefers the left-most possible direction. In this maze, there are no 4-way intersections, so at each intersection there are at most two possibilities.
In the seven possibilities above, only three relate to the left-hand rule.
Providing the maze has no 'islands' this algorithm will always get you to the end of the maze. It will not usually find the shortest route, but we will cover that soon.
Here is the PBASIC Source Code to solve the line maze above (or any non-island maze):
' {$STAMP BS2}
' {$PBASIC 2.5}
'###################################################################
' This program uses IR sensors to follow a black line maze. #
' Developed by Richard T. Vannoy II, RoboticsProfessor@gmail.com #
'###################################################################
'##########################
'# Initialize Variables #
'##########################
i VAR Byte
j VAR Byte
PAUSE 2000
FREQOUT 4, 500, 4000 'Make a sound, then pause 3
' seconds before starting
PAUSE 3000
start:
'#####################
'# Begin Main Loop #
'#####################
j = 15 - INC 'INC is the memory name for
' pins 8-11
'I do 15-INC because I want 1 to
' equal black and 0 to equal white,
' which is the reverse of the
' sensor output.
IF j = 6 THEN 'RIGHT ON!!
PULSOUT 15, 800 'Medium speed left (speed up later)
PULSOUT 14, 700 'Medium speed right(when this works)
ELSEIF (j = 2) OR (j = 3) THEN 'Slight Right
PULSOUT 15, 800 'Medium speed left
PULSOUT 14, 725 'Half speed right
ELSEIF (j = 4) OR (j = 12) THEN 'Slight left
PULSOUT 15, 775 'Half speed left
PULSOUT 14, 650 'Fast speed right
ELSEIF j = 1 THEN 'Hard Right
PULSOUT 15, 775 'Half speed left
PULSOUT 14, 735 'Slow speed right
ELSEIF j = 8 THEN 'Hard Left
PULSOUT 15, 765 'Slow speed left
PULSOUT 14, 650 'Fast speed right
ELSEIF j = 0 THEN 'ALL WHITE!! Ran off end of line
DO 'U-Turn left
PULSOUT 15, 700 'Left wheel backwards
PULSOUT 14, 700 'Right wheel forwards
PAUSE 20
j = 15 - INC 'Keep reading sensors until
IF (j > 4) THEN EXIT 'at least one sensor hits the line
LOOP
ELSEIF j = 14 THEN 'Left only
GOSUB leftTurn
ELSEIF j = 7 THEN 'Right only
GOSUB inch 'Probable right turn, but verify
j = 15 - INC
IF j = 0 THEN GOSUB rightTurn
ELSEIF j = 15 THEN 'T Intersection
GOSUB inch 'This could also be end of maze, so
j = 15 - INC ' inch forward and check.
IF j = 15 THEN
END 'Lots of black!=End of maze
ELSE
GOSUB leftTurn 'Just a normal "T" intersection, so
endif ' turn left
ELSE
PULSOUT 15, 765 'All possibilities not covered above
PULSOUT 14, 725 'Slow turn if strange combination
ENDIF
PAUSE 20
GOTO start
'######################
'# End of Main Loop #
'######################
'######################
'# Begin Subroutines #
'######################
leftTurn: '$$$$ LEFT TURN $$$$
GOSUB inch 'Forward one inch before the turn
DO
PULSOUT 15, 725 'left back a little
PULSOUT 14, 700 'right medium forward
PAUSE 20
j = 15 - INC 'Keep going until one or two of the
IF (j = 12) OR (j = 8) THEN EXIT 'left sensors is over the line
LOOP
RETURN
rightTurn: '$$$$ RIGHT TURN $$$$
GOSUB inch 'Forward one inch before the turn
DO
PULSOUT 14, 775 'right back a little
PULSOUT 15, 800 'left medium forward
PAUSE 20
j = 15 - INC 'Keep going until one or two of the
IF (j = 3) OR (j = 1) THEN EXIT ' right sensors is over the line
LOOP
RETURN
inch: '$$$$ MOVE 1 INCH FORWARD $$$$
FOR i = 1 TO 5
PULSOUT 15, 800
PULSOUT 14, 700
PAUSE 20
NEXT
RETURN
left90: '$$$$ TURN LEFT 90 DEGREES $$$$
FOR i = 1 TO 15
PULSOUT 15, 700
PULSOUT 14, 700
PAUSE 20
NEXT
RETURN
right90: '$$$$ TURN RIGHT 90 DEGREES
FOR i = 1 TO 15
PULSOUT 15, 800
PULSOUT 14, 800
PAUSE 20
NEXT
'#####################
'# End Subroutines #
'#####################
The code above will work for any proper maze, but since it doesn't keep track of all the dead-ends and bad pathways, it will never get 'smarter' or find a shortest route. If you examine the code above, you might see that it decides what to do at each intersection, but it never keeps track of the turns taken or the alternatives when available. Since the robot has no 'memory', it will take the same path through the same maze every time.
To fix this, we must add code to save the action taken, and the alternative, so that we can later make a different turn.Let's take a simple example. Say that we have the simplest of mazes, a maze in the shape of the letter 'T'. Picture the bottom of the 'T' as the starting point and the top right end of the 'T' as the finish. A right hand-rule would start, make the right turn, then complete the maze.
Our left-hand rule robot would take an incorrect path. It would get to the intersection, then go left, then find the dead-end, reverse, go straight at the intersection, then get to the finish. So the left-hand rule robot would somehow need to turn GoLeft-UTurn-GoStraight-Finish into GoRight-Finish.
To do this, the robot must 'un-turn' or 'unravel' all of the bad turns and modify the final path to the optimum above. The solution seems to be in one of the following:
And once the shortest path is found, the last challenge is to have the robot get down the shortest path as fast as possible. I see two areas where programming can be used here:
The first test of the source code did not look like the source provided above. In the first run of the robot, it ran off the lines, ran in circles, turned the wrong direction, and overall looked like a total failure!! I first slowed down the servo speeds so I could better see what was happening. Then I would take a run at an intersection to see the behavior. By watching what the robot did or didn't do, I worked through all possible intersections several times. I found a number of problems, but mostly the problems had to do with the poor or wrong execution of a turn.
There are several possibilities when reaching an intersection. For example, when reaching a 'T' intersection, this could either be a 'T' or the end of the maze, so moving forward one inch (to clear the 3/4 inch tape) and then rechecking sensors, gives two possibilities. If the sensors see all white, then the robot is at a 'T', so a left turn is taken. If the sensors see all black, the end of the maze was reached, so the program shuts down.
For a Left-or-Straight Intersection, or a Right-or-Straight Intersection, a move forward one inch is also needed to differentiate between these intersections and a Left-Only or Right-Only Intersection, so I had a built in turn here. Since I had already moved forward a little, the turn could be executed by just rotating the motors in opposite directions for enough time to turn 90 degrees and then take a sensor reading to get started and settled in on the new course.
In the code above, there are two variations of right and left turns (rightTurn, right90, leftTurn, left90). I started by using right90 and left90, but found that as the batteries got weaker the robot didn't make the full 90 degree turn. I solved this in rightTurn and leftTurn by making a partial turn, then reading the sensors until the right, or left sensors pick up the line. That way the robot is off and running as soon as it detects it has acquired the new line.
Here is the video of the source code above as it traverses the maze: