1. Following a wall. Following a wall entails going on a roughly straight path that is roughly parallel to the wall on one of its sides (in this case, the wall of its left side). If it veers from its path such that it is no longer parallel to the wall, it needs to have a way to determine and correct this. If it gets too far away from or too close to the wall, it needs to be able to determine and correct these conditions as well.
2. Making a 90° turn. This turn will be a rough estimate of a 90° turn rather than an exact one. Once the turn is complete it will be able to correct errors of a small degree by using the same alignment procedure that enables it to stay parallel to the wall.
3. Making decisions about what to do based on where the robot is in the maze. The robot must recognize when a turn is possible or necessary and decide whether to go straight, turn right, or turn left. This involves checking the front of the robot for an approaching wall and also checking both sides for doorways or different branches of the hallway.

Finally, the robot must have a way of recognizing when it has gotten stuck and getting out of the situation. For example, if it is wedged in a corner, it would need to back up and then try again. These escape clauses need to cover a wide range of possible pitfalls.

In addressing these three components, we have tried many different methods. While this page describes those algorithms which we are currently using, we have included links to some of the methods that we tried which weren't as sucessful. Click here to see some of the navigation elements that didn't work.

 Click here to see our code.

Following a Wall

We have a working version of the wall-following aspect of the robot's navigation system. There are two distance sensors (front sensor and back sensor) on the left side of the robot. If the front sensor is closer to the wall than the back sensor, the robot turns to the right until it is properly aligned again, parallel to the wall. If the back sensor is closer to the wall than the front sensor, it turns to the left until properly aligned. If both sensors are too far away from the wall, it jogs to the left by turning left and then right again. If both sensors are too close to the wall, it jogs to the right in the same manner. The jogs make rather minor corrections and it is sometimes necessary to call a jog procedure two or more times in a row. However, most of the time a single jog is sufficient, and a more drastic jog would be an overcorrection more often than not.

In programming the robot to follow a straight wall, we struggled with numerous glitches, most of which involved the robot beginning a turn (usually in a jog method) and never finding the wall again and straightening out, but rather continuing to turn ad infinitum. We adjusted the threshold values and adjusted the mathematics of the code to allow for a greater margin of error, and this seems to have fixed these problems.

The robot had also tended to veer rather significantly to the right, but we experimented with the motors and discovered that the right motor was noticeable less powerful than the left motor. Replacing the right motor fixed the veering problem.

Making a 90° Turn with Shaft Encoding

In writing a 90° turn procedure, we considered a single case: the robot is approaching a wall to the front and needs to turn right. Once perfected, this procedure can easily be modified to make a left turn.

After previous trials with sensor based turns and timed turns, we decided on our current method of turning, using a shaft encoder. Using an IR sensor and a shaft encoder on one of the axles of the gear train, we can reliably count the number of revolutions each axle has made.

Advantages:

• This method will allow the robot to turn the same amount, regardless of the strength of the battery.

Disadvantages:

• If any slippage occurs in the axles or wheels, the robot will still think it is turning effectively, and may not make a precise turn.

As we have not experienced any problems with slippage yet, we do not anticipate this being a problem we will need to address. After initial experimentation to set the number of revolutions for a 90° turn, we do not expect to have to change these values. We plan to stay with shaft encoding as our method of turning.

Making a Decision

When the robot approaches a point at which it could or should turn, it needs to make a decision about which direction to go. We altered the structure of the program to accommodate the need for an interruption when this decision needs to be made. We added a main procedure that calls the wall-following procedure. The wall-following procedure is essentially the same as it has been, but it checks frequently to see if a decision needs to be made (i.e., if there is a wall in front or a doorway on either side). If so, the wall-following procedure is stopped, and the control returns to the main procedure. The main procedure then determines which case caused the interruption and takes the appropriate action.

We added a variable to keep track of whether or not the program needs to be interrupted. When the program checks all the sensors, it changes the value of this variable if it recognizes a wall in front or a doorway on either side. The wall-following procedure and all of its subprocedures check this variable frequently; if the variable indicates that a decision needs to be made, the wall-following procedure is stopped and control returns to the main procedure.

We struggled a great deal with the reliability of the crickets. The unreliability of our hardware slowed down our progress considerably in the area of code development, but we eventually determined the cause of these problems.

• Lisa Marie Hazel (lhazel@wellesley.edu)
• Meredith Shotwell (mshotwel@wellesley.edu)
• Created: February 28, 2000
• Last Modified: July 10, 2000