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, starting from any place of the maze. The fact that the start point is not fixed leads the robot to map the maze in order to avoid being trapped in loops.

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

These are the data structures used:

maxNumberOfCrossings = 50 uint8_t ct[maxNumberOfCrossings] : an array to save the cross type of each crossing;

uint8_t et[maxNumberOfCrossings][4] : a matrix to save exits taken from each crossing;

int32_t px[maxNumberOfCrossings], py[maxNumberOfCrossings] : arrays to save coordinates of each crossing;

uint8_t nCross, lastCrossing : number of crossings discovered and last one discovered;

int8_t dx, dy : current direction (dx = 0 and dy = 1 => North);

uint8_t plan[maxNumberOfCrossings] : constructed plan to follow;

uint8_t planSize : plan's size;

uint8_t queue[maxNumberOfCrossings] : queue to apply breadth-first search, in order to find crossings to explore;

uint8_t qwi, qri : pointers to write and read from the queue;

int32_t cx, cy : current coordinates;

uint16_t minv[8], maxv[8], thrd[8] : used during calibration;

uint32_t timeLastCross : coordinates are calculated based on time occurred between travel from one crossing and next one found;

uint8_t cameFrom[maxNumberOfCrossings] : to save directions already explored in each crossing and used for backwards reconstruction of the path (after the BWS -Backward Search- discovers a new location with unvisited exit);

uint8_t visited[maxNumberOfCrossings] : to save crossings already visited during BWS.

Algorithm

The robot program has the option of calibration of all sensors. Saves its thresholds to the EEPROM and automatically loads them when started.

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