Wall Following Robot in a Maze

Note:- This is an assignment for ENPM809Y course at UMD for MEng in Robotics degree and might contain some information given by professor to test run the cpp code

This program consists of implementing the “wall following” algorithm to drive a robot to a goal. The goal is always reachable and is always adjacent to one of the 4 outer walls of a maze. For this program we will need to use a third-party library which provides a simulator to visualize the outputs of your program. This simulator also provides functionalities to detect walls, set walls, change the color of cells, and set text.

The simulator used in this assignment can be found at https://github.com/mackorone/mms and this simulator makes use of Qt and hence it must be installed before building the simulator

We can configure the maze simulator to use our c++ code in the following way:

The mouse settings can be configured as given below:

The Wall following Algorithm

The purpose of this program is to make the robot traverse through the maze and by either following the left or right wall depending on passed parameter.

By left hand rule, we are trying to indicate the following algorithm, where G represents the Goal coordinates:

The expected output from Left hand Rule and Right hand Rule algorithm:

Making use of functions such as moveForward(), turnLeft() and turnRight(), we are able to move the robot respectively, however the complexities lies where we need to keep a track of direction and accordingly make the robot move in the required direction. The robot starts at (0,0) and faces north.

The directions of this 16x16 maze is represented as follows:

Detecting the walls

We need to detect walls so we can redirect the robot and this can be done by making use of wallFront(), wallRight() and wallLeft() function

Setting walls

Once we are able to find a wall, we want to set walls with method setWall(int x, int y, char direction). This is where the direction becomes critical and hence we need to maintain a record of direction on every turning right and left. In this particular problem, we need to set walls whenever they are detected as an obstacle.

Implementation

1. Wrote a function to generate a random goal. Keeping the condiiton that if the X coordinate of the goal is 0 or 15 then its Y coordinate is a number between 0 and 15. If the X coordinate is not 0 or 15, then its Y coordinate is 0.
2. Set the outer walls using the method Simulator::setWall(). Set the walls using a double for loop.
3. Wrote code for the robot to return back to origin, taking the shortest path and skipping the repetitive path as indicated below:

In the below image, we are using left-hand rule approach to reach final goal and get back taking shortest path:

Left-hand rule approach:

Right-hand rule approach:

Additional code documentation can be found in the Doxygen produced documentation revealing the different classes and their methods