
\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<C$) by taking a series of $k$ good moves.  So $M(k) =1$ for $k<C$

In general, the number of nodes with added cost $d+C$ is sum of the
number of nodes with added cost $d+C-l$ after taking a move with added cost $l$.
A good move has cost $1$ and following it $M(d+C-1)$ nodes have added cost
$d+C-1$, and there are (b-1) bad moves with cost $C$ following which 
there are $M(d)$ nodes with added cost $d$.  So
$$M(d+C) = M(d+C-1) + (b-1)M(d)$$

{\bf Part e.} For $b=C=2$, $$M(d+2) = M(d-1) + M(d)$$
This is the well known Fibonacci sequence shifted by one (i.e. $M(d) = Fib(d+1)$)
with has the known solution
$$Fib(d+1) = \frac{\Phi^{d+1} - \hat{\Phi}^{d+1}}{\sqrt{5}}$$
where $\Phi = \frac{1+\sqrt{5}}{2},\hat{\Phi} = \frac{1-\sqrt{5}}{2}$

So $M(d) = O(\Phi^d)$

Now compare $A^*$ with BFS.  Say $A^*$ search paths of depth $d$, and BFS
paths of $d_2$.
\begin{eqnarray}
M(d)&=& 2^{d_2}\\
\Phi^d & = & 2^{d_2}\\
d& =& d_2 \frac{ln{2}}{ln{\Phi}}\\
& = & d_2 1.44
\end{eqnarray}

So $A^*$ can find paths about 44\% longer than breadth first search.

\end{document}  


