MazeWalker - Beatriz Ramos, João Estorninho

Task

On this project, we built a maze with black tape and the main goal was to make our robot follow the tape lines and explore the maze until it finds an object/obstacle.

Solution

Map Representation

Our map was built with black lines of tape so that the robot could follow them and understand the roads and crossings. For the crossings, we used binary representation with 3 bits:

-The most significant represent the existence of a road on the left;

-The middle one represent the existence of a straight road;

-The less significant bit represent the existence of a road on the right.

This was how we got our "relative turns". As the robot could came for other side of the crossing (for example from the North instead of South, we had to consider the absolute turn value so that we could recognize the same crossing coming from other directions as well and so, we used two variables (dx and dy) to know where in the compass rose.

Data Structures

Algorithm

Our algorithm was decomposed in 6 functions.

Our main function was solveMaze() which called all the other auxiliary functions needed. Firstly, in the solve maze, the robot walks to the next crossing calling the travelToNext() function, leading us straight to the next crossing. Then, using discoverCrossingType(), is returned the type of crossing found once it recognized a crossing in its way.

After we get the crossing type, the map is updated adding this new found crossing to our data structures (ct, py, px and et). If already exists similar coordinates (which could be the same with a small error, comparing with a sensible value of tolerance) from a previously found crossing, its coordinates are readjusted.

After the updateMap(), the function decideTurn() is called. This is the most complex auxiliary function. Once called, it has 3 nested functions with 3 options to take. The first option is if there are any unvisited exits. If yes, we would take one of them, set the corresponding exit as visited in our et array, reset the plan to zero and take that turn with the turnAsDecided() function. This function turnAsDecided() receives the information where to turn and calls our movements functions turn90lf(), turn90r(),turn180lf() or turn180r(). If all the exists have already been explored, we check the value of the plan and if it is different than 0 (check if we have a plan), we just call the followPlan().

On this followPlan() function we just return the next exit on the plan array and decrease the planSize (in other words, we take that exit out of the plan as we already took it).

At last, if we do not have a plan, we call the function constructPlan(). In this function we pick our current cross and look for neighbors checking if they have any unvisited nodes. If yes we make a plan of turns to reach them. If not, we use our queue putting this crossing neighbors into our queue and exploring their neighbors, eventually finding an unvisited node somewhere on the maze (Breadth-First Search - BFS). This decideTurn() and turnAsDecided() and travelToNext() are called in a loop, exiting only if travelToNext() function returns 1 (in other words, maze exit / object found).