Elevation

The Website of Team 14.

Project maintained by ECE3400-Team14 Hosted on GitHub Pages — Theme by mattgraham

Milestone 3: Maze Search Algorithm

Purpose:

The goal of this milestone was to implement a search algorithm that would allow our robot to traverse an entire maze as efficiently as possible. We start with a simple BFS-like algorithm for constructing movement instructions between squares in the maze, and eventually upgraded our search to implement Dijkstra’s algorith.

Hardware Updates:

Going into this milestone, our robot was using right hand wall-following to traverse mazes. This only requred two wall sensors, a forward-facing and right-facing sensor, to accurately traverse the maze. Before writing our new algorithm, we knew that our robot would need accurate information about the walls on all sides to make informed decisions about where to go next. Therefore, we added a left-facing wall sensor.

With sensors facing forward, left, and right, our robot could determine every wall surrounding it after entering an unexplored square. It can assume that there is no wall behind it because it just came from that square (except at the start, when we assume the robot starts with a wall behind it).

Version 1: Movement Tree Algorithm (BFS)

When first envisioning an algorithm for traversing the maze, we wanted a generalized algorithm that could move the robot between square in the frontier of the maze (i.e. squares that have not been explored yet). Our first idea for doing this was to construct a tree of possible moves (nodes) from a square using Breadth First Search (BFS) through the explored territory of the maze until a new frontier square was reached, then tracing through the tree to create a list of moves for the robot to follow to move to this new location. The algorithm looks like this:

let T be a tree of explored squares in the maze
let v be a possible move for the robot (node)
bfs-moves(T,v):
       let Q be a queue
       Q.push(v)
       while Q is not empty
         v = Q.pop()
         label v as visited
           if v is not in T, construct the movement path to v and return
           otherwise:
              for all possible moves w from v in the maze 
              (priority order: forward, left, right, backwards)
                if w moves to a node not visited by the algorithm
                  Q.push(w)

We created a Node data structure to maintain information about the graph. It stores information about the robot’s location and orientation, the robot’s previous move, and the move required to travel there.

struct Node {
  byte position;      //corresponds to x,y coordinates of the robot
  char move;          //move used to get here 
                      //(forward: 'f', left turn: 'l', 
                      //right turn: 'r', no move: 's')
  byte orientation;   //orientation of the robot at this point 
                      //(North, South, East, or West)
  struct Node* parent;//the parent of this node 
                      //(the previous move)
};

The valid moves that the robot can make in this algorithm are “move forward”, “turn left”, “turn right” and “stop”. The algorithm will find the next unexplored square that requires the least number of moves to reach, prioritized in the order listed. That is, if two unexplored squares are an equal number of moves away, the one that uses higher-priority moves will be chosen.

Once we found an unexplored square, our algorithm traverses the tree back to the starting node, adding the moves at each node to a stack along the way. The final stack contains an ordered list of moves that the robot can follow to get from its current location to the new unexplored node.

  let S be a stack of chars representing robot movements 
  (forward: 'f', left turn: 'l', right turn: 'r', no move: 's')
  let v be a move to an unexplored square
  while (v != NULL) {
    char next_move = v->move;
    S.push(next_move);
    v = v->parent;
  }

These moves can then be executed in order by popping elements off of the movement stack.

while (!S.isEmpty())
  {
    char move = S.pop();
    //have robot perform [move] and update its coordinates and orientation
    performAction(move);
  }

To keep track of unvisited nodes in the bfs algorithm above, we used the arduino QueueList library. We used the StackArray library for generating the stack of moves to be performed by the robot.

Example running movement tree algorithm on 5x4 maze:

 

Advantages and Disadvantages:

While this algorithm was relatively simple to implement and resulted in accurate and somewhat-efficient traversal of the entire maze, we realized that it had some issues:

Version 2: Dijkstra’s Algorithm

Since our algorithm above was already pretty close to Dijkstra’s algorithm, we modified our algorithm to keep track of the “distance” of each node from the start node. The modified algorith is as follows:

let T be a tree of explored squares in the maze
let v be a possible move for the robot (node)
procedure dijkstra(T, v):
        let Q be a queue nodes in the frontier
        L.append(v)
        while L is not empty
           sort Q by shortest distance
           v = Q.pop() //node with shortest distance in Q
             if v is not in T, construct the path to v and return
             otherwise (have not found path to frontier yet):
                for all moves to neighboring nodes w from v in the maze 
                (priority order: forward, left, right, backwards)
                   if w has not been visited yet
                    Q.push(w)
                    else
                     if the path from v to w is shorter than dist(w)
                       update w with path from v

The data structure for Node now has an additional field dist for keeping track of distance from the start node.

struct Node
{
  byte position; //corresponds to x,y coordinates of the robot
  byte move_and_or;    //contains the orientation of the robot 
                       //and move required to get here
  struct Node *parent; //the parent of this node 
                       //(the previous position and move)
  unsigned int dist; //distance from start to [position]
};

Since nodes are now prioritized by distance rather than move, the algorithm does not have to keep track of every individual turn made by the robot. Instead, each node can represent a movement between squares. That is, 'l' now represents “turn left, then go forward” and 'r' represents “turn right, then go forward”. We also introduced new move 't' for going backwards, that represents “turn twice in place, then go forward.” With this new representation of moves, we have condensed the maximum number of moves to store to the number of squares in the maze, and we have reduced the number of individual moves that need to be added to the movement stack.

Instead of the ListQueue we used in the previous algorithm, we used the LinkedList library to store elements. LinkedList features a useful sort function that allowed us to sort the elements of the queue using a comparison function, shown below:

int compare(Node *&a, Node *&b)
{
  if (a->dist < b->dist)
    return -1;
  else if (a->dist == b->dist)
    return 0;
  else
    return 1;
}

Weighing the moves so that a turn has weight 1 and moving forward has weight 2, we get the following maze traversals:

See our source code for the full implementation on our robot.

Running Dijkstra’s algorithm on a 5x4 maze:

 

Traversing the second half of a full 9x9 maze with Dijkstra’s algorithm:

Note: We provided some movement assistance to the robot at certain points due to it getting stuck on the tape, which did not affect the search algorithm. The robot misses a turn at the end (turning around instead of right) but maps the maze accurately because the walls on the path it took are almost identical to the intended path.

 

Map of the 9x9 maze after complete traversal:

maze1