This project made use of an autonomous mobile robot to solve an unknown maze and find the shortest path from the starting point to the finishing point. The programming of this robot entailed two main algorithms: the wall-following algorithm and the path-finding algorithm.
The implementation of a wall-following algorithm was considered essential because it would enable the robot to navigate through the maze without colliding with any walls. The robot was equipped with three ultrasonic sensors. Two of those sensors were located at the front and rear ends of the robot and they could be rotated to face whichever wall the robot might need to follow, be it to the left or to the right. The readings of both sensors were then used to calculate the distance of the robot from the wall. The wall-following algorithm was designed such that the robot could maintain a constant predetermined distance from the wall while moving forward. This means that the robot could travel in a straight line, in parallel to the walls on its sides. This enabled it to avoid collisions with the walls on both sides. The third sensor was stationary and placed at the front end of the robot, facing forward. This sensor was fitted in order to detect a wall in front of the robot, thus preventing frontal collisions.
While the wall-finding algorithm would allow it to travel smoothly through the maze, the robot would also need assistance in finding the shortest path to the finishing point. Hence, it was programmed with a path-finding algorithm, which allowed it to map out its surrounding walls as it traversed the maze, while simultaneously finding the quickest route to the finishing point.
Since the path-finding algorithm would perform in real-time as the robot moves through the maze, it would be possible for the robot to solve a maze which is entirely new and unmapped. Being also supported by the wall-finding algorithm, the robot could do so without colliding.
Figure 1. The robot that was used for this project
Figure 2. An example of a maze that the robot could solve
Student: Justine Pisani
Supervisor: Prof. Matthew Montebello