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

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

{\bf Problem 1.} Consider a graph search problem in which each
node is a non-negative integer.  Consider the following operations
on numbers, viewed as operators in a graph search problem.

\begin{itemize}

\item $D$ (for ``Double'')  $D(n)$ is $2n$.

\item $H$ (for ``Half'')  $H(n)$ is $\lfloor\frac{n}{2}\rfloor$.

\item $S$ (for ``Successor'') $S(n)$ is $n+1$.

\item $E$ (for ``make-Even'') If $n$ is odd then $E(n)$
is $n-1$, else E(n), is $n$.
\end{itemize}

The plan (sequence of operations) $H;E;D;E$ maps the number
11 to the number 8 ($H(11) = 5$; $E(5) = 4$; $D(4) = 8$; and
$E(8) = 8$).

Consider the following propositions about numbers.

\begin{itemize}

\item The proposition {\bf Even} is true of a node $n$ just in
case $n$ is even.

\item The proposition {\bf Odd} is true of a node $n$ just in
case $n$ is Odd.

\item The proposition {\bf One-Two} is true of a number $n$ just
in case the prime factorization of $n$ contains a single factor of 2.
For example {\bf One-Two}(6) is true but {\bf One-Two}(12) is false.
\end{itemize}

Each operator can be applied at any node.
In the following table each operator has been assigned an empty
prerequisite list.  Make a copy of this table with the add lists
and delete lists filled in.  Each add list and delete list should be a subset
of the propositions {\bf Even}, {\bf Odd}, and {\bf One-Two}.  The
delete lists should be as small as possible and the add lists as large
as possible so that the operator specification holds of the actual
operators.

\begin{tabbing}
\hspace{4ex} \= Operator \hspace{4ex} \=Prerequisite List
\hspace{4ex} \= Delete List \hspace{4ex} \= Add List \\
~ \\
\> $D$ \> $\emptyset$ \\
~ \\
\> $H$ \> $\emptyset$ \\
~ \\
\> $S$ \> $\emptyset$ \\
~ \\
\> $E$ \> $\emptyset$ \\
\end{tabbing}


In the following table each operator has been assigned
prerequisites.  Make a copy of this table with minimal delete
lists and maximal add lists inserted.

\begin{tabbing}
\hspace{4ex} \= Operator \hspace{4ex} \=Prerequisite List
\hspace{4ex} \= Delete List \hspace{4ex} \= Add List \\
~ \\
\> $D$ \> {\bf Odd} \\
~ \\
\> $H$ \> $\emptyset$ \\
~ \\
\> $S$ \> {\bf Even} \\
~ \\
\> $E$ \> $\emptyset$ \\

\end{tabbing}


{\bf Problem 2.}  GPS was developed in the late 50's by Simon
and Newell as a model of
human problem solving.  The GPS procedure for STRIPS planning
is given below.

\noindent To find a plan $\alpha$ such that
$\Sigma\rightarrow[\alpha]\Omega$ do the following:

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

\item Nondeterministically select some operator $o_i$ such that some proposition on the add list of
$o_i$ is a member of $\Omega$ but not a member of $\Sigma$

\item Let $\Omega'$ be the prerequisites of $o_i$.

\item Recursively find a plan $\beta$ such that
$\Sigma\rightarrow[\beta]\Omega'$.

\item Let $\Sigma'$ be the result of running the program $\beta;o_i$
from start state $\Sigma$, i.e., $\Sigma'$ is the largest set of
propositions such that $\Sigma\rightarrow[\beta;o_i]\Sigma'$.

\item Recursively find a plan $\gamma$ such that $\Sigma'\rightarrow[\gamma]\Omega$.

\item Return the procedure $\beta;o_i;\gamma$.

\end{enumerate}

Step 2 of the above procedure is non-deterministic.  This allows for
many different possible executions.
An implementation of this procedure would have to search the space
of all possible executions.

Give an example of a planning problem for which there exists a plan
that solves the problem but where GPS can not find a solution.

{\bf Problem 3.} Consider the following forward chaining partial order planner.
The difference between the planner given below and the one
given in the notes is step 4.  Deterministic selections are not backtracked
and do not correspond to branches in the search tree.  Nondeterministic selections
on the other hand are backtracked and do correspond to branches in the search
tree.

\noindent {\bf The Procedure {\tt FIND-COMPLETION}($\beta$ $c$)}

\begin{enumerate}
\item If the nonlinear plan $\beta$ is order inconsistent, or the total
cost of the steps in $\beta$ is greater than $c$, then fail.

\item If the nonlinear plan $\beta$ is complete then return $\beta$.

\item If there is a causal link $\clink{s}{P}{w}$ in $\beta$ and a
threat $v$ to this link in the symbol table such that $\beta$ does
not contain either $v < s$ or $v > w$, then nondeterministically
return one of the following.

\begin{enumerate}
\item {\tt FIND-COMPLETION}($\beta + (v < s), c$)

\item {\tt FIND-COMPLETION}($\beta + (v > w), c$)
\end{enumerate}

\item If none of the above cases apply then nondeterministically do one
of the following.

\begin{enumerate}
\item Nondeterministically select an operator $o$ from the
allowed set of operations such that for each prerequisite $P$ of $o$
there exists a step name $s$ that adds $P$.  Create a new entry $w$ in
the symbol table that maps a new step name to the operator $o$.  Let
$\beta'$ be the plan that results from adding the step $w$ and adding
a causal link $\clink{s}{P}{w}$ for each prerequisite $P$ of $w$.
Return the plan {\tt FIND-COMPLETION($\beta',\;c$)}.

\item Deterministically select a prerequisite $P$ of the step {\tt FINISH}
such that $\beta$ does not contain any causal link of the form
$\clink{s}{P}{\mbox{\tt FINISH}}$ but where some step in $\beta$
adds $P$.  Nondeterministically select some step name $s$ in the
symbol table such that $s$ adds $P$ and return the plan
$$\mbox{\tt FIND-COMPLETION($\beta + \clink{s}{P}{\mbox{\tt FINISH}}, c$)}.$$
\end{enumerate}

\end{enumerate}

{\bf part a.}  Is the above planner sound, i.e., will it only return correct
solutions.  Explain your answer.

{\bf part b.}  Is the above planner complete, i.e., will it find a solution
whenever a solution exits.  Explain your answer.

{\bf part c.}  Show that the above planner is not systematic, i.e., give a linear plan
that is a topological sort of two different nonlinear plans generated down two
different branches of the search generated by the above procedure.

{\bf part d.}  Explain why the linear version of the forward chaining planner, and the
the backward chaining version of the nonlinear planner, are both systematic
in the sense that no two branches of the search tree can generate the same plan.
\end{document}