I've Decided to Do the Line-Maze with 3PI

My students fielded 11 robots at the end of the last semester, and they really did a great job!
Here’s a sample of a fast line follower one student did:
Autonomous Line Following PWM Controlled Car

…anyway, most of the line followers and line maze robots used the BS2 chip and servos for motors. The servos were super slow compared to the 3pi videos on YouTube, so I went for speed. Here is my slow line maze entry:
My Line Maze Robot

So, it took a while, but I finally figured out how to do the algorithm for the line maze. I do it by “unwinding” each bad turn after every dead-end is reached. The BS2 has about 32 bytes of memory, so is very limited and won’t do well with any “include every turn” algorithms.

My questions:
Anybody wanna talk about line maze algorithms with 3pi?
How much memory is available in the 3pi for maze data?


Thank you for sharing your projects with us! I moved this thread to the 3pi forum because I think a discussion on 3pi maze-solving would benefit other 3pi users and it would be easier for them to find it here. Have you had a chance to look through our 3pi user’s guide yet? We have an entire section devoted to maze solving. It won’t produce a maze-solver that’s as fast as the one in the video on the product page, but it explains the algorithm and provides simpler, slower, working code. This leaves the user the fun of improving it by doing things like tuning its performance better for higher speed, making smoother turns, remembering the lengths of the straight segments of the course so that you can drive them faster, etc.

The 3pi has 1024 bytes of SRAM and 512 bytes of EEPROM, which gives you plenty of room to store information as you explore a large maze, especially if you’re efficient about the way you store that data. In a non-looped (loopless?), right-angle maze, you only need two bits of information to store the action taken at each intersection as there are only four options available to you: left, right, straight, and back. So if you’re dealing with an absolutely huge maze, you can pack four intersections’ worth of data into a single byte of memory (though this makes the programming a bit more complicated).

- Ben

Sorry, i didn’t see the 3PI section.

I’ve downloaded everything I can, so will be reading up soon.
Looks like there is plenty of memory to store a line maze.

I never thought about storing the length of lines so you can speed up the robot on the straightaway. Great idea!! Could you talk about how to do that?

Seems like you could set some timer for each leg, but wouldn’t it take 3 passes?
One pass to do the rule (say left-hand). (But because you “unwind” or correct for bad dead-ends, you won’t have an accurate length for a long straightaway that had several detours on pass one.
Pass two to go the best route and time each leg.
Pass three to go the best route at best speed.

Or could there be a better way?

When I was trying to improve my maze performance, I noticed that my speed was being limited by the intersections. If I was moving too quickly when I hit them, I would invariably screw up somewhere. Going slowly enough to survive the intersections led to annoyingly slow driving on long straight segments, however. My solution was to time then length of every segment I encountered during the learning phase. I would reset the timer at an intersection and then stop it when I hit the following intersection. As I stored an array of visited intersections, I would store the times in a parallel array, so I would end up with 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 (in some units that provide reasonably small numbers that can allow me to meaningfully differentiate between longer and shorter segments while still fitting within a single byte for all segments).

Once I’ve learned the maze, my maze-driving algorigthm is something like:

  1. If I am 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), else
  2. 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

T is computed from a function that uses the previously measured segment “length”. For short segments, T will be negative and I will just drive the entire segment at normal speed. For longer segments, T will be positive and cause me to drive most of the segment at high speed before slowing down just in time to handle the intersection safely. I came up with a function for T on paper, and then I ran a series of tests to get the various constants right. This approach requires just one successful learning run.

Typically, one would use encoders to measure the lengths of the segments. I was 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, the function you come up with for T when the batteries are freshly charged might stop working when they are nearly drained.

- Ben