Goals
• To have robot capable of maze exploration using DFS, BFS, Dijkstra, or A* • To have the robot be able to update the GUIDepth-First Search
Algorithm
We decided to implement depth-first search as our maze exploration algorithm. Because we do not need to determine the shortest path to a certain point, we decided that breadth-first search wastes time backtracking back to nodes; depth-first search is a far better algorithmic option when our goal is simply to discover and visit all spaces in the maze.
The main difference in how our robot moves with DFS is its acknowledgement of previously explored intersections. Originally, wall detection was the only source of information used in direction selection. With DFS, our robot now keeps track of all previously explored intersections using a 9x9 array, and when wall detection results in more than one possible path, this exploration array is accessed. If any directions are unexplored, they will be given priority over any explored directions.
This algorithm gives our robot the ability to explore an entire maze, when originally it could easily get stuck traversing the same section of a maze repeatedly. Generally, our robot will travel normally (wall following), reach a dead end, make a u-turn, travel back to the most recent node (intersection with more than one possible direction), traverse an unexplored path, and repeat. A matrix will remember the This results in an effective depth-first search and full exploration of any maze up to 9x9.
In this code, once the intersection is determined, the robot checks each potential wall location for a wall. When there is not a wall, that location is encoded as a possible direction.
Once each possible wall location is determined, the function determine_dir() is called to determine the next direction the robot should go in. From each possible direction you could go in, the new direction and x and y coordinates are determined, and then checked against the matrix which holds each coordinate and whether or not it was visited.
Implementation
We then tested our algorithm on a variety of maze layouts, the footage of which we have documented below. This includes the GUI receiving information about the maze.
The first maze was a simple 2x3 maze with one wall:
The second maze was also a 2x3 one, this time with two walls:
Our final maze layout was a 4x5 maze with a long L-shaped wall. This time, the robot had trouble at a few intersections due to a a slightly more uneven surface making the line sensors touch the ground. Notably, this occurred at the last intersection, so we intervened to get our robot back on course:
Here is a closeup of the GUI result for the 4x5 maze. The extra wall detected near the final intersection was due to our aforementioned intervention when the robot had trouble with an intersection:
