Assignment
1. Consider a scheduling problem, where there are five activities to be scheduled in four time slots. Suppose we represent the activities by the variables A, B, C, D, and E, where the domain of each variable is {1, 2, 3, 4}. The constraints for the scheduling problem are: A > D, D > E, B ≥ A, B ≠ C, C ≠ A, C ≠ D, C ≠ D + 1, and C > E.
(a) Show how arc consistency (AC-3) can be used as a preprocessing first step. To do this you must:
(i) Draw the constraint graph (HINT: all of the constraints are binary and bidirectional);
(ii) Show an initial queue with the constraints in the order given above (the A - D constraint at the front of the queue) and then show how the queue changes throughout the algorithm; and
(iii) Show a table that illustrates how the algorithm progresses-the table consists of rows containing the constraint being considered, the elements in the domains of the two variables connected by the constraint after the arc is made consistent, and the arcs that are added to the queue by this step. Marks will be given for each of these elements of your answer.
(b) With the constraint graph preprocessed by AC-3 in part (a), show how backtracking search can be used to solve this problem. To do this, you must draw the search tree generated to find all answers. Indicate (in a summary) the valid schedule(s) that are found. Use the following variable ordering: A, D, E, C, and B.
2. You are given a Knowledge Base consisting of the following definite clauses:
B ∧ C ⇒ A
D ⇒ B
E ⇒ B
C
H ⇒ D
E
G ∧ B ⇒ F
C ∧ K ⇒ G
A ∧ B ⇒ J
Give a top-down derivation for A.
3. Convert the following FOL sentences into clauses. Show all intermediate conversion steps. Include steps that are required to incorporate the clauses into an empty Knowledge Base.
(a) ∃x∀yL(x, y)
(b) ∀x∃yL(y, x)
(c) ∀z{Q(z) ⇒ {-∀x∃y[P(y) ⇒ P(g(z, x))]}}
4. Give a most general unifier for the following pairs of expressions (if one doesn't exist, state the reason why):
(a) P(x, B, y, D) and P(A, w, C, z)
(b) Q(x, B, y, D) and Q(A, w, C, x)
(c) P(f(x), g(g(B))) and P(z, g(y))
(d) G(f(x), r(x), T) and G(x, r(q), q)
(e) B(v(x, a), z) and B(p, p)
5. You are given the following Knowledge Base (already converted to clause form):
¬B(x) ν C(x), ¬C(K) ν D(L), -C(M) ν E(N), D(w) ν ¬E(y).
Using resolution, prove ∃x¬B(x). Provide a diagram as shown in the book/slides. Be certain to show any unifiers that are required in the resolution proof.