Maze Solver Robot, using Artificial Intelligence

STORY

Introduction
This tutorial was developed upon my last project: Line Follower Robot - PID Control - Android Setup. Once you have a robot with line following capabilities, the next natural step is to give him some degree of intelligence. So, our dear "Rex, the Robot" will try now finding how to scape from a "labyrinth" on a shortest and fastest way (by the way, he hates the Minotaurus.

For starting, what is the difference between Maze and Labyrinth? According to http://www.labyrinthos.net, in the English-speaking world it is often considered that to be qualified as a maze, a design must have choices in the pathway. Clearly, this will include many of the modern installations in entertainment parks and tourist attractions, including our 2D maze here. Popular consensus also indicates that labyrinths have one pathway that leads inexorably from the entrance to the goal, albeit often by the most complex and winding of routes.

The majority of mazes, however complex their design may appear, were essentially formed from one continuous wall with many junctions and branches. If the wall surrounding the goal of a maze is connected to the perimeter of the maze at the entrance, the maze can always be solved by keeping one hand in contact with the wall, however many detours that may involve. Those ‘simple’ mazes are correctly known as "Simply-connected" or "perfect maze" or in other words, that contain no loops.

Returning to our project, it will be split in two parts (or "passes"):

(First Pass): The robot finds its way out from a "non-known perfect maze ". Does not matter where you put it inside the maze, it will find a "solution".
(Second Pass): Once the robot found a possible maze solution, it should optimize its solution finding the "shortest path from start to finish".
The video bellow, will show an example of Rex finding its way out. In the first time that the robot explores the maze, of course it will waste a lot of time "thinking" about what to do at any intersection. Testing the numerous possibilities, it will take several wrong paths and dead ends, what force him to run longer paths and perform unnecessary "U-Turns". During this "1st Pass", the robot will be accumulating experiences, "taking notes" about the different intersections and eliminating the bad branches. In its "2nd Pass", the robot goes straight and quickly to the end without any mistake or doubt. Along this tutorial, we will explore in details how to do it:

  Downloand File

Douploads |  uplod

Downloand |  Downloand