Maze solving robot

Abstract

When a robot navigates a maze, intelligent algorithms are used to plan its path around the maze. Different path-finding algorithms can help the robot exit the maze while possibly traversing the shortest path. In some instances, the robot might not know what the maze looks like before actually exploring it. These algorithms can be also applied to find the optimal path within different environments, such as for a robotic waiter in a restaurant. In this project, we investigate path-finding techniques, in particular the A*, Flood Fill and Modified Flood Fill, to lead a robot from its starting location to its goal within different mazes. Additionally, we use the Offline SLAM approach to localize and map the robot’s position using Particle Filtering while traversing the shortest path extracted. We constructed different mazes with sizes varying from 6 by 6 to 9 by 9 cells, each maze consisting of black cells representing traversable cells and white cells representing obstacles. For mazes whose mapping was known by the robot, we investigated the A* and Flood Fill algorithms. For solving mazes that the robot had never seen before, we investigated the Modified Flood Fill and Flood Fill algorithms. We implemented our solution using a Lego EV3 robot with colour sensors used to detect whether a cell was white or black. The algorithms implemented were designed to run in a simulation as well as on the robot. This allowed us to observe how a robot traverses the mazes using each algorithm and to determine if the shortest path was achieved. For localizing the robot, we ran a simulation where by the robot extracts the shortest path using A* on the maze given. Then the robot traverses the path extracted and localizes itself after each movement using the Particle Filtering technique. The algorithms implemented led the robot to the target destination within our mazes via the shortest paths. In known mazes, A* and Flood Fill recommend the exact same paths. On the other hand, when solving unknown mazes, Modified Flood Fill was far more computationally efficient than Flood Fill, even though both algorithms recommended identical paths from starting location to goal. Particle Filtering localized the robot with a Root Mean Square Error of approximately 0.16 on the x-axis and 0.15 on the y-axis within each maze.