8.f. Improving the Maze-Solving Code

We have gone over the most important parts of the code; the other bits and pieces (like the function display_path(), the start-up sequence and calibration, etc.) can be found with everything else in the folder examples\atmegaxx8\3pi-mazesolver. After you have the code working and you understand it well, you should try to improve your robot to be as fast as possible. There are many things you can do to try to make it better:

• Increasing the line-following speed.
• Improving the line-following PID constants.
• Increasing turning speed.
• Identifying situations where the robot has gotten lost.
• Adjusting the speed based on what is coming up; e.g. driving straight through an ‘S’ at full speed.

The following video shows a 3pi prototype—it only has one blue power LED, but it is otherwise functionally identical to the final version—that we programmed to compete in LVBots Challenge 4.0. The code is more advanced (and complicated) than the sample maze-solving code we have just provided. Improvements over the sample program include a higher base running speed with better-tuned line-following PID constants, faster and smoother turns, and increased speed on long straight segments.

When we were trying to improve the 3pi’s maze performance, our first step was to improve its line-following ability by better tuning the PID constants as we slowly increased the robot’s maximum speed, and our second step was to improve the turns to be faster and smoother. Very quickly, however, we noticed that further speed improvement was being limited by the intersections. If the robot was moving too quickly when it hit them, it would invariably screw up somewhere. Going slowly enough to survive the intersections led to unnecessarily slow driving on long straight segments, however.

Our solution was to time the length of every segment the robot encountered during the learning phase. The code would reset the timer at an intersection and then stop it when the 3pi hit the following intersection. As the program stored an array of visited intersections, it also stored the segment times in a parallel array, producing something like:

{ L, S, S, R, L, ... }
{ 3, 3, 6, 5, 8, ... }

The top array gives the action performed at each visited intersection (L = turned left, S = went straight, R = turned right), and the bottom array gives the amount of time spent driving along the segment that directly led to that intersection. The units of the segment times were chosen to provide numbers that can allow the robot to meaningfully differentiate between longer and shorter segments but that never exceed 255 for any segment in the maze. This second restriction means that the values can be stored in an array of unsigned chars (i.e. each segment’s time takes up just one byte of memory), which helps keep memory usage down. The ATmega168 has just 1024 bytes of RAM, so it’s important that applications like this store data in an efficient way that leaves enough room for the stack, which is also stored in RAM. A good rule of thumb is to leave 300 – 400 bytes of RAM available for the stack and data used by the Pololu AVR library (or more if you have some deeply nested functions or functions with a lot of local variables). Note that the ATmega328 has 2048 bytes of RAM, which gives you a bit more room for your data.

Once the 3pi has learned the maze, the maze-driving algorigthm is essentially:

1. If the robot is going straight at the next intersection, drive the current segment at high speed; don’t even worry about slowing down until we know we have an intersection coming up that will require a turn.
2. Otherwise, drive the current segment at high speed until time T has elapsed, at which point slow back down to normal speed until the next intersection is reached.

The value T is computed from a function that uses the previously measured segment “length”. For short segments, T is negative and the 3pi just drives the entire segment at normal speed. For longer segments, T is positive and causes the 3pi to drive most of the segment at high speed before slowing down just in time to handle the intersection safely. We came up with a function for T on paper and then ran a series of tests to get the various constants right.

Typically, one might use encoders to measure the lengths of the segments. We were able to just use timing on the 3pi, however, because of the 3pi’s power system, which uses a regulated voltage for the motors and produces highly repeatable results. With a more traditional power system, motor speed would decrease as the batteries discharge, and a timing approach like this would potentially produce unreliable results. For example, if you were to use a robot with a more traditional power system, the function you come up with for T when the batteries are freshly charged might work poorly when they are nearly drained.

Tip: Once you start significantly increasing your maze-solving speed, performance becomes dependent on the traction of the tires. Unfortunately, traction decreases over time as the tires pick up dust and dirt from the course. Our fast maze solver needs to have its tires cleaned every few runs or else it starts fishtailing on the turns, which slows it down and can even cause it to mess up. You can see the effects of this on the second (solution) run of the video (the tires hadn’t been cleaned recently). You can easily clean the tires by wiping them with a little rubbing alcohol on a paper towel.