6.824 Artificial Intelligence, Fall 1993 Problem Set 6

Due: Beginning of class Wednesday, November 3

Problem 1. If all solutions to a constraint satisfaction problem assign the variable X the value x then we say that X = x is entailed by the constraints. A constraint propagation algorithm is called complete if it can derive all assignments that follow from the constraints. This is the same notion of completeness that is used for inference rules in general — inference rules are complete if, given any set of premises, they can be used to derive all assertions semantically entialed by the premises. Give an example of a Waltz line drawing where value propagation is incomplete, i.e., there is an assignment that is entailed by the constraints but value propagation will not derive that assignment. Here we view Waltz line labeling as a formal CSP — we are only concerned with the formal set of constraints and are not concerned with physical realizability of labelings. For the example you construct determine whether arc consistency will solve it, i.e., whether arc consistency will derive the entailed assignment.

Problem 2. Give a proof that in Boolean CSPs, i.e., in CSPs in which every variable has only two possible values, the procedures value propagation, arc consistency propagation, and GFC are all equivalent. Recall that a SAT problem is a set of Boolean clauses where each clause is a disjunction of literals where each literal is either a Boolean variable or the negation of a Boolean variable. Describe value propagation for SAT problems. This procedure is called unit propagation and can be run to completion in linear time (you do not have to prove this).

Problem 3. A Horn clause is a clause with at most one positive literal. Show that unit propagation is complete for Horn clauses, i.e., if unit propagation fails to derive an inconsistency then the given set of Horn clauses is satisfiable. In particular you should consider the case where unit propagation does not derive an inconsistency. In this case you should show that a model of the clauses can be constructed and hence that the clauses are satisfiable. Combined with the fact that unit propagation can be done in linear time, this shows that Horn clause satisfiability is linear time decidable.

Problem 4. This problem considers the degree to which a heuristic function improves the performance of a search problem. Consider a graph search problem with b operators (the search has branching factor b). In this problem we will ignore the posibility that any node can be reached by more than one path. There are b^{d} different nodes that can be reached by paths of length d. We also assume that each operator has a cost of C where C is a natural number. We allow for more than one goal node and for any node n we define h^{∗}(n) to be the cost of the shortest path from n to a goal node (which will be C times the number of operations in the path).

The definition of h^{∗} implies that at each node n one of the operators must move one step closer to the goal, i.e., there is an operator o such that h^{∗}(o(n)) is one less than h^{∗}(n). Such an operator will be called a good move from the node n. In this problem we assume that there is only one good move from n. The operators other than the good move will be called bad moves. We assume that the bad move does not change the distance to the goal, i.e., if o′ is a bad move from n then h^{∗}(o′(n)) equals h^{∗}(n).

We assume a heuristic function h such that for any node n we have that h(n) = \frac{C−1}{C}h^{∗}(n). This is unrealistic because in this case we could get a perfect heuristic function by multiplying h by \frac{C}{C−1}. However, this unrealistic assumption may model more realistic cases where the expected value of h is \frac{C−1}{C}h^{∗}. Note that since h^{∗}(n) is always a multiple of C, h(n) is always an integer. The larger the value of C, the more accurate the heuristic function.

We now have two parameters characterizing A^{∗} search — the branching factor b and the parameter C which characterizes the accuracy of the heuristic function — the larger the value of C the more accurate the heuristic function.

part a. Should increasing the parameter C increase or decrease the advantage of A^{∗} relative to breadth first search? Should increasing b increase or decrease the advantage of A^{∗} over breadth first search? Give a qualitative explanation of your answers.

This heuristic function is monotone so the projected cost of a path is just the cost of the operators (in this case twice the number operators) in the path plus h(n) where n is the final node in the path. We define the added cost of a path to be the projected cost of the path minus the projected cost of the empty path.

Part b. Let G be the number of good moves in a path and let B be the number of bad moves in a path. Show that the added cost of a path equals c_{G}G + c_{B}B. Give the values of c_{G} and c_{B} in terms of b and C. c_{G} is the “marginal cost” of a good move and c_{B} is the marginal cost of a bad move.

Part c. Let M(k) be the number of nodes that can be reached by paths with added cost of exactly k. Assume that M(k) grows exponentially in k and argue that the order of running time of A^{∗} to find a path of length d is O(M(d)). (Hint: You should argue that O(M(1) + M(2) + … + M(d)) = O(M(d)))

part d. Argue that M[0], M(1), …, M(C −1) are all 1 and give a recurrence relation expressing M(d+C) as a function of M(d+C −1) and M(d). (Hint: Consider special cases such as b = C = 2 and b = 2, C = 3.)

part e. Use the recurrence you found in part c to compute The order of growth of M(d) in the case where b = C = 2. This requires solving a second order linear recurrance relation. In this case it can be done by assuming that M[d] = aλ_{1}^{d} + bλ_{2}^{d} and solving for a, b, λ_{1} and λ_{2}. To find the order of growth you need only the larger of λ_{1} and λ_{2}. Your answer should show that A^{∗} can find paths about 44% longer than breadth first search.

Using the recurrence in part d it can be shown by induction on d that for b ≥ 2 and C ≥ 2 we have

(b − 1)^{\frac{d}{C}} ≤ M(d) ≤ b^{(1+ϵ(b)) \frac{d}{C}}
where ϵ(b) = \frac{− ln[1 − \frac{1}{\sqrt{b}}]}{ln b}

So for large values of b, A^{∗} can find paths roughly a factor of C larger than can be found by breadth first search. (You do not need to do this induction proof.)