Toeing the Line: Experiments with Line-following Algorithms

Applicant Name:	Jonathan Gray (Marlboro, NJ)
Applicant Grade:	Grade 9
Category:	Senior Division: Mathematics / Computer Science
Project Description:	Following lines is an essential part of robot navigation in a First LEGO League robotics competition. However, programming a robot to follow a line is not an easy task. This project compares several algorithms that robots can use for line following. I hypothesized that robots that were programmed to stay closer to the line and stop less for corrections would be faster and more accurate. For the experiment, a basic LEGO robot used six different algorithms to follow a winding black line, and the robot’s speed and accuracy on each run were recorded. My hypothesis proved to be incorrect. The results showed that algorithms programmed to continuously search for the line were more accurate than those that tried not to lose the line. It was also found that the faster algorithms sacrificed accuracy for speed.

Problem:
Which one of six specific algorithms will allow a robot with one or two light sensors to follow a winding black line on a white background most accurately and most quickly?

Hypothesis:
I predict that the algorithms will rank in a certain order from fastest and most accurate to slowest and least accurate. These predictions are based on how close to the line the robot is programmed to stay and how much time it should spend correcting its route.

Method:

1. Construct a basic Lego Mindstorms robot with two light sensors.
   
   
2. Program the robot using RoboLab software.
   
   
3. Create a test mat using black electrical tape on poster board.
   
   
4. Use an AC adapter to keep robot power levels at maximum.
   
   
5. Test each algorithm four times (alternate the left and right sides of the line where applicable):
   
   
   1. Place the robot on the test mat so that the back of the robot is flush with the beginning of the line, and the light sensor is centered over the line.
      
      
   2. Start the stopwatch and run the appropriate program on the RCX at the same time.
      
      
   3. Hold the power cord lightly above the robot so that the robot does not drive over it. Do not apply any resistance to the power cord.
      
      
   4. Stop the stopwatch when the robot reaches the end of the line or leaves it, and record the time displayed in seconds.
      
      
   5. Record the distance the robot traveled along the line in inches.