The Concepts Behind Robotic Maze Solving

[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]

14 thoughts on “The Concepts Behind Robotic Maze Solving

  1. 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

  2. @ 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.

  3. @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

Leave a Reply to Andrey MikhalchukCancel reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.