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

The algorithm was decomposed in 6 functions.

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

After getting the crossing type, the map is updated adding this new found crossing to 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, the robot take one of them, set the corresponding exit as visited in the 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 movements functions turn90lf(), turn90r(),turn180lf() or turn180r(). If all the exists have already been explored, the value of the plan is checked and if it is different than 0 (check if a plan exists), just calls the followPlan().

On this followPlan() function, the next exit on the plan array is returned and the planSize is decreased (in other words, takes that exit out of the plan as it already took it).

At last, if there is no plan, calls the function constructPlan(). In this function the current cross is picked and looks for neighbors, checking if they have any unvisited nodes. If yes, a plan of turns to reach them is made. If not, our queue is used to put this crossing neighbors and explore them, eventually finding an unvisited node somewhere on the maze (Breadth-First Search - BFS). These decideTurn(), turnAsDecided() and travelToNext() are called in a loop, exiting only if travelToNext() function returns 1 (in other words, maze exit / object found).