Problem 1 --- State-Space Search Representation

(a) Formulate this problem as a state-space search problem Give a precise definition of a state, the start state, the goal state or goal condition, and the operators. Operators should be specified as "schemas" that indicate for a given state, when the operator is legal (i.e., a set of constraints on when the operator can be applied to an arbitrary state) and the description of the successor state after the operator is applied. In other words, each operator should be specified in a way that it would easily implemented in a program to solve this problem.

(b) Show the State Space
Draw the complete state-space graph that includes all nodes (and legal directed arcs connecting these nodes) for this problem. Inside each node show the state description, and label each arc with its associated operator. Highlight a path that gives a solution to the problem.

Problem 2 --- Using various search techniques

(i) For each of the search strategies listed below, (a) indicate which goal state is reached if any, (b) list, in order, the states expanded, and (c) show the final contents of the OPEN and CLOSED lists. (Recall that a state is expanded when it is removed from the OPEN list.) When all else is equal, nodes should be expanded in alphabetical order.

1. breadth-first
   
2. depth-first
   
3. best-first (using f = h)
   
4. A* (using f = g + h)
   
5. RBFS (using f=g+h) --- due to the fact that RBFS is a recursive algorithm give the search tree as your answer for RBFS!
6. SMA* (using f=g+h and limiting the open-list to just 3 elements)
   

General Pseudocode for Searching

  OPEN   = { startNode } // Nodes under consideration.
  CLOSED = { }           // Nodes we're done with.

  while OPEN is not empty
  { 
    remove an item from OPEN based on search strategy used
    - call it X

    if goalState?(X) return the solution found

    otherwise // Expand node X.
    {
      1) add X to CLOSED
      2) generate the immediate neighbors (ie, children of X)
      3) eliminate those children already in OPEN or CLOSED
      4) add REMAINING children to OPEN
    }
  }
  return FAILURE  // Failed if OPEN exhausted without a goal being found.

  OPEN   = { startNode } // Nodes under consideration.
  CLOSED = { }           // Nodes we're done with.

  while OPEN is not empty
  { 
    remove an item from OPEN based on search strategy used
    - call it X

    if goalState?(X) return the solution found

    otherwise // Expand node X.
    {
      1) add X to CLOSED
      2) generate the immediate neighbors (ie, children of X)
      3) add all children to OPEN
    }
  }
  return FAILURE  // Failed if OPEN exhausted without a goal being found.

Problem 3 --- Compare RBFS and A*

Problem 4: A* Termination

Problem 5: Using Various Search Techniques to Solve the Travelling Salesman Problem (TSP)

Problem 6: Questions concerning Adversarial Search