Pololu Blog »
Video: LVBots May 2014 maze solving competition
On May 29, LVBots held a maze solving competition at Pololu. The goal in maze solving is to get from the start to the finish in the shortest time. Contestants had four tries to solve the maze. The first run is typically in a learning mode where the robot goes slowly and explores the maze. On subsequent runs, the robots would attempt the shortest path, and the best robots had progressively more aggressive speeds.
I would have liked to see one of the custom-built robots win, but despite their best attempts, none of the other competitors were able to beat a stock 3pi robot running Ben’s maze solving code from six years ago. The old video below demonstrates how the 3pi solves a maze and also describes how the course is built.
This year, we tried to hone our rules about robots cutting corners of the maze. No robot will follow the line perfectly, so we have to allow some corner-cutting, but we do not want to make it so lax that the robot could dead reckon directly to the finish. After a lot of debate, we settled on two rules:
- A designated point on the robot must not go past the walls of an imaginary 6″-wide corridor centered around the path.
- The whole robot needs to generally follow the same path through the maze.
It was exciting to see Paul’s robot, Dr. Maze, use dead reckoning to cut the corners. Paul was hoping to get away from line following and rely on encoders to navigate the maze. Unfortunately, this caused the robot to get lost on the long straightaway and fail to solve the maze. Dr. Maze exhibits its corner-cutting skills at the end of the first video.
Are you in the Las Vegas area? Check out the LVBots Meetup page to get involved.
The code running on my 3pi in the video is custom-written, heavily tuned for this specific style of course (e.g. it only works if my tires and the course are clean), and very ugly since it was frantically written the night before a competition six years ago, so it's probably not that helpful for me to post it, but I would be happy to give you some pointers on improving our sample 3pi maze-solving code. You might find the following forum thread helpful with that:
Also, I wrote and shared some maze-solving code that works on looped and non-looped mazes (it uses an entirely different, more complicated algorithm so it can deal with loops). If you want to take a look at that, see:
Most of the robots in this particular maze-solving competition used a "right hand on wall" or "left hand on wall" method to learn the maze, then simplified it to skip unnecessary turns. You might find the sample maze-solving program for the 3pi that Ben linked to in his last post helpful; it covers the "left hand on wall" strategy as well as simplifying the solution.