[Patrick McCabe’s] latest offering is a well-built maze-solving bot. This take on the competitive past-time is a little more approachable for your common mortal than the micro-bot speed maze solving we’ve seen. Don’t miss seeing the methodical process play out in the clips below the fold.
The playing field that [Patrick’s] robot is navigating is made up of a electrical-tape track on a white background. The two-inch tall double-decker bot is every economical. It uses an RBBB Arduino board to read an optical reflectance sensor array made by Pololu, then it drives a couple of geared motors using an L293D h-bridge breakout board. But we already know that [Patrick’s] a talented robot builder, this time around we’re happy to see his in-depth discussion of how to program a robot to solve a maze. In it he covers all of the different situations your robot might face and how to deal with them. Once you’ve dug through all of the concepts, dust off that bot you’ve got lying in the corner and start writing some new firmware.
[youtube=http://www.youtube.com/watch?v=2FF6ceCI0kc&w=470]
[youtube=http://www.youtube.com/watch?v=MLHeUEPLSAY&w=470]
This is really neat. Thanks for sharing how you did this.
I should be doing my work – – but this video is neat. Thanks
No Loops?
Looks like a simple “Turn left” design.
Um. So once it’s learned a maze, what happens if you put it somewhere else, or in a different maze? Does it recognize this isn’t what it remembers and go back to searching?
Needs Robot cheese, a small rf transmitter it always goes to through the maze.
Left first is my fave too.
A much simpler robot solving the “turn left” mazes: http://www.youtube.com/watch?v=9CVMRT2JyTs
Just one MCU :)
queues and backtracking!
*stacks and backtracking
my bad
Unfortunately, this “left hand on the wall” method of solving a maze will often-times not work, especially in a competitive environment. Maze designers will most certainly not build a puzzle in which this method will work.
Imagine a maze with a ring around the outside edge. The method mentioned in his article simply will not work, as the bot would just go ’round and ’round… never making a right turn unless forced to at the edges.
A much more common method for maze solving robots is the ‘flood-fill’ or ‘modified flood-fill’ algorithm.
Here is a pretty decent write-up of the method:
http://www.micromouseinfo.com/introduction/floodfill.html
@ Jason
You are correct that this left hand on the wall method does not work on mazes with loops. That is something that is pointed out in my article.
I have looked a little into flood fill and it appears that the robot has to be programmed to know where the end of the maze is. In these competitions normally the maze is setup in a grid and the end is in the center. If the ending is anywhere in the maze then I believe all bets are off if the robot is not programmed to know where in the grid the maze is. I could be wrong because I have only read a little on it.
Sorry I meant:
“…bets are off if the robot is not programmed to know where in the grid the *end is.”
@McCabe You could also stick to a left-turn system but have the robot log where IT has been in the maze (timing distance between turns should work if the grid is spaced out enough). Then if the robot senses that it is about to repeat a direction, it would check if it had checked all directions at all intersections since it’s first time going that direction at that point and force a new direction if it had exhausted that area. A fair bit more logic involved, but probably still doable on a micro-controller