This paper refers to a robot that has learned the left-hand rule, so an explanation of this rule is necessary here.
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...
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?"
Since the robot will have five sensors, 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.
The five sensors can either be analog or digital. If they are digital, they will only indicate one (1) or zero (0). If the sensors are analog, you can either build the circuitry to convert this analog signal to a one or zero, or use an input port in your micro controller that will do analog to digital (A/D) conversion.
From now on, I will presume that 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. If the sensors are spaced properly, they can be set to indicate very precisely where the black line is in relation to the robot. Using this logic, here are a few combinations of patterns the program can "see" as the robot moves around:
0 0 1 0 0 = The line is right under me in the middle.
0 1 0 0 0 = The line has moved to the left (or the robot has drifted right)
1 1 1 0 0 = Robot may have just gotten to a left hand turn (or Straight or Left above)
1 1 1 1 1 = 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.
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 a dead end.
In this case, the behavior is simple; Do a 180 degree turn and go back the way you came.
Right only and Straight or Right intersections both present the same pattern initially.
0 0 1 1 1
How do we find out which??? I turns out, all you have to do is to create a subroutine called "inch()" that moves the robot forward one inch. (Notice that to see 0 0 1 1 1, the robot has just crossed on to the 3/4 inch black tape line and moving one inch forward will guarantee that the robot has passed over the line. ALSO, note that the robot, at this point, is positioned perfectly to take a 90 degree right turn by having one motor go forward and the other go backward.)
So look at the two possibilities above. What will the sensors see one inch 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
inch() ' Go one inch forward
pattern = readSensors()
if pattern = "00000" then
gosub rightTurn
else
Go straight (actually - Do nothing, or Go back to following the line under you.)
end if
end if
This makes the inch() subroutine very important. It becomes the method for determining which of several possibilities has just been encountered.
Left only and Straight or Left intersections both present the same pattern initially.
1 1 1 0 0
How do we find out which intersection this is??? Once again, we call the inch() subroutine 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. If this was a right-hand rule robot, we would develop pseudocode similar to that above to decide what to do.
All three of these show an all ones pattern:
...will all detect 1 1 1 1 1 initially.
Now, after the inch() routine is called, 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
The robot actually spends most of it's time following the line between intersections, so let's cover the line following behavior. To see the patterns that develop while the robot is following the line, picture setting the robot down on a white surface. The observed pattern will be:
0 0 0 0 0
Now, if you were to slowly pass a piece of 3/4 inch black tape under the sensor array, if your spacing is correct, you should see the pattern change like this as you move the tape:
1 0 0 0 0
1 1 0 0 0
0 1 0 0 0
0 1 1 0 0
0 0 1 0 0
0 0 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1
Notice that none of these patterns are "Intersection" patterns, so we have no conflict. I start out by writing the behavior I want to see for all of these combinations
0 0 1 0 0 = Robot directly over the line. FULL SPEED AHEAD!
0 0 1 1 0 = Robot has drifted left or line is turning to right, so...
Slow down the right motor a little to get the robot exactly back over the center.
0 0 0 1 0 = Right motor ahead slow, Left motor ahead medium
Motor speeds of "Fast", "Medium" and "Slow" are arbitrary. These speeds need to be set and then experimented with until the robot reacts smoothly and efficiently to the line.
What I found was that I can get such fine control of line following that the robot never gets far from centered over the line, so the outside two sensors serve no purpose during line following and only kick in at the intersections.
Please email me at RVannoy@ITT-Tech.edu if you have any questions or comments.
Copyright 2007-2010 Richard T. Vannoy II, All Rights Reserved.
Last modified: April 28 2009 08:03.