Part 1: What is a Line Maze?

As a class project, and to help my students learn about robotic algorithms, I decided to design and build a Line-Maze Solving Robot. The documentation for this project grew rapidly, and became too long to comfortably fit on "one page", so I decided to split this into sections. Use the links below to cruise around.

1.1 What is a Line Maze?

1.2 Definitions

1.3 Islands or Loops

1.4 Rules

1.5 A Basic Algorithm (System) for Solving a Maze

1.1 What is a Line Maze?

Here are some photos of line mazes I have created with a brief description of each.

Figure 1-1: My First Line Maze

Figure 1-1 shows the first line maze I constructed. This is a standard, large classroom white board with 3/4 inch electrical tape for lines. The contest using this maze required a robot to start at the open rectangle at the top-right of the photo and navigate, using the black lines, to the "finish line" or the black rectangle at the bottom-right.

Figure 1-2; A Small, Portable Maze

Figure 1-2 shows a small portable maze I built in 2008. Notice the retangular cut-out at the bottom-center that is my carrying handle. I made a line maze on this side of the board and an oval race track on the other side of the board. This way, I could travel from classroom to classroom and bring along a robot to display and demonstrate for both line following and line maze contests. This course is on a 2 X 4 foot piece of plywood and to get an idea of scale and size, all of the intersections are 6 inches apart. The small upside-down "T" at the bottom left is "Start" and the black rectangle at the bottom-right is the "Finish".

Figure 1-3: The Monster!

Last year, my students were working on using the 3PI robot (Pololu.com) which was considerably faster than the Parallax BOE-Bot and other servo driven robots. They wanted a challenge, and specifically a maze that would reward the robot who could attain the fastest speed. Notice the long straightaway down the center. This allowed a "smart" robot to accelerate rapidly here and on the other fairly long straight sections on either side of the maze. As above, the intersections are six inches apart. The total length of the shortest path to the finish is 27 feet, and the team shown here completed this maze in the incredible time of thirteen seconds!!

Here is the You-Tube video showing the team in the photo above winning the line maze contest.

1.2 Definitions

Only a few of the definitions needed to get you started are covered here. For a complete list of definitions for mazes, go to astrolog.org.

Most maze solving robots operate in "Perfect" mazes or mazes with no loops.

Loop

A path that connects with itself forming a circle (or a path where the robot can go around the same path continually and never get to the end of the maze.)

Maze

A network of interconnected passages meant to be a challenge to navigate from start to end. Today this most often means a non-unicursal intellectual puzzle. Comes from the Old English word to confuse or confound.

Perfect Maze

A Maze without any detached walls and without any isolated sections. A perfect Maze always has exactly one solution, and there is always exactly one unique path from any point in the Maze to any other point in the Maze.

Simply Connected

A Maze without any loops.

Shortest Path

The Holy Grail of Maze solving. A shortest path is a solution such that no other solution path in that Maze has a shorter length. A Maze can have more than one shortest path.

Solution

A path in a Maze from start to finish.

Solve

The act of finding the solution to a Maze.

1.3 Islands or Loops

Islands or loops in a maze are passageways that allow the robot who always goes one direction, say left, at intersections, to wind up going around and around the same loop forever, thus not ever solving the maze. This type of loop is generally not used in line maze contests. If it is used, it is stated clearly in the rules since the strategy for solving a maze is more complex and considerably different from the "Simply Connected" maze.

1.4 Rules

For now, I will provide the simple rule set. Later I will expand on this and provide some links.
Most maze solving contests have a set of rules that boils down to: The robot who can navigate from the Start to the End of the maze in the shortest time is the winner. Robots are usually allowed two or three runs through the maze to get their best time.

1.5 A Basic Algorithm (System) for Solving a Maze

1.5.1 One of the most common methods for solving a maze is called the wall follower rule which can use the right-hand rule or the left-hand rule. Put one hand on the wall inside the maze and start walking. If the maze is simply connected and has no loops (see definitions above), then you will always get to the end of the maze. See this Wikipedia page for a more detailed explanation of maze solving algorithms.

To successfully traverse a line maze, a robot needs to develop several behaviors:

These behaviors are needed just to travel around the maze:

• How do I travel quickly along the straight portions of the track?
• How do I determine if I have reached an intersection?
• How do I know which way to turn at any intersection?
• How do I know when I have reached the end of the maze?

And these behaviors are required if the robot is to become "smarter" as a result of going through the maze:

• How do I ignore dead-end paths once I have discovered them?
• How do I find the shortest/quickest way to the Finish?
• How do I travel quickly when I can?
• How do I negoitiate turns efficiently and quickly?

1.5.2. Strategy: In most maze solving contests, the rules allow the robot to make two or three runs through the maze, and the winner is the robot that can solve the maze in the shortest time. There are a number of ways to do this, but typically, the robot sets up a strategy that will allow the robot to solve the maze in two passes through the maze. Something like this:

In the first pass, the robot has no choice but to go down a number of dead-end paths as it learns the maze. If the robot can travel at a relatively high speed, this first pass is usually at a lower speed to help with accuracy. The main task on this pass is to record all turns and apply an algorithm that can deduce and plan the shortest path from Start to End.

The basic sequence for the first pass is:

• Navigate to a dead-end or an intersection
• If an intersection, record the type and take highest priority turn available. Turn priorities for a left-hand rule robot are: 1) Left Turn 2) Go straight 3) Go Right.
• If a dead-end is encountered, 'unwind' or correct the last turn since it was bad.
• Continue this sequence until the end of maze detected.
• At this point, a correct sequence of turns to be made should be stored in memory.

For pass two, the robot retrieves the stored information which provides the correct direction to proceed at each intersection to complete the maze in the shortest possible path.

The second or third pass, if allowed provides an opportunity to try a range of special programming skills that will improve the overall run time.