COSC 6368 (Dr. Eick) in Fall 2017
Homework1 (Individual Homework)
First Draft

Assigned: 10/3/2017
Last Updated: 10/6/2017
Due: 10/17/2017 at 11p

Problem 1: State-Space Search Representation

The "3 Missionaries and 3 Cannibals Problem" is defined as follows. Three missionaries and three cannibals are standing on the left bank of a river. There is a small boat to ferry them across with enough room for only one or two persons. Exactly one or two persons must be in the boat each time it crosses the river in either direction. An indivisible action corresponds to one or two people getting into the boat, moving across the river, and then all passengers disembarking the boat. The goal is to get all 6 people across the river. If ever there are more missionaries than cannibals on either side of the river, the missionaries will convert the cannibals. Find a sequence of crossings to transport safely all the missionaries and cannibals across the river without exposing any of the cannibals to conversion.

(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 general state, when the operator is legal (i.e., a set of constraints on when the operator can be applied to an arbitrary state, which is given as an n-tuple) and the description of the successor state (given as an n-tuple that is completely specified from the previous state's n-tuple and the parameters associated with the given operator) 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: Apply Various Search Techniques to the Same Search Problem

Assume that you have the following search graph, where S is the start node and G1 and G2 are goal nodes. Arcs are labeled with the cost of traversing them and the estimated cost to a goal is reported inside nodes.

Search Space for Problem 2 of HW1

(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. SMA* (using f=g+h and limiting the open-list to just 3 elements)

General Pseudocode for Searching

The following is the basic outline of the search strategy used for breadth-first, depth-first, and best-first search algorithms. 

  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.
The following is the basic outline of the search strategy used for the A* and SMA* search algorithms. 

  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: A* Evaluation Functions

What characteristics should a good evaluation function h for A* have? Give reasons for your answer!

Problem 4: Real-Time Labyrinth Search

Assume you have to search a labyrinth of interconnected rooms trying to find a particular room that contain a red flower. There will be many intersections of walkways that connect rooms all of which look completely the same and are not distiguishible; you will not know if you entered a particular crossing before; however, you will be given a piece of chalk that allow you to mark the to put signs of your own choosing on a wall. Devise a search strategy that will find a room with a red flower assuming that such a room exists. Describe your seach strategy clearly! Explain why your search strategy will find a red flower, assuming that the labyrinth is finite!

Problem 5: Questions concerning Adversarial Search

(a) Assume alpha/beta search is applied to the following game tree, listed below:
Search Space for Problem 2 of HW1

Two 2 versions v1 and v2 of alpha/beta search are used:
(v1) enumerating leaf nodes from left to right
(v2) enumerating leaf nodes from right to left
Will versions v1 and v2 always select the same move, if there is a single best move? Will version v1 and v2 always have the same runtime? Give reasons for your answers!

(b) Most game-playing programs do not save search results from one move to the next. Instead, they usually start completely over whenever it is the machine's turn to move. Why?

Problem 6: Constraint Satisfaction Problems

Consider the problem of placing k nights on a nxn chessboard such that no two knights are attacking each other; k is assumed to be less than n**2.
a. Choose a CSP formulation. In you formulation, what are the variables?
b. What are the possible values of each variable?
c. What sets of of variables are constrained on how?
d. Now give a sketch of a search strategy that solves this problem for a given k value or reports that it is infeasible.

Problem 7: Planning

Assume the following state of the Boxworld is given:

Box World1

Describe (outlining all partial and complete plans generated and explaining why they are generated and also giving the goal-subgoal tree(s) for the final plan) how a STRIPS-like (or NOAH-like, if you prefer that) classical AI planning system will come up with a plan that accomplishes the following goal, assuming that the depicted state is the initial state:

on(F,C) and on(A,F)