3. Maze Solving

Pololu Optimized Line-Maze Solver

This is a demonstration of a 3pi maze-solving robot that was programmed by a Pololu engineer to compete in LVBots Challenge 4.0. The code running on this 3pi prototype—it has only one blue power LED on the bottom—is more advanced (and complicated) than the sample maze-solving code we provide. 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.

Tech Fest 3pi Line-Maze Solver (by RoboticsProfessor)

For pictures and information, please see the San Diego Tech-Fest, Winter 2009 web site.

Flood-Fill Line-Maze Solver for Looped Mazes

Lufamseed programmed his 3pi with a flood-fill algorithm that allows it find the shortest path through a looped maze. A looped maze is one that has internal cycles that can thwart a standard left- or right-hand-on-the-wall strategy by causing the robot to loop endlessly around the cycle or to miss entire sections of the maze. Flood-filling requires the robot to treat the maze as a grid of possible intersections; it populates this grid as it traverses the maze and at every step it floods the maze starting from a particular, known cell. Flooding the maze assigns values to every reachable cell based on how long it would take to reach that cell through known paths, which lets the robot deduce the shortest path from its current location to the cell the flood originated from. This algorithm can require a lot of memory, so storing data compactly is a must when implementing it on the 3pi.

Roboglia 2010 Regional Round

Karandex’s 3pi maze-solver won this competition (in Maharashtra, India) with a time of 6 seconds. This video shows both the winning 3pi and the second-place finisher, which took 16 seconds to solve the same maze. This is a stock 3pi running optimized code.

Maze Solver From Any Location

Moat’s 3pi line tracking robot solves the maze from any starting point. First, the robot learns the entire maze. Then, the robot may be placed anywhere. Once it figures out where it is, it goes straight to the end. The code is available here.