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.

Comments

  1. zerobitjack says:

    This is really neat. Thanks for sharing how you did this.

  2. Esteban says:

    I should be doing my work – – but this video is neat. Thanks

  3. Squintz says:

    No Loops?

  4. Renee says:

    Looks like a simple “Turn left” design.

  5. Torby says:

    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?

  6. Hirudinea says:

    Needs Robot cheese, a small rf transmitter it always goes to through the maze.

  7. Raul says:

    Left first is my fave too.

  8. A much simpler robot solving the “turn left” mazes: http://www.youtube.com/watch?v=9CVMRT2JyTs

    Just one MCU :)

  9. t&p says:

    queues and backtracking!

  10. t&p says:

    *stacks and backtracking
    my bad

  11. Jason says:

    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

  12. Patrick McCabe says:

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

  13. Patrick McCabe says:

    Sorry I meant:

    “…bets are off if the robot is not programmed to know where in the grid the *end is.”

  14. DarwinSurvivor says:

    @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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 92,158 other followers