This tutorial will help you create an Arduino based robot that can solve basic line mazes that do not have closed loops.
How it works:
The robot is programmed to drive over the black lines of the maze and use optical sensors on the bottom of the robot to track the lines. As it travels along, the program we are using will solve the maze for the shortest path with a simple to understand method called the "Left Hand Rule" or sometimes called the "Left Hand on Wall" method.
The "Left Hand Rule" approach is to make your way through the maze, while choosing how to turn at intersections as follows:
- Always turn left if you can
- If you cannot turn left, go straight
- If you cannot turn left, or go straight, turn right
- If you cannot turn left, go straight, or turn right, turn around because you must be at a dead end
The method of solving the maze for a shorter path is by keeping track of the turns made, and reducing the list of turns as you add the latest turn to the list with known substitutions. The substitutions are three turn combinations where either (L)eft, (R)ight, or (S)traight are on either end of a (B)ack as follows:
- LBR = B
- LBS = R
- LBL = S
- SBL = R
- SBS = B
- RBL = B
For example, from the starting point:
- Start moving
- (L) eft turn is made at found intersection
- Add "L" to list
- Check if last three on list can be shortened: NO, only one turn recorded.
- (B) ack at a found dead end
- Add "B" to list
- Check if last three on list can be shortened: NO, only two turns recorded.
- (L) eft turn again when it finds the initial intersection at which it previously turned left
- Add "L" to list
- Check if last three on list can be shortened: YES.
- Replace "LBL" with "S" traight
- Continue until end point is found.
The path was shortened so it will run the solved path turns when the maze is run again from the start position. From the start, it will now drive straight through the intersection and avoid the dead end.
More about the theory behind various maze solving algorithms can be found here: https://en.wikipedia.org/wiki/Maze_solving_algorithm# #L##/p>
The robot's program will run our example code from an Arduino compatible micro controller. If you are unfamiliar with Arduino, you can learn all about it and download the programming software at www.arduino.cc.