MazeWalker - Beatriz Ramos, João Estorninho

Task

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

Solution

Map Representation

The map was built with black lines of tape so that the robot could follow them and understand the roads and crossings. For the crossings, were 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 is useful to get the "relative turns". As the robot could come from different sides of the crossing (for example from the North instead of South), is necessary to consider the absolute turn value, in order to recognize the same crossing coming from all directions. Two variables (dx and dy) were created to know from where the robot comes.

Data Structures

define afterCrossingDelay 900
define tolerance 1500
define maxNumberOfCrossings 50
define LED 13

uint16_t minv[8]; uint16_t maxv[8]; uint16_t thrd[8]; uint8_t nCross, lastCrossing; uint8_t ct[maxNumberOfCrossings]; uint8_t et[maxNumberOfCrossings][4]; int32_t px[maxNumberOfCrossings], py[maxNumberOfCrossings]; int32_t cx, cy; uint8_t planSize; uint8_t plan[maxNumberOfCrossings];// = {1, 2, 2, 0, 1, 1, 0, 2}; uint32_t timeLastCross; uint16_t s0, s3, s4, s7,s2,s5; uint8_t queue[maxNumberOfCrossings]; uint8_t cameFrom[maxNumberOfCrossings]; uint8_t visited[maxNumberOfCrossings]; uint8_t qwi; uint8_t qri; int8_t dx, dy;

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).