This machine is basically being designed to implement the algorithms into physical objects i.e by making autonomous robots. This basically follows the concept of backtracking as the famous rat and cheese maze formula. Apart from that various optimization techniques are used here such as finding the least path by traversing the entire maze for the first time and then remembering the edge cost for each possible path and in the second go it will give you the most optimal solution.
Unlike my previous maze solving robot, this autonomous bot is mounted with ultrasonic range finding sensors, which gives the distance values from three directions simultaneously. These data are then used for mapping and go as an input to our main algorithm which uses these data for finding a path.
The wheels are mounted on motors with encoders that keeps records of the distance moved by the bot in a particular direction. This data is very useful while backtracking of the bot from any dead end.
There are basically 2 steps. The first is to drive through the maze and find the end of it. The second is to optimize that path so your robot can travel back through the maze, but do it perfectly without going down any dead ends.
I use a technique called the left hand on the wall. Imagine you are in a maze and you keep your left hand on the edge of the wall at all times. Doing this would eventually get you out of a non-looping maze. This instructable will only deal with mazes that do not loop back on themselves.
This left hand on wall algorithm can be simplified as follows: - If you can turn left then go ahead and turn left, - else if you can continue driving straight then drive straight, - else if you can turn right then turn right. - If you are at a dead end then turn around.
The robot has to make these decisions when at an intersection. An intersection is any point on the maze where you have the opportunity to turn. If the robot comes across an opportunity to turn and does not turn then this is considered going straight. Each move was taken at an intersection or when turning around has to be stored.
The optimisation follows the principle of traversing the entire maze at once using any traversal algorithm like Breadth First Search or Depth First Search which includes backtracking form the dead ends and recording everything in the Stack Data Structure. The data obtained from the backtracking is used as a reference for path optimisation.