Milestone 3: Maze exploration

Goals

  • Explore maze using DFS, BFS, Dijkstra, or A* (show that your robot can do different maze configurations, we expect at least one of them to be a minimum size of 4x5).
  • Update the GUI while exploring.

Our algorithm

To explore the maze, we decided to not use Depth First Search (DFS) or Breadth First Search (BFS). Instead, we used a combination of both, known as Iterative Deepening Search (IDS). This algorithm combines the spatial efficiency of DFS and the speed of BFS for those nodes that are closer to the root. Additionally, it uses less memory, which is instrumental at this point of the course, since we have a considerable amount of code already. For more details, you can visit this website.

Translated to robot-world, that would mean that every time we call IDS, DFS is limited to a certain depth. Hence, the algorithm performs DFS with a BFS flavour. Refer to the image below for a graphical representation of how the nodes would be explored:

The full code for this section was rather long. Click here to see it in our code repo.

We first tried on a 3x4 maze:

Then, we changed the configuration of that maze:

Finally, we tried a 4x6 maze that also has a node that could't be reached by using right hand following, proving the robustness of our code:


Radio communication

Most of the radio communication was already done in Lab 3. See below how our robot is also capable of updating the GUI through the remote Arduino station via radio communication.

Click here to see full code for this part