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 it and understand the roads and crossings. For the crossings, we used binary representation with 3 bits, the most significant represented left and if there was a road on the left or not, the middle one represented if there was a straight road or not and the less significant bit the right side if there was a road or not. 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 wind rose.

Data Structures

Algorithm

Our algorithm was composed mainly of 6 functions. Our main function was solveMaze() which called all the other auxiliar functions that we needed. First in the solve maze, the robot walked into the next crossing calling the travelToNext() function leading us straight to the next crossing, getting to the discoverCrossingType() which returned the type of crossing found once it recognized a crossing in its way. After we get the crossing, we needed to update the map, adding this new found crossing to our data structures (ct, py, px and et) or correcting his coordenates if we found some similar coordenates of a known crossing which could be the same with a small error (comparing with a sensible value of tolerance). After the updateMap(), the function decideTurn() was called. This is our most complex auxiliar function, once called it has 3 function nested with 3 options to take. The first option was if there were unvisited exits, if there were, we would take one of the unvisited, set the corresponding exit in our et array to 1, 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 there wasn´t any exit unvisited, we check the value of the plan and if it is different than 0 (means 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 neighbours checking if they have any unvisited nodes, if yes we make a plan of turns to reach them, if not, we user our queue putting this crossing neighbours into our queue and exploring their neighbours, eventually finding an unvisited node somewhere on the maze. This decideTurn() and turnAsDecided() and travelToNext() are called in a loop exiting only if travelToNext() function returns 1 ( in other words, maze exit found).