private ArrayDeque<Action> searchForGoal(SearchGoal g){
    // We keep track of potential paths in a queue.
    ArrayDeque<PartialPlan> fringe = new ArrayDeque<PartialPlan>();

    // We don't want to re-expand a given node, so we put it into the closed
    // set.
    Hashtable<Position, Boolean> closedSet = new Hashtable<Position, Boolean>();

    // We start off with a PartialPlan at the current position of the ant.
    PartialPlan start = new PartialPlan(new Position(this.x, this.y));
    boolean debug = false;
    if(debug)
      System.out.println(map);

    // We add our starting plan to the fringe.
    fringe.push(start);

    // If the fringe is ever empty, then we have exhausted all possibilites.
    while(!fringe.isEmpty()){
      // The current partial plan we are considering.
      PartialPlan consider = fringe.remove();

      // The map tells us the possible moves. (We wont plan to move into unknown
      // areas.
      Move[] successors = map.getPossibleMoves(consider.getX(), 
                                               consider.getY(),
                                               hasFood);
      Collections.shuffle(Arrays.asList(successors));
      // We make sure that the current position hasn't been considered yet, and
      // if it has, we continue to the next one.
      if(closedSet.put(consider.getPosition(), true) == null){
        // If we are at the goal, then we are done.
        if(g.isGoal(consider.getPosition())){
          return consider.moves;
        }
        // Add all of the successor states to the fringe.
        for(Move successor : successors){
          PartialPlan newPlan = consider.planWithMove(successor);
          fringe.add(newPlan);
        }
      }
    }

    // The only plan that can't return null is the unknown search.
    if(g.planName().equals("the unknown") && false){
      // The fringe is exhausted, so we choose a random direction from our list 
      // of possible directions.
      System.out.println("No path to " + g.planName() + 
                         " found. Using fallback");
      ArrayDeque<Action> backup = new ArrayDeque<Action>();
      Move[] p = map.getPossibleMoves(x, y, hasFood);
      int index = (int)(Math.random() * p.length);
      backup.add(p[index].getAction());
      return backup;
    }else{
      return null;
    }
  }