There has been some discussion on the LUGNET Robotics Group lately about building robots that can navigate mazes. There are a number of ways in which the problem can be solved - this is one of them. I demonstrated this device at MindFest 1999 and prepared a tutorial on building a mazewalker in PDF format which you might want to look at for background information.

Introduction

The problem of building a 'bot to navigate a maze is challenging to say the least. Besides the basic problem of building a bot that can navigate accurately, there is the added challenge of designing a maze which is navigable by the robot. At the same time, the designer must figure out how to represent the maze in the robot memory as well as work within the limits presented by the programming environment.

Long ago I figured out that most good ideas have already been developed by others. So I dug out my old CS texts and revisited basic graph traversal algorithms. The old terminology came back rather quickly - node, vertex, cycle, visit, depth, and breadth soon became common words again. Robert Sedgewick's Algorithms in C is one of the cornerstones of any decent collection of CS books, and it provides a treasure chest of really good graph algorithms.

Have a look at the tutorial on building a mazewalker for more detail on the following sections.

Inverting the Problem

If you say "I'm building a robot that navigates mazes" quickly enough - it sounds easy to do. It's not. There are three steps that your robot must perform if it is to truly do its job.

1. It must determine where the boundaries are in the maze
2. It must represent the maze in its memory
3. It must be able to compute an optimum path through the maze

Since the maze is only on paper, I can use a simple light sensor to detect the lines. I know that from the center of any square, I can either move to the next square, or I will hit a wall along the way.

Building the MazeWalker

The mazewalker shown in these photos is built with parts from the RIS 1.0 kit. I added a pair of rotation sensors and micro-motors because they make the device much simpler to work with. Instead of using the rotoation sensors, the touch sensors could be used to sense the LEGO stud bumps and provide very accurate location information, but I didn't think of it until I saw Mario Ferrari's TicTacToe Robot.

There is nothing really complex or interesting about the mechanism, except maybe the gantry assembly. I used inverted beams on either side of the central beam with the gear racks. This allows the gantry mechanism to move smoothly without wheels.

The track mechanism that moves the paper around is equally boring. The yellow tubing across the tracks "presses" the paper down to make sure we get good contact. The steering wheels are there to make it easier to move the gantry and tracks. I had to stick something on the long axles since I ran out or short ones.

Programming the MazeWalker

The real reason for building this device is to demonstrate an application that actaully requires pbForth to run. Most robots can be programmed with the LEGO Mindstorms software or with NQC. The hardy among us might even give LegOS a try. The main thing that this problem requires is a way to represent the maze itself, and that requires some kind of a bitmap. As we all know, variables are few and far between with the exisiting programming environments. Enter pbForth. I was able to easily set up an array to represent the maze. In fact, the maze that this bot can solve is up to 10x10, but it takes rather a long time to do the job. For the demos, I restricted it to a simple 4x4 maze from the tutorial notes.

Each cell in the array is split into two groups of four bits. The four bits represents the walls in each of the four directions that the mazewalker can move in. One group represents the "known" boundaries which are initially all zero - except for the outside walls of the maze. The other group of bits represents the "assumed" boundaries - which are initially all ones. As the robot navigates the maze and discovers walls and openings, it sets known boundary bits and clears assumed boundary bits. When a cell has all of its potential walls mapped, both groups of bits match.

There is, of course, a trick that can be used to simplify the task. Once the boundary between two cells is determined to be a wall or open, then the bits for that boundary in both cells can be set.

The algorithm for the maze walker is fully explained in the tutorial on building a mazewalker. It is a combination of depth-first search to actually build the maze image, and then a modified breadth-first search to find the optimum path between any two squares. I will post the code on this site once it is cleaned up to the point where it is useful.

For more information contact info@hempeldesigngroup.com