Milestone 3

---

Milestone Goals

Implement a maze navigation algorithm that effectively explores mazes of arbitrary size and configuration, while also updating the GUI.

Navigation Algorithm - Depth First Search (DFS)

• We chose to implement a modified DFS algorithm
• DFS is relatively simple to get working
• DFS does not use very much memory
• Our DFS prioritizes moving straight over turning left or right, as turning takes time
• The robot will continue moving to unexplored grid spaces until it either:
• Hits a dead end
OR
• Encounters only grid spaces it has visited before
• When the robot encounters a dead end (3 walls), it begins backtracking
• Unless the robot has explored everything, there is guaranteed to be some unexplored node along the robot's path
• It will continue retracing its steps until it finds an unexplored grid space
• At that point, it will turn and explore the new area
• To support this, we store the coordinates of each grid node
• This allows the robot to retrace its steps in the opposite direction
• This information is stored in an array that functions as a stack (with a pointer that we change to "pop" coordinates off of the stack)
• When the robot finds that it can only see coordinates that it has encountered before, we move into one of those spaces
• We then search in our traversal stack for the coordinate we just moved into, and pop off everything that came after it
• We then continue reversing our steps as described above
• Below is pseudo-code demonstrating our algorithm

        void dfs(){
          if (forward_unexplored){
            move_forward();
            push_coordinate_stack();
          }
          else if (right_unexplored){
            turn_right();
            move_forward();
            push_coordinate_stack();
          }
          else if (left_unexplored){
            turn_left();
            move_forward();
            push_coordinate_stack();
          }
          else if (only_see_walls){
            turn_around();
            move_forward();
            retrace_steps();
          }
          else{
            move_visited_grid();
            pop_coordinates_stack();
            retrace_steps();
          }
        }

        void retrace_steps(){
          pos = pop_coordinate_stack();
          move_to_coordinate(pos);
          if (see_unexplored)
            dfs();
          else
            retrace_steps();
        }
      

---

Maze Navigation Algorithm Demonstration

This video demonstrates our robot completing all required behaviors:

• Robot capable of maze exploration using DFS
• Robot capable of exploring a maze of size at least 4x6
• Robot capable of updating the GUI during exploration

This video shows our robot exploring a 4x6 maze in a different configuration, still using DFS: