|
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 ...
Powered by AkoComment! |
Categories 
Tags
