\input psadobe \documentstyle[12pt,epsf]{report} \newcommand{\bigcenter}[1]{\begin{center} {\Large\bf #1} \end{center}} \setlength{\oddsidemargin}{.25in} \setlength{\evensidemargin}{.25in} \setlength{\textwidth}{6in} \setlength{\topmargin}{-0.4in} \setlength{\textheight}{8.5in} \parskip=2ex \parindent=0ex \newcommand{\necpos}[1]{[\langle #1 \rangle]} \input nofill.tex \input texcom.tex \begin{document} \centerline{\bf \large 6.824 Artificial Intelligence, Fall 1993} \centerline{\bf \large Problem Set 6 Solutions} \medskip \medskip {\bf Problem 1.} Consider the following line drawing \epsfxsize 2.5in \centerline{\epsffile{walts.ps}} Starting with the arrows around the border, there a unique assignment to the lines in this drawing which is entailed by the constraints. This assignment is \epsfxsize 2.5in \centerline{\epsffile{walts-sol.ps}} {\bf Value propagation} on this figure will find the labeling drawn in the first figure ($+$`s on outside box, and counter-clockwise arrows in hole, but the rest of the hole will not be labeled. Line $c$ can be counter-clockwise arrow or $+$, and line $a$ can be counter-clockwise arrow or $+$. The arrow junction at $aeb$ is unconstrained and cannot be assigned. So value propagation is stuck at this point. {\bf Arc consistency propagation} finds the assignment to the hole lines as follows. From the arrow junction at $aeb$ it finds $a \neq \leftarrow$ (not a counterclockwise arrow). Thus $a = +$, and from this the arrow junction is labeled with $b = +$ and $e = -$. Now the L junction at $bc$ constrains $c = \leftarrow$ (counter-clockwise arrow). {\bf Problem 2.} To show that Value propagation, Arc Consistency, and Generalized Forward Checking (GFC) are equivalent for Boolean variables the key observation is that Boolean variables can have one of two values. So equations $x = T$ imply disequations $x \neq F$, and disequations $x \neq T$ imply equations $x = F$ (In other words equations and disequations are interchangeable). Show {\bf Value propagation} $\equiv$ {\bf Arc Consistency}.\\ It is clear that Arc Consistency can derive everything Value Propagation can derive (not just for boolean variables.)\\ Value propagation can derive everything Arc Consistency can derive since any time Arc consistency derives a disassignment from a constraint and a set of assignments, Value propagation can make a corresponding assignment. (Basically this happens when there is a clause with one unassigned variable.) Show {\bf Arc Consistency} $\equiv$ {\bf GFC}.\\ Again Arc Consistency is known to be at least as powerful as GFC.\\ It is easy to see that GFC is just as powerful as Arc Consistency because GFC derives disassignments from assignments and constraints, and in the case of boolean variables Arc consistency reduces exactly to this. Show {\bf Value Propagation} $\equiv$ {\bf GFC}.\\ By transitivity. {\bf Unit Propagation} \begin{enumerate} \item Given partial assignment and formula $\phi$, remove from $\phi$ clauses that are satisfied by the partial assignment, and remove all literals assigned to false by the partial assignment from the clauses they appear in. Set current assignment $A$ to the partial assignment. \item Initialize queue $Q$ to clauses with single literals. Remove these clauses from $\phi$. \item If $A$ is inconsistent (assigns some variable both $T$ and $F$ return ``inconsistent''. If $Q$ is empty return current (possibly partial) assignment. \item Remove a constraint $(l)$ from $Q$. If $l = x$ add $x = T$ to $A$, otherwise add $x = F$ to $A$. \item Remove from $\phi$ clauses that are satisfied by the new assignment, and remove all literals assigned to false by the new assignment from the clauses they appear in. Add clauses with single literals to $Q$, and remove them from $\phi$. \item Goto step 3. \end{enumerate} This procedure can be implemented so it runs in linear time. {\bf Problem 3.} Show that arc consistency is complete for Horn clauses.\\ Remember that a {\em constraint propagation algorithm} is called complete if it can derive all assignments that are entailed by the constraints.\\ Consider an unsatisfiable setof Horn clauses. We must show that if there is no assignment satisfying these Horn clauses then the above unit propagation procedure will return "inconsistent". I will prove this by showing that the contra-positive is true. {\em If arc consistency propagation fails to derive an inconsistency then the given set of Horn clauses is satisfiable.} Suppose we have some set of Horn clauses $\Phi$ and that unit propagation does not find an inconsistency and outputs a partial assignment. We can divide the clauses into two sets: (1) clauses that are satisfied by the partial assignment, and (2) clauses that are not satisfied by the partial assignment. Consider the clauses in set (2). Each of these clauses has at least 2 literals which are not bound in the partial assignments, because if only one literal remained unbound and the clause was not yet satisfied that literal would be assigned by unit propagation. Furthermore, these clauses contain at least one unassigned literal which is the negation of a variable, because each clause has at most one positive literal. So we can satisfy all the clauses by assigning all the unbound variables to false. Thus $\Phi$ is satisfiable. Combined with the results from problem 2, this shows that Horn clause satisfiability is linear time decidable. Note: there was some confusion on the notions of soundness and completeness for boolean formulas. A {\em constraint propagation algorithm} is called complete if it can derive all assignments that are entailed by the constraints. An {\em algorithm to determine satisfiability} is called complete if when it outputs ``no'' given some formula, the formula is not satisfiable. These notions are really the same. Consider converting a constraint propagation algorithm $A$ to a satisfiability algorithm as follows:\\ `` on input $\phi$, run $A$ on $\phi$. If $A$ outputs ``inconsistent'' output ``no'', otherwise output ``yes''.''\\ If $A$ is complete (in the first sense), this algorithm is complete in the second. Think about it... {\bf Problem 4.} Consider a graph search problem with $b$ operators each with cost $C$ (the search has branching factor $b$). There are $b^d$ different nodes that can be reached by paths of length $d$ (ignoring the possibility that any node can be reached by more than one path.) 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$ 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 $C$ less than $h^*(n)$. Such an operator will be called a {\em good move} from the node $n$. In this problem we assume that there is only one good move from $n$. The operator other than the good move will be called the bad move. 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)$. {\bf Part a.} Increasing the parameter $C$ increases the advantage of $A^*$ over breadth first search because the heuristic function is more accurate. In the limit $h$ goes to $h^*$. Increasing the branching factor $b$ increases the advantage of $A^*$ over BFS because BFS must search every branch of the search tree, while $A^*$ only searches short paths with bad moves. As $b$ gets bigger $A^*$ will prune more of the search tree relative to BFS. $h$ is monotone so the projected cost of a path $m \leadsto n$ is just the cost of the operators (in this case just $C$ times the number of operators) in the path plus $h(n)$ where $n$ is the final node in the path. We define the {\em added cost} of a path $m \leadsto n$ to be the projected cost of the path $m \leadsto n$ minus the projected cost of the empty path $m \leadsto m$. {\bf Part a.} Let $G$ be the number of good moves in a path and let $B$ be the number of bad moves in a path. There are two ways to approach this problem. Intuitively, consider only one good move -- it has cost $C$, but leads to a node which has decreased projected cost. The decrease in projected cost is $C -1$ since $\Delta h^* = C$, $\Delta h = \frac{C-1}{C} \Delta h^* = C-1$ so $c_G = C -(C-1) = 1$. A bad move also has cost $C$ and leads to a node with the same cost so $c_B = C$. This is the way most people solved this \begin{eqnarray} ProjectedCost(m \leadsto n) & = & C(B+G) + h(n)\\ ProjectedCost(m \leadsto m) & = & h(m)\\ & = &\frac{C-1}{C}h^*(m)\\ & =& \frac{C-1}{C}(CG +h^*(n)\\ & = &(C-1)G + h(n)\\ \end{eqnarray} so \begin{eqnarray} AddedCost(m \leadsto n) &=& ProjectedCost(m \leadsto n) - ProjectedCost(m \leadsto m)\\ & = & C(B+G) + h(n) - ((C-1)G + h(n))\\ & =& CB + G\\ \end{eqnarray} {\bf Part c.} Let $M(k)$ be the number of nodes that can be reached by paths with {\em added cost} of {\em exactly} $k$. Assume that $M(k)$ grows exponentially in $k$. $A^*$ expands nodes with minimum projected cost from the start node, so it will expand paths with projected cost $1, 2, 3 \ldots$. Notice also that the difference between the added cost of a path and the projected cost of a path is an additive constant, namely the projected cost of the empty path from the start node. So we can also say that $A^*$ will expand paths of increasing added cost. In other words it will first expand all nodes of added cost $1$ -- there are $M(1)$ of these, then those with added cost $2$ -- there are $M(2)$ of these, up to cost $d$ So the total number of nodes $A^*$ will expand is $$\sum_i^d M(i)= \sum_i^d a^i = \frac{a^{d+1} - 1}{a-1} = O(a^d) = O(M(d))$$ In words the number of nodes reachable with added cost $k$ is so much bigger than the previous ones that it dominates. Thus the order of running time to find a path of length $d$ (ignoring the time to store fringe nodes on some sort of priority queue) is $O(M(d))$ {\bf Part d.} $M(0)$ contains only the start node so $M(0) = 1$.\\ There is only one node with added cost $1$ -- via a good move from the start node -- so $M(1) = 1$. Similarly up to added cost $C$ when it is possible to take a bad move, there is only one node with added cost $k$ ($k