Milestone 3

Part 1: Determining Search Algorithm

We considered a couple search algorithms for inspiration for searching our maze. Here are some of the methods we considered, and how we could use them.

• Flood fill
• This is used in Paint to fill open spaces with a given color. We considered this because if the maze was sparse, ie not many walls, a depth first search might lead to more backtracking
• We decided to not use this method because it would work well only for open spaces, and if we had dense walls it would not be worth implementing.
• Breadth-first search
• We decided against this method because, unlike computerized exploration, we need to backtrack after every exploration, and this would take too much time
• Depth-first search
• We selected this algorithm!
• Using this algorithm, our robot will continue along a path until it cannot continue. We considered two algorithms to implement this, as shown below. We selected the cardinal direction method because it is conceptually more clear to debug.
• If we cannot continue to unexplored blocks, we backtrack to the last block where we could have branched to an unexplored block.
• We saved our path by saving the previous location at each explored block, so that we move to previous blocks.

Part 2: Testing the Algorithm

To explore the effectiveness of the algorithm, we wrote a Matlab simulation based off of 2017 Team Alpha’s work. This is a simplified version of what is on the Arduino because we don’t need to consider the turning logic. The videos below show the simulation running on two different 4x5 maze configurations.

Part 3: Implementing on the Arduino

To make this algorithm consume as little memory as possible, we used a bitfield struct to store all the information needed to run the algorithm. Bitfield structs trade processing speed for memory efficiency, but since the expected number of accesses per iteration is low, this is a good tradeoff to make:

  struct{
    unsigned int north: 1;
    unsigned int east: 1;
    unsigned int south: 1;
    unsigned int west: 1;
    unsigned int visited: 1;
    unsigned int lastD: 2;
    unsigned int reserved: 1;
  };

Each struct represents a square in the maze, and the struct stores the locations of the walls in the square, whether the square has been visited, and the direction the robot came from when it entered the square, for use in backtracking. By using a memory efficient implementation, we can store the information of the entire maze in the arduino in 81 bytes.

To traverse the maze, the arduino must make a turn at every intersection in order to see every wall, because there are only two sensors on the robot. The robot then writes the locations of the walls into the maze memory structure, and uses walls and visited squares to make a move toward an unvisited square. If all adjacent squares are visited or walled off, the robot initiates a backtrack to look for a new unvisited path. Displayed below is a video of our maze algorithm working on the robot and updating the GUI: