%% This LaTeX-file was created by <jcl> Wed Feb 10 19:47:22 1999
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\batchmode
\listfiles
\makeatletter
\def\input@path{{/home/jcl/afs/AI2//}}
\makeatother
\documentclass[dvips]{slides}
\usepackage[T1]{fontenc}
\usepackage{graphics}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newcounter{slidetype}
\setcounter{slidetype}{0}
\newif\ifLyXsNoCenter
\LyXsNoCenterfalse
\newcommand{\noslidecentering}{
	\LyXsNoCentertrue%
}
\newcommand{\slidecentering}{
	\LyXsNoCenterfalse%
}
\newcommand{\lyxendslide}[1]{
	\ifLyXsNoCenter%
		\vfill%
	\fi%
	\ifcase \value{slidetype}%
		\or % no action for 0
		\end{slide} \or%
		\end{overlay} \or%
		\end{note}%
	\fi%
	\setcounter{slidetype}{0}
}
\newcommand{\lyxnewslide}[1]{
	\lyxendslide{.}
	\setcounter{slidetype}{1}
	\begin{slide}
}

\makeatother

\begin{document}

\lyxnewslide{Overview}

Outline

\begin{itemize}
\item What
is
planning?
\item Detailed
example
of
planning
in
action.
\item Rough
history
of
planning.
\end{itemize}
\lyxnewslide{Planning?}

What
is
a
Planning
problem?

\begin{itemize}
\item Input

\begin{enumerate}
\item An
initial
state
\item operators
which
transform
the
state
\item A
goal
condition
\end{enumerate}
\item Output

\begin{enumerate}
\item A
plan
which
transforms
the
intial
state
to
the
goal
condition.
\end{enumerate}
\end{itemize}
\lyxnewslide{More
definitions}

More
definitions

\begin{itemize}
\item Initial
state:
A
logical
sentence
about
what
is
true
in
the
world.
\item Operator
contains:

\begin{enumerate}
\item precondition
-
a
logical
sentence
which
must
hold
in
order
to
apply
it.
\item postcondition
-
an
assertion
of
what
holds
after
the
operator
is
applied.
\end{enumerate}
\item goal
condition:
a
precondition
of
what
must
be
done
in
order
to
satisfy
the
planning
problem.
\item Plan:
A
sequence
of
operations
which
achieve
the
goal
condition
when
applied
to
the
initial
state.
\end{itemize}
\lyxnewslide{Ways
to
think
about
planning}

Two
views
of
planning:

\begin{itemize}
\item ``Planning
is
search
except
the
operators
can
also
vary''

\begin{itemize}
\item Planning
is
slower
then
a
search
algorithm
on
particular
search
problems
.
\item Search
is
a
special
case
of
planning.
\end{itemize}
\item ``Planning
is
finding
a
program
which
fits
a
specification
on
a
virtual
computer''

\begin{itemize}
\item Planning
is
perilously
close
to
a
halting
problem.
\item The
expressiveness
of
the
language
used
to
state
planning
problems
is
important.
\end{itemize}
\end{itemize}
\lyxnewslide{Planning
problem}

A
simple
planning
problem:

We
have
3
blocks,
block
A,
block
B,
and
block
C.
Currently,
Blocks
A
and
C
are
on
the
table.
Block
B
is
on
block
C.
We
want
to
have
block
A
on
block
C
and
block
C
on
block
B.
We
can
achieve
our
goals
by
moving
blocks
around
one
block
at
a
time. 

\lyxnewslide{Exact
definitions}

We'll
look
at
Graphplan.
Here
are
some
more
exact
definitions:

\begin{itemize}
\item literal:
A
predicate
with
all
variables
bound.
\item Initial
state:
Any
conjunction
of
literals.
\item Final
state:
Any
conjuction
of
literals.
\item Operator
Precondition:
Any
conjuction
of
literals
with
variables.
\item Operator
Postcondition:
Any
conjunction
of
literals
with
variables.
\end{itemize}
Important
note:
All
variables
are
instantiated
with
values
before
they
reach
the
graph!

(there
are
many
extensions
to
richer
languages)

\lyxnewslide{Formalization}

Formalization
of
the
planning
problem:

\begin{itemize}
\item Initial
State:
A-Clear
and
A-on-B
\item Goal
State:
B-on-A
\item Operator: 

\begin{enumerate}
\item Move-<x>-to-<y>

\begin{enumerate}
\item If
<x>-Clear
and
<y>-Clear
\item then
<x>-on-<y>
and
not
<y>-Clear
\end{enumerate}
\item Move-to-table-<x>-on-<y>

\begin{enumerate}
\item If
<x>-Clear
and
<x>-on-<y>
\item then
<y>-Clear
and
not
<x>-on-<y>
\end{enumerate}
\end{enumerate}
\end{itemize}
\lyxnewslide{Beginning}

Now
we'll
run
through
a
planning
algorithm.
We
will
use
Graphplan,
which
is
a
reasonably
modern
planner.
First,
we
lay
out
the
initial
state
as
the
first
layer
of
the
graph:

\vspace{0.3cm}
{\centering \includegraphics{Beginning-2.eps} \par}
\vspace{0.3cm}

Think
about
how
useful
A-Clear
and
Not-B-Clear
would
be
instead...

\lyxnewslide{Next
Layer}

Next,
we
apply
ever
operator
possible
to
the
literals
in
the
first
layer.

\vspace{0.3cm}
{\centering \includegraphics{First-step-2.eps} \par}
\vspace{0.3cm}

\begin{itemize}
\item There
is
an
implicit
Noop
operator
which
corresponds
to
the
assumption
that
unmodified
state
is
unchanged.
\item For
efficiency
reasons,
we
keep
track
of
exclusions
between
operators
and
literals.

\begin{itemize}
\item Operators
are
exclusive
if
they
cannot
both
be
applied
at
the
same
time.
\item Literals
are
exclusive
if
every
way
of
reaching
them
is
exclusive.
\end{itemize}
\end{itemize}
\lyxnewslide{Last
Layer}

There
goal
literal,
B-on-A
is
not
found
so
another
layer
is
constructed
in
the
graph.
Every
operator
is
applied
to
any
possible
set
of

literals. 

\vspace{0.3cm}
{\centering \includegraphics{Second-step-2.eps} \par}
\vspace{0.3cm}

\lyxnewslide{Questions}

\begin{enumerate}
\item Can
you
find
the
operators
that
I
missed
in
the
second
layer?
\item What
extra
exclusions
can
be
made
in
the
second
layer?
\end{enumerate}
Now,
the
goal
literal,
B-on-A
exists
so
we
search
for
a
plan. 

\begin{enumerate}
\item Only
Move-B-on-A
achieves
B-on-A.
This
requires
A-clear
and
B-clear.
\item A-clear
is
achieved
by
a
Noop
in
the
first
layer.
B-Clear
is
achieved
by
Move-to-table-A-on-B.
\item We
require
A-Clear
and
A-on-B
which
fits
the
initial
state.
\end{enumerate}
\lyxnewslide{Plan}

The
final
plan
is:

\begin{enumerate}
\item Noop-A-Clear
and
Move-to-table-A-on-B
\item Move-B-on-A
\end{enumerate}
If
there
was
no
successful
plan,
the
graph
would
grow
another
layer
and
search
again.

\lyxnewslide{history}

A
brief
history
of
planning

\begin{enumerate}
\item (1970s)
First
order
planners

\begin{itemize}
\item Computers
were
slow.
\item First
order
expressions
were
too
powerful
-
\( \forall a:f(a) \)
\end{itemize}
\item STRIPS
-
a
simple
language

\begin{itemize}
\item Stating
planning
problems
is
a
bit
awkward.
\item Planning
is
``merely''
exponential
time
in
the
plan
length.
\end{itemize}
\item Linear
vs
Nonlinear
planning

\begin{itemize}
\item If
you
have
multiple
goals
sometimes
achieving
the
second
goal
invalidates
the
first
goal.
\end{itemize}
\end{enumerate}
\lyxnewslide{linearity}

Linear
vs.
Nonlinear
planning
and
the
Sussman
Anomaly

Your
goals
are
A-on-B
and
B-on-C.
Initially,
you
have
A-on-C. 

\begin{itemize}
\item Linear
method:
satisfy
A-on-B
then
satisfy
B-on-C.

\begin{enumerate}
\item Move
A
onto
B
\item Move
A
onto
the
table
\item Move
B
onto
C
\end{enumerate}
\item Nonlinear
method:
satisfy
all
goals
simultaneously.

\begin{enumerate}
\item Move
A
to
the
table
\item Move
B
onto
C
\item Move
A
onto
B
\end{enumerate}
\end{itemize}
\lyxnewslide{1990}

\begin{enumerate}
\item (early
90s)
More
modern
planners
(Example:
Prodigy)
have
different
search
strategies

\begin{itemize}
\item Forward
search
(substating)
\item Backward
search
(subgoaling)
\item Partial
plans
and
plan
repair
\end{itemize}
\item 1995
Graphplan
-
many
hacks
to
speed
up
planning

\begin{itemize}
\item C
vs.
LISP
\item Parallel
operators
\item Reduction
of
problem
to
search
on
a
graph
\item Constraints
and
constraint
propagation
\end{itemize}
\end{enumerate}
\lyxnewslide{More
hacks}

\begin{enumerate}
\item (now)
Graphplan
inspired
planners

\begin{itemize}
\item Type
analysis
of
planning
domains.
\item Reduction
of
graph
to
satisfiability
problem
and
application
of
SAT
solvers.
\item Many
other
tricks
\end{itemize}
\end{enumerate}
www.cs/\~{}jcl/compileplan/compiling\_planner.html 

Current
planning
research
topics
include:

\begin{itemize}
\item Planning
with
unknown
state
\item Planning
with
known
state
but
uncertain
outcomes
to
operators
\item Combination
of
both
\end{itemize}
\lyxnewslide{More
planning}

\begin{itemize}
\item probabilistic
unknown
state
=
HMM
\item probabilistic
unknown
outcomes
=
MDP
\item probabilistic
unknown
state
and
outcomes
=
POMDP
\item Contingent
planning
\item Time
constraints
\item Anytime
planning
\end{itemize}
\lyxendslide{foo}

\end{document}
