\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}
\medskip
\medskip

\centerline{Due:  Beginning of class Wednesday, November 3}

{\bf Problem 1.}  If all solutions to a constraint satisfaction problem
assign the variable $X$ the value $x$ then we say that $X=x$ is {\em entailed by}
the constraints.  A constraint propagation algorithm is called {\em 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.

{\bf 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).

{\bf 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.

{\bf 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 {\em 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.

{\bf 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 {\em added cost} of a path to be the
projected cost of the path minus the projected cost of the empty
path.

{\bf 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.

{\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$ 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) + \ldots + M(d)) = O(M(d))$)

{\bf part d.} Argue that $M[0]$, $M(1)$, $\ldots$, $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$.)

{\bf 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\lambda_1^d + b\lambda_2^d$
and solving for $a$, $b$, $\lambda_1$ and $\lambda_2$.  To find the
order of growth you need only the larger of $\lambda_1$ and $\lambda_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 \geq 2$ and $C \geq 2$ we have
$$(b-1)^\frac{d}{C} \leq M(d) \leq b^{(1+\epsilon(b))\frac{d}{C}}$$
$$\mbox{where}\;\;\epsilon(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.)

\end{document}