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

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


{\bf Problem 1.} Consider rewrite rules such as the following.
$$(*\; x \; (+\; y\; z)) \rightarrow (+\; (*\; x\; y)\; (*\; x\; z))$$
$$(+\; (+\; x\; y)\; z) \rightarrow (+\; x\; (+\; y\; z))$$
$$x \rightarrow (+\; x\; (+\; y\; (-\; y)))$$
Each rewrite rule specifies that an instance of the left hand side
can be rewritten as an instance of the right hand side.  For example,
the first rule specifies that $(*\; (f\; a)\; (+\; c\; d))$ can be rewritten
to $(+\; (*\; (f\; a)\; c)\; (*\; (f\; a)\; d))$.  The last rule specifies that
$(f\; a)$ can be rewritten as $(+\; (f\; a)\; (+\; (g\; b)\; (-\; (g\; b))))$.

The above rules are only meant as an example --- in this problem
we consider the general concept of rewrite rules.
Let $R$ be a set of rewrite rules and let $s$ and $w$ be ground
expressions (expressions that do not contain variables).
Suppose that we use the following procedure to determine if
there exists a way of rewriting $s$ to $w$ using rewrite rules
in $R$ using at most $d$ rewriting steps.

{\bf Procedure to determine if $s$ can be rewritten to $w$ in $d$ steps}

\begin{enumerate}

\item If $s$ is the same expression as $w$ then return ``yes''.

\item If $d$ is 0 then fail.

\item Select (nondeterministically) a {\em ground instance}
$u \rightarrow v$ of a rewrite rule in $R$.

\item If $u$ does not equal $s$ then fail.

\item If $u$ equals $s$ then
return the value of a recursive call to the procedure
on $v$, $w$ and $d-1$.
\end{enumerate}

The above procedure operates on ground expressions (step 3 selects
a ground instance of a rewrite rule).  The general lifting transformation
can be applied to this procedure.  The following questions concern
the differences between the ground procedure and the lifted procedure.

In the following questions we assume that at least one rule
in the rule set $R$ contains a variable and that there are $n$
different rules in $R$.

In the ground procedure given above, how many ways are there of
executing step 3?  In the lifted version of the procedure, what is the
maximum number of ways that the sequence of step 3 followed by step 4
can execute without failure?  Consider a call to the lifted version of
the procedure.  As a function of $n$ (the number of rules) and $d$
(the allowed number of steps), give the maximum possible number of
leaves in the search tree, i.e., the maximum number of times some
recursive call to the procedure can fail at step 2.

\noindent {\bf Problem 2.} This problem is on the lifted linear backward chaining planner.
Consider the nonlinear planning procedure {\tt FIND-COMPLETION} given below.
This procedure takes a nonlinear plan $\beta$ and searches for a
completion.

\medskip

\noindent {\bf Procedure for computing {\tt FIND-PLAN($\Sigma$, $\Omega$, $c$, $h$)}:}

{\small
\begin{enumerate}
\item If $\Omega$ is a subset of $\Sigma$ then return the empty plan.

\item Select an operator $o_i$.

\item If some element of the delete list of $o_i$ is a member of $\Omega$ then fail.

\item If no element of the add list of $o_i$ is a member of $\Omega$ then fail.

\item Let $\Omega'$ be the weakest precondition of $\Omega$ with
respect to $o_i$.

\item Let $\beta$ be {\tt FIND-PLAN($\Sigma$, $\Omega'$, $c-c(o_i)$, $h$)}

\item Return the plan $\beta;o_i$.
\end{enumerate}
}

For each of steps 1, 2, 3, 4 and 5 of the above procedure state
whether that step is deterministic or nondeterministic in both the
ground and the lifted version of the planner {\em for the blocks world}.
Give a {\em brief} explanation of each answer.  At least one answer is different
when the planner is restricted to the blocks
world than when we consider arbitrary STRIPS planning.
Also, a step is considered to be nondeterministic if and only if there
is more than one way of completeing the step without failing (the step
has a nonfailing branching factor of at least two).

{\bf Prolem 3.} Give a resolution proof that the following two clauses
are unsatisfiable.
$$P(x,\;y) \vee P(y,\;x)$$
$$\neg P(x,\;y) \vee \neg P(y,\;x)$$
Hint: consider the case where $x$ equals $y$.

{\bf Problem 4.}  Give a polynomial time reduction of the STRIPS planning problem
to resolution theorem proving.
More specifically, given a set $o_1, \cdots o_b$ of STRIPS operators, a set $\Sigma$
of initial propositions, and a set $\Gamma$ of goal propositions,
show how to construct, in time polynomial in the written length of the STRIPS
problem, a set of clauses $\calc$ such that one can
derive the empty clause from $\calc$ if and only if the given STRIPS
problem has a solution.  You should assume that
the planning problem is ground, i.e., all propositions
involved are simple proposition symbols.

\end{document}