Maze-solving robot

When a robot navigates a maze, intelligent algorithms are used to plan its path around the maze. These algorithms could be further extended to find the optimal path within different environments, such as a path for a robotic waiter in a restaurant. This project investigates path-finding techniques, in particular the A*, flood fill (FF) and modified flood fill (MFF) to lead a robot from its starting location to its goal, within different mazes.

In some instances, the robot would not know what the maze would look like before actually exploring it. Different path-finding algorithms could help the robot exit the maze, while possibly traversing the shortest path. Different mazes were constructed, with sizes varying from 6 x 6 to 9 x 9 cells. Each maze featured black cells representing traversable cells and white cells representing obstacles.

The A* and FF algorithms were investigated in the case of mazes the mapping of which was known to the robot. On the other hand, for solving mazes that the robot had never seen before, the MFF and FF algorithms we applied. The proposed solution was implemented using a Lego EV3 robot, fitted with colour sensors to detect whether a cell was white or black. The implemented algorithms, which were designed to run in a simulation as well as on the robot, made it possible to observe how a robot traverses the mazes using each algorithm and to determine if the shortest path was followed.

All the algorithms used led the robot to the target destination within the mazes along the shortest paths. In known mazes, A* and FF recommended the exact same paths. However, while both algorithms recommended an identical path from starting point to goal when seeking to solve unknown mazes, MFF proved to be far more computationally efficient than the FF algorithm.