CSE 415: Introduction to Artificial Intelligence Winter 2006

Ch 5-6 Exercises

• Problem 5.5 (a) Rectilinear floor-planning: The problem is to find nonoverlapping places in a large rectangle for a number of smaller rectangles. Formalize the set of variables, the sets of possible values, and the constraint relation.

• Problem 5.8 Use the AC-3 algorithm (Fig. 5.7) to show that arc consistency is able to detect the inconsistency of the partial assignment {WA = red, V = blue} for the problem shown in Figure 5.1. Because the constraints are undirected arcs, the algorithm would require us to consider BOTH directions of each arc, making your work lengthy. Luckily Tyler has figured out which arcs and directions are important, so you just need to fill in the following table. That is, instead of following the queue order of arcs that would result from the AC-3 algorithm in the book, you should use the arc order of the table below, which was chosen to keep the problem short (the queue ordering results in lots of steps where no changes are made). Other than the order in which the arcs are explored, you should follow the algorithm as it is in the book by filling in the table with the possible values at each step, and indicating when the inconsistency has been detected.

  *	WA	NT	SA	Q	NSW	V	T
  Initial	R	RGB	RGB	RGB	RGB	B	RBG
  SA-WA
  SA-V
  NT-SA
  NT-WA
  Q-NT
  Q-SA
  NSW-V
  NSW-SA
  NSW-Q

• Consider the following subgraph isomorphism problem. The binary relation F has the following pairs: F={(1,3)(1,4)(2,1)(3,2)(4,3)(4,5)}. The binary relation G has the following pairs: G={((A,C)(A,D)(B,A)(C,B)(C,F)(D,C)(D,E)(F,E)}. We want to find a subgraph isomorphism (like on CSP lecture slide 15) from the variables {1,2,3,4,5} to the values {A,B,C,D,E,F}. The constraint relation R is given by:

  R = {(i,v,j,v') | if (i,j) is in F then (v,v') must be in G and if (j,i) is in F then (v',v) must be in G}

  This says that if i and j are connected by an edge in relation F, v and v' must be connected by the edge (in the appropriate direction) in relation G.

  • First draw the 2 graphs F and G.
  • Then show the specified parts of the tree search to find a consistent labeling using only forward checking and none of the other heuristics. Do this in the blind order that has variable 1 at level 1 in the tree, variable 2 at level 2, and so on all the way down to variable 5 at level 5. At each level, of the values that are still possible, try them in alphabetical order.
  • Start the search at node (1,A). Apply forward checking and show the whole FTAB for variables 2, 3, 4, and 5. Do the same for the whole subtree under (1,A). If you find any consistent labelings mark them with a *.
  • Do the same for (1,B).
  • So for every node you show of the tree search, you show the assignment at that node and a forward checking table at all levels except level 5 where there are no more future units.
  • The subtrees below (1,A) and (1,B) are all you have to do. You don't need to go any further unless you're curious.
• The following tree is a game tree, with the triangles pointing up being the computer's moves (which will choose the maximum), and the triangles pointing down being the opponent's moves (which will choose the minimum). The circled numbers at the bottom are the evaluated states. You need to:
  • Perform the minmax algorithm on this tree, writing the values in the triangles as you go.
  • In a separate copy of the tree, perform minmax using alpha-beta pruning, writing down only the values in the triangles that get evaluated, and marking where the alpha-beta cut-off(s) occur(s).
  

• Hand in a printed copy of these exercises in class on the due date, Monday Feb 6th.