The algorithm of Gadget

The code for Gadget is written in the Wiring language for the UBC Engineering Physics custom-designed TINAH board with the Atmel ATMega128 16MHz microprocessor, similar to that of the more famous Arduino systems.

The code

The following code is version 28 (we keep many versions to make it easy to rollback to previous versions easily). This is the latest version and is seen here raw and unmodified.

Description of algorithm

Tape-following

Gadget has more tape-sensing QRD1114 sensors than any other robot this year therefore there should be some algorithm which would give us an advantage over anyone with less sensors. To efficiently and rapidly read and process all eight sensors, Russell has developed a "Two-Eight" scanning method. There are two modes:

Eight Sensor Scan: the robot scans each of the eight sensors from left to right. Once a sensor "sees" the tape, it sets that sensor as the reference sensor and enters Two Sensor Scan.

Two Sensor Scan: the robot scans the reference sensor, and the one on the right of it. If only the left one sees the tape but not the right one, it shifts the reference sensor leftwards if the reference sensor is currently right of the center; in the opposite case, it shifts the reference sensor rightwards if it is currently left of the center. If both relevant sensors are on the tape, then no shifting occurs; if nothing is detected, it switches to Eight Sensor Scan.

In each iteration of Two Sensor Scan, if at least one sensor is on, it sends an instruction to the steering servo motor. The tape is either exactly under one sensor, with eight different possibilities, or in between two adjacent sensors (both of which read positive), with seven different possibilities. So, there are fifteen possible angles. Hence, the instruction sent to the angle is the appropriate one from a lookup table containing 15 angles.

Lane-changing

The track of the Roborace has two lanes. Avoiding obstacles requires Gadget to detect obstacles and switch to the other lane if that is the case. To this end, Daniel and Russell have developed a sophisticated algorithm to switch lanes. A boolean variable determines which lane Gadget is on. Lane changing is initiated if the rangefinder detects an obstacle for longer than a certain threshold. Once initiated, lane changing goes through several stages:

Stage 0: Initiate lane change: the robot sets the servo motor to an angle so as to steer towards the other lane. Then, it enters Stage 1.

Stage 1: Leave the tape: the robot continues steering in the direction set by Stage 0, which is unchanged. Now, it scans all eight sensors until none of the sensors are on the tape. Once this condition is satisfied, the robot sets the servo motor to go straight. Then, it proceeds to the next Stage.

Stage 2: Transit between lanes: the robot moves straight in between lanes until it detects the tape track. If the tape track is on the right side, it is entering the right lane, regardless of whether it came from the right lane (but of course, if it is entering the same lane that it came from, lane change probably failed. This sometimes happens during acute curves in the track. However, such failed lane changes may still help the robot avoid the obstacle). Conversely, if the tape track is on the left side, it is entering the left lane.

Stage 3: Lane re-entry: the robot continues moving straight until the tape track has moved to the side away from the new track. The reason for this slight "overshoot" is because if the tape was on the same side as the new track, the standard tape following algorithm would make it forcefully steer into the new track (even though it is already angled to enter this track) and result in unacceptable oscillations and even failure of the tape-following algorithm. However, overshooting slightly would result in an elegant and smooth lane re-entry.

Stage 4: End of lane change: after a successful lane change, the robot is now on the new lane, so the boolean variable governing the lane it's on is logically negated.

Motor control

Gadget is capable of very high speeds because it uses more powerful motors (and it has two of those) than most other robots. However, the servo motor requires time to respond; as such, moving at too great a speed may cause oscillations since the robot is simply unable to steer fast enough. Hence, the robot is usually run at roughly 70% voltage. In addition, to avoid skidding, Daniel has implemented a way for braking to be employed during curves. A timer for braking starts when the robot suddenly steers after going straight, or when starting to lane change. Then, the robot reduces motor PWM duty cycle to some value (out of 1023) based on a lookup table containing one appropriate value for every steering angle. It only stops braking after a certain number of milliseconds, usually around 200. After that, it accelerates at full speed for a short period of time before returning to its usual speed.

Optimizations

The code runs relatively fast, thanks to the optimization efforts of Daniel. It scans the tape over 15,000 times per second. Given the relatively simple nature of the algorithm compared to, say, a chess engine, there is not much use for separate functions, which result in unnecessary increases in overhead. By using lookup tables rather than re-calculating values repeatedly, the workload of the processor is further reduced. In addition, the code only prints certain things to the LCD screen (a slow and lengthy process) once every many thousand times the algorithm itself loops.

However, the software does not bottleneck the performance; instead, the servo motor does. So only once per thousands of times the tape is scanned does the servo motor actually steer.