Building a Maze Solving Robot - My Experiences

This year (2001), my parents have assigned me the task of doing a science fair project. After many many brainstorming ideas, I've finally settled on the idea of a project about maze solving robots and algorithms. I read Robot Science and Technology's article about the C* algorithm, with just a little bit of confusion. After 3 readings I still don't get it, so I decided I'd better start off simpler. I've also played around with Maze Bots, and read over their listings of algorithms. After much deliberation I finally decided on 3 different algorithms to do a project on:

This year (2001), my parents have assigned me the task of doing a science fair project. After many many brainstorming ideas, I've finally settled on the idea of a project about maze solving robots and algorithms. I read Robot Science and Technology's article about the C* algorithm, with just a little bit of confusion. After 3 readings I still don't get it, so I decided I'd better start off simpler. I've also played around with Maze Bots, and read over their listings of algorithms. After much deliberation I finally decided on 3 different algorithms to do a project on:

1. Random solving

2. Left/Right wall following

3. A branching search pattern where you return to the last branch after a dead end.

Random Algorithm

This is by far the simplest way of solving a maze. Mind you know, I didn't say best or shortest or fastest, but simplest. You simply have your robot run around making a random decision to turn or not when it encounters a opening to the left or right. The only problem with this, as I mentioned above, is that I will be slow, and there is a good possibility that the robot will not find the exit in the time allotted. I.E. Your robot could wander for hours always taking the wrong turns. Needless to say, it is probably well worth it to invest some programming time into a better algorithm if your looking for speed or accuracy.

Left/Right Algorithm

Ahhh ... the amateur roboticists favorite. The whole principle behind this algorithm is that you can solve any continuous, i.e. no "islands", maze by following either the right hand or left hand wall. This will always get you out, unless the finish is is a "island," like the picture below.

In the above maze, a robot using the left/right wall following algorithm would never reach the exit. This algorithm is just slightly more complex to code, but it's benefits over the random algorithm are large. Simply have your robot turn to the left (or right) whenever it encounters a doorway. Again, the downside of this algorithm is speed. One wall may continue for a long way before reaching the end.

Branch And Return Algorithm

Branch and return is simply a name that I made up. I'm sure there is some technical name, but for now that name will do. This is the most complex out of the three that I have chosen for my project. The principle behind this algorithm is that by exploring each branch of the maze you will eventually find the exit. This algorithm requires that you "remember" when you come to a branch, and begin to record your steps from that branch. After exploring that branch and you come to a dead end, you simple follow your path back to the original branch and take the next turn. This algorithm require much more coding, and some way of knowing your distance and direction, like wheel encoders, or maybe a accelerometer and compass. The problem with this algorithm is that the robot could fall into a endless loop. For instance suppose we had a maze that looked like this:

If the robot is heading from the top of the maze toward 'a' it then may decide to take a right and follow the corridor until it reaches 'b', it then might turn left and reach 'a' again, and then follow back to 'b', and never realize that it is going in a circle. One possible way to combat this is to have the robot take a random corridor when coming to an intersection. Giving the robot a degree of "forgetfulness", i.e. having it forget intersections encountered long ago, could prevent it from being caught in a very long loop.

Concrete - Actual implementation

For my science fair project, I plan on running the same robot through 2 or 3 different mazes for each algorithm, and recording it's time. Personally, I tend to change my robots chassis every few months. The biggest reason for this is that I usually have built the chassis out of legos, and/or tape. This makes for quick ripping apart and rebuilding. I've finally settled on a design that I think I'll keep for a while. I've built my latest robot chassis out of balsa wood. The main body is a 6 x 6 x 0.25 in (15 x 15 x 0.63 cm) flat square.

I've mounted two 4 battery packs on the back end of it, and centered two servers on either side. I secured two 6 x 3 inch balsa pieces together with wood glue and some reinforcing pieces of wood to form the main base. For each servo I built a small box on the bottom that just houses the box of the servo. For wheels, I've used two of the large lego wheels. They can be screwed very nicely to the servo shaft, and the have a excellent grip because of the rubber treaded tires. In the front bottom of the base I've mounted on of Craig Maynards BOBIRD (Brains On Board Infrared Detectors) for central obstacle detection. At the moment I'm having a bit of trouble with the detector seeing the floor. I also plan to place at least two more IRPD sensors on the top front for extra detection, and possible a few on the back for reverse detection. For processing power I'm going to use a OOPic, and possible a Basic Stamp 2. The OOPic's high level programming language makes it much easier than the Basic Stamp's dumbed down language. For distance ranging (if I ever wanted to turn it into a firefighter) I will either mount a Sharp GPDU12 on a servo in the bots middle, for rotational ranging, or stationary at the front of the bot, for frontal ranging. Most likely I'll also mount a breadboard on the bot for easy prototyping (and in my case permanent circuits!). Basically, my whole chassis is held together by Elmer's and wood screws. Next month, I hope to be able to talk a bit about the code and hardware for navagating the maze. Continue Reading ...