8.a. Solving a Line Maze

The next step up from simple line following is to teach your 3pi to navigate paths with sharp turns, dead ends, and intersections. Make a complicated network of intersecting black lines, add a circle to represent the goal, and you have a line maze, which is a challenging environment for a robot to explore. In a line maze contest, robots travel as quickly as possible along the lines from a designated start to the goal, keeping track of the intersections that they pass along the way. Robots are given several chances to run the maze, so that they can follow the fastest possible path after learning about all of the dead ends.

The mazes that we will teach you to solve in this tutorial have one special feature: they have no loops. That is, there is no way to re-visit any point on the maze without retracing your steps. Solving this type of maze is much easier than solving a looped maze, since a simple strategy allows you to explore the entire maze. We’ll talk about that strategy in the next section.

We also usually construct our mazes using only straight lines drawn on a regular grid, but this is mostly just to make the course easy to reproduce – the maze-solving strategy described in this tutorial does not require these features.

For information on building your own course, see our tutorial on Building Line Following and Line Maze Courses.

An additional resource for understanding simple, non-looped maze solving is this presentation (505k pdf) written by customer (and robotics professor) R. Vannoy. It doesn’t include any code, but it goes over some important concepts and contains a number of visuals to help illustrate the important points.