\documentclass[oribibl]{llncs}
\usepackage{makeidx}  % allows for indexgeneration
\input{psfig.sty}

\iffalse
\documentstyle[12pt,psfig]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.8in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\addtolength{\textheight}{0.2in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\fi

\newcommand{\five}{{$(t=5)$}}
\newcommand{\ten}{{$(t=10)$}}
\newcommand{\fiveten}{$t=5 [10]$}
\newcommand{\GP}{\mbox{\sf Graphplan}}
\newcommand{\TGP}{\mbox{\sf TGraphplan}}
\newcommand{\Bur}{\mbox{\sf Buridan}}
\newcommand{\Cbur}{\mbox{\sf C-Buridan}}
\newcommand{\Zander}{\mbox{\sf Zander}}
\newcommand{\Maxplan}{\mbox{\sf Maxplan}}
%%\newcommand{\UICGP}{\mbox{UIC-Graphplan}}
\newcommand{\PGP}{\mbox{\sf PGraphplan}}
%%\newcommand{\BPGP}{\mbox{BPgraphplan}}
\newcommand{\andd}{\wedge}
\newcommand{\orr}{\vee}
\newcommand{\implies}{\rightarrow}
\newcommand{\ceiling}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\figfont}{\sl}
\newcommand{\shortcite}[1]{\cite{#1}}
\newcommand{\comment}[1]{}
%Macro to draw pretty boxes around things
\newlength{\boxwidth}
\setlength{\boxwidth}{\textwidth}
\addtolength{\boxwidth}{-27 pt}
\newcommand{\boxer}[1]{\begin{center} 
			\fbox{ \begin{minipage}{4.5in}
				\vspace*{.05in} #1 \vspace*{.05in}
				\end{minipage}} \end{center}}

\newcommand{\dollar}{\$}%$
\def\action#1{{\tt `#1'}}
\def\prop#1{{\tt `#1'}}
\begin{document}
\title{Probabilistic Planning in the Graphplan Framework}
%%\thanks{Portions of this work were presented
%%at the unrefereed 1998 AIPS workshop on Planning as Combinatorial Search.}
%%}
\author{Avrim L. Blum \and John C. Langford}
\institute{School of Computer Science,
Carnegie Mellon University, Pittsburgh PA 15213-3891
\email{\{avrim,jcl\}@cs.cmu.edu}}
\maketitle

\begin{abstract}
%%The \GP\ planner compiles a STRIPS planning problem into a compact
%%graph structure which is then used to speed up the search for a plan.
%%Empirical results have indicated substantial performance benefits to
%%this approach.   
The \GP\ planner has enjoyed considerable success as a planning
algorithm for classical STRIPS domains. 
In this paper we explore the extent to which its representation can
be used for {\em probabilistic} planning.  In particular, we consider
an MDP-style framework in which the state of the world is known but
actions are probabilistic, and the objective is to produce a
finite horizon contingent plan with highest probability of
success within the horizon.

We describe two extensions of \GP\ in this direction.  The first, \PGP,
produces an optimal 
contingent plan.  It typically suffers a
performance hit compared to \GP\ but still appears to be fast compared
with other approaches to probabilistic planning problems.  The second,
\TGP, runs at
essentially the same speed as \GP, but produces potentially
sub-optimal policies: \TGP's policy selects the first action on the
highest probability {\em trajectory} from its current state to the
goal.  Ideally, we would like an 
optimal planner for probabilistic domains with the same speed that
\GP\ would have if the domain were made deterministic.  By comparing
the speed and quality of these two planners to each other and to other
existing planners, we are able to estimate
how far off we are from our ideal.
%% We also compare these planners to
%%other approaches on a variety of domains.  For instance, we show that
%%\PGP\ improves substantially over standard dynamic programming
%%for a number of natural problems.\\

\PGP\ is based on a forward-chaining search, unlike the
backward-chaining search of the standard \GP\ algorithm.  Thus, one 
focus of this paper is exploring the extent to which \GP's representation
can be used to speed up forward search in addition to the
backward search for which it was originally intended.

%% 
%% 
%% 
%% We describe two extensions of \GP\ in this direction, called \PGP\ and
%% \TGP.  Given a bounded number of time steps, \PGP\ produces a policy
%% with highest expected utility, for several options of utility
%% function.  For reasons explained in this paper, \PGP\ is based on a
%% forward-chaining search through the 
%% planning graph.
%% A key part of this work is to explore ways 
%% in which the planning graph framework can be used to speed up forward
%% search as well as the backwards-chaining search for which it was
%% originally intended.  \PGP\ suffers a substantial performance hit
%% compared to the deterministic \GP, but appears to still be fast
%% compared with other approaches to probabilistic planning problems.
%% 
%% Planning in probabilistic domains is more complex than in
%% deterministic domains.  \TGP\ solves a variant problem with complexity
%% similar to the deterministic domain planning problem.  The solution is
%% generally suboptimal with respect to the full planning problem but is
%% often optimal on natural problems and provides a much quicker
%% solution.  On a deterministic domain, \TGP\ reduces to \GP, producing
%% a legal plan if one exists.  On probabilistic domains, the policy
%% produced by \TGP, for each state, chooses the first action on the
%% highest-probability trajectory from that state to the goal.  

%{\sf Content areas: planning and control, probabilistic reasoning,
%constraint satisfaction, plan evaluation, search.}
\end{abstract}
\section{Introduction}
The \GP\ planner is based on compiling a STRIPS-style planning problem into
a compact (polynomial size) graph structure in which information can
be quickly propagated to aid in the search for a plan \cite{BF97}.
Empirical results indicate that this approach is often quite fast
compared to other traditional methods \cite{BF97,Bylander97,KNHD97}.
Since its initial formulation, this basic algorithm has been extended
and improved in a number of ways, such as allowing operators with
contingent effects \cite{GK97,KNHD97,ASW97}, handling certain kinds of
uncertainty \cite{SW98,WAS98}, and further speed improvements
\cite{KNHD97,KLP97}. 

In this paper, we explore the question: to what extent can the speed
of \GP\ be extended to probabilistic domains?  We consider the setting
in which initial conditions and current state are known, but actions
can be probabilistic, having several possible outcomes.  This falls
into the framework of Markov Decision Processes (MDPs).  In
particular, instead of looking for a plan that consists of an action
sequence, we will be looking for a contingent plan that tells which
action to take based on the history of outcomes so far.  The
specific kind of 
MDP we focus on is one in which, as with STRIPS planning, our
objective is to satisfy all of a given set of conjunctive goals. Our
aim will be to produce an optimal finite-horizon contingent plan, where by
``optimal'' we mean maximizing the probability of success within the
time window (though much of the discussion applies to objectives
such as minimizing the expected completion time as well).

Ideally, we would like an optimal planner for probabilistic domains
with the same speed that \GP\ would have, had the domain been
deterministic.  Embedding probabilistic outcomes into \GP's graph
structure is straightforward.  However, how to search for a plan is
less obvious.  Planning in probabilistic domains is inherently more
complex than in deterministic domains, in part because a complete
policy can have size exponential in the horizon time whereas in
deterministic domains, plan sizes are linear in the horizon time.

We instead present two planners: \PGP\ and
\TGP.  \TGP\
%% uses a simple extension of the \GP's backward-chaining search and 
runs at essentially the same speed as
\GP, but produces potentially sub-optimal policies. Specifically,
\TGP\ finds the highest probability  {\em trajectory} from the start state to
the goal, which can then be turned into a kind of greedy contingent
plan in a natural way. In contrast, \PGP\ produces {\em optimal}
contingent plans but typically suffers a performance hit.  Unlike the
backward-chaining search of \GP, 
\PGP\ is based on a {\em forward-chaining} search through the planning
graph, which is much more natural
for producing optimal plans in these probabilistic settings (we
discuss this further in Section \ref{whyforward}).  \PGP\ is like a
standard top-down Dynamic Programming algorithm, but 
uses information stored in the graph to prune its search.
The difficulty here is that for forward-chaining search, \GP's mutual exclusion
relations are not especially helpful, and instead \PGP\ uses
other kinds of information propagated {\em backwards} from
the goals.   In this sense, our objectives are similar to those of
Kambhampati and Parker \cite{KP99}.

We compare \PGP\ and \TGP\ to each other and to several other
probabilistic planners such as Buridan \cite{KHW95}, SPI \cite{BDG95},
and vanilla dynamic programming, on a variety of domains.  
Comparing \PGP\ and \TGP\
to each other allows us to estimate how far off we are from
our ideal objective.   In particular, from the perspective of \GP, two
key questions are: ``to what 
extent can the planning graph representation be used to speed up {\em
forward search}?'' and ``Can \GP's backward-chaining search produce a
near-enough-optimal solution?''


\comment{
%% 
%% An especially well-studied extension to deterministic planning is to
%% allow actions with probabilistic outcomes.  Indeed, this is the
%% setting of Markov Decision Processes (MDPs).  An MDP is typically
%% described as a set of states, in which each action has an associated
%% probabilistic transition function.  The planning agent knows at all
%% times what state it is in, it just cannot necessarily predict the
%% effect of any given action.  The MDP also specifies a reward function,
%% which for our purposes we can simply think of as a partition of the
%% states into ``goal states'' and ``everything else''.  A solution to an
%% MDP (a {\em policy}) is a mapping from states to actions with the goal
%% of maximizing expected utility for some given utility function.  We
%% will be considering finite-horizon utility functions such as
%% ``maximize the probability of success within some given time $t$.''
%% These utility functions are not necessarily time-independent, so for
%% our purposes the ``state'' should be viewed as containing an entry for
%% the current time as well.

%% We present \PGP\ and \TGP, two new planners for probabilistic STRIPS
%% operators.
%%Both new planners assume that the initial state is known and that the
%%effects of executing a probabilistic action are known, fitting into
%%the framework of finite-horizon Markov Decision Processes (MDPs).
\PGP\ finds optimal finite horizon plans much like standard top-down
Dynamic Programming.   \PGP\ differs from a standard top-down DP solution in
that it uses information propagated backwards from the goals in the
planning graph to
constrain the search. Our motivations are similar to those of 
Boutilier et al.~\shortcite{BDG95}, though their
algorithms are quite different.  For reasons we describe more fully
below, \PGP\ uses a forward-chaining search on states, unlike the
backward search on goal-sets of the original \GP, and therefore takes
a substantial performance hit.  Nonetheless, \PGP\ appears to be quite
competitive with other approaches to probabilistic planning, and we
believe further substantial improvements should be possible.

\TGP\ is a more straightforward extension of \GP\ to the finite
horizon MDP framework.  We define an {\em trajectory} to be a sequence of
transitions in the MDP.  In other words, a trajectory is a sequence of
actions and outcomes leading from one state to another, such as ``I
turn the key in the ignition, the car starts, I drive to the airport,
get there in time for my plane, I catch my flight, and arrive at my
destination.''   Let us define the {\em probability of a trajectory} to be
the probability that the specified sequence of transitions are in fact
taken when the sequence of actions is performed (e.g., the car
actually starts, we actually get to the airport on time, and the
flight really arrives where it is supposed to).
Given some number of
time steps, \TGP\ produces the policy that for each state finds the
highest probability trajectory leading to a goal state and chooses the first
action on that trajectory.  If the MDP is actually a deterministic process,
then \TGP\ becomes the same as the \GP\ algorithm.
The difference between the \PGP\ policy and the \TGP\ policy
is similar to the difference between calculating the expectation and
choosing the most likely event from a probability distribution. 
\TGP\ is generally faster than \PGP\ in part because it can take
advantage of the mutual exclusions of \GP, and it can also be used as
an ``anytime planner'' by just computing the initial best trajectory, and
then replanning whenever we fall off the trajectory in the plan's execution.
However, \TGP\ may not necessarily produce the true optimal policy.
}


\subsection{Other related work}
%% Planning in a probabilistic setting is a classic problem.
%% Most closely related to our objectives are methods for
%% propositional planning, 
%% that use the propositional representation of states to avoid enumerating
%% a full state space. 
There is a long history of work in probabilistic planning. One of the
first planners designed specifically for probabilistic STRIPS-style
domains is \Bur\ 
\cite{KHW95}, extended to the contingent planner \Cbur\ by
\cite{DHW94}.  Unlike our work, these planners also considered
partially observability, but in general were quite slow.  Closer
to our motivations is Structured Policy Iteration (SPI) of
\cite{BDG95}.  SPI is designed for the fully observable MDP setting, and
attempts to use the propositional representation of states and actions
to find an 
optimal policy without expanding out the entire state space.
\Zander~\cite{ML99} and \Maxplan~\cite{ML98} by Majercik and Littman 
compile a planning problem onto a stochastic
satisfiability problem, solving the problem in that
representation. \Maxplan\ is a blind planner, while \Zander\ produces
contingent plans. 


There has also been work on probabilistic planning explicitly using
representations motivated by \GP.  In particular,
Boutilier et al.~\cite{BBG98} generalize \GP's pairwise
mutual-exclusion constraints to $k$-wise constraints, and examine the
reduction in the size of the MDP that is implicitly represented by the
layer at which the planning graph levels off.

The work of Dean et al.~\cite{DKKN95} 
has a close connection to the goals of \TGP.  That work finds an
initial trajectory using a forward search, and then attempts to
interpolate (in an anytime fashion) towards an optimal solution.

\section{\GP\ and its representation}
\GP\ \cite{BF97} is a planner for STRIPS domains.  These domains
consist of {\em initial conditions} that describe
the starting state of the world, {\em operators} which
describe the legal actions that may be performed, and {\em
goals} representing those facts that we wish to be true at the end
of a plan.  Operators have conjunctive preconditions, add-lists, 
and delete-lists.  For instance, in a blocks-world, the initial
conditions specify the starting configuration of the blocks, the goals
specify what we wish to be true about the blocks at the end of the
plan, and the operators specify our legal moves.

\GP\ is based on compiling such a planning problem into a
polynomial-size structure called a {\em planning graph}.  A planning
graph is a directed, leveled graph.  The first level has one node for
each proposition in the initial conditions.  The next level has a node
for each action (fully-instantiated operator) that might possibly be
performed at time 1: that is, one node for each action whose
preconditions all exist in the initial conditions.   The next level of
the graph lists all propositions that might be true at time 2: namely,
the union of the add-effects of all actions in the previous action
level, including the no-ops (for consistency,
\GP\ also includes a {\em no-op} action for each proposition that
simply propagates the proposition forward in time).  The next level
consists of actions that might possibly be performed at time 2, and so
forth. Edges in a planning graph connect actions to their
preconditions and their add and delete effects.

\GP\ begins by creating a planning graph forward from the initial
conditions until all of the goals appear in the graph.  It then
searches in a backward-chaining fashion.  If the recursive search does
not find a plan, then the graph is extended one more time step and the
process is repeated.  The planner also has a mechanism for eventually
halting if, in fact, the problem has no solution.

The planning graph allows for several important
optimizations including:
\begin{enumerate}
\item Propagating pairwise {\em mutual
exclusion} relations between propositions and between actions forward
through the graph while it is being created.  These relations tell the
planner that, for 
instance, propositions $P$ and $Q$ cannot be both made true by time
step 4, and are used to prune the backward search.
\item Allowing the plan to perform several operators in parallel so
long as they do not conflict with each other.
\end{enumerate}
Memoizing the results of unsuccessful searches is also
used, and improvements to \GP\ use a number of other optimizations as
well.  For more details see \cite{BF97,KNHD97,KLP97}. 

\subsection*{Representing probabilistic actions}

In this paper, we consider probabilistic actions.
Specifically,  we consider operators with conjunctive preconditions
and with several sets of add  and delete effects, each set having an
associated probability.  For example, an ``open
door'' action might require that the door be unlocked, and with 88\%
probability actually open the door, with a 10\% probability do
nothing, and with 2\% probability pull off the handle.  We assume that
the outcome that actually occurred will always be known when executed
(the MDP not the POMDP setting). 


%% We now describe changes to the graph itself used by both \PGP\ and
%% \TGP\ in order to accommodate probabilistic actions. 
To represent these kinds of operators, the graph is constructed in the
normal manner except that each action contains a list of possible
``outcomes'', each with its associated probability, and then each
outgoing edge of the action indicates which outcome produced that
edge.  For instance, suppose that we have an operator that with
probability 0.7 deletes $G0$ and adds $G1$, and with probability 0.3
just adds $G1$.  Then, there would be two outcomes, one with
probability 0.7 and one with probability 0.3.  There would also be
three outgoing edges.  One edge would be a delete edge leading to $G0$
and associated with the first outcome, one would be an add edge
leading to $G1$ and associated with the first outcome, and one would
be an add edge leading to $G1$ and associated with the second outcome.
Since each outcome contains its probability, this representation is
sufficient to reconstruct
the definition of the operator.

\section{\PGP}\label{sec:pgp}
A standard algorithm for solving a finite-horizon MDP is dynamic
programming.  One begins by computing the value of each state for a time
horizon of 0, then uses that to compute  
values for a time horizon of 1, and so on up to the given horizon $t_{max}$.
In propositional planning, 
because we have an initial state and the state space is not explicitly
enumerated, it is more natural to do 
this in a recursive top-down fashion, as described in Figure
\ref{topdownDP}.   Notice that top-down DP,
because it stores the result of each computation, explores each state
at most once per time step just like bottom-up DP.

\PGP\ begins with this vanilla top-down Dynamic Programming as its
starting point,\footnote{In particular, this is a forward-chaining
search, and allows only one non-noop action per time step. It would be
interesting to consider parallel actions as in \GP, but the
computation becomes quite a bit hairier in the probabilistic setting.}
but uses the planning graph to prune its search.  In
particular, \PGP\ propagates two distinct kinds of
information through the graph.  The first kind tells the planner how
various nodes in 
the graph contribute to solving the problem goals, and the second
focuses more on how near or remote that contribution is.
Both kinds of information are used in
the same way: to tell the planner when the path it is currently exploring
provably cannot reach the goals within the given time horizon
and therefore it may safely return failure in its recursive
call.  The two types of information are given below.

\begin{figure}[t]
\boxer{

{\small
DPsolve$($state $s$, time $t)$: Compute $value(s,t) = $ best
possible probability of success within the time window for a
contingent plan starting from state $s$ at time-step $t$.

\begin{enumerate}
\item If $t = t_{max}$ then return 0 if goals not satisfied, else
return 1.
\item If already-visited$(s,t)$, then return the previously-computed
value.
\item For each possible action $a$,
\begin{enumerate}
\item For each possible state $s'$ that could result from taking action $a$ in
state $s$, recursively call DPsolve$(s',t+1)$.
\item Let $value(s,a,t)$ be the probability-weighted average of the results.
\end{enumerate}
\item Let $value(s,t) = \max_a value(s,a,t)$.  Return this quantity,
after first storing it in case we ever visit $s$ at time $t$
in a later recursive call.  Also, return argmax$_a
value(s,a,t)$ as the optimal action.
\end{enumerate}
}}
\caption{Standard top-down Dynamic Programming\label{topdownDP}}

\vspace{-0.1in}
\end{figure}

\comment{
In particular, given a state of the world at some time $t$ (e.g.,
think of the initial state), we consider each possible action that
might be performed.  For each action, the planner recursively computes
the expected utility of that action.  This is done by taking the
probability-weighted average, over the different possible outcomes of
that action, of the utility of the state at time $t+1$ resulting from
that outcome (where this utility is computed recursively).  The
planner then chooses the action of highest utility, which gives the
utility of the current state at time $t$, and then ``memoizes'' the
triple $(state, action, utility)$ so that the computation for any
given state at any given time step is performed at most once.  The
base case of the recursion is when either the goals have all been
achieved or the time limit $t_{max}$ has been reached.  To simplify
the code, we only allow the planner to perform one non-noop action
per time step in any given execution path.  This is the starting point
for the \PGP\ planner.

\PGP\ as stated so far is substantially slower than \GP.  The problem 
is that the planning graph contains only information propagated
forwards from the initial conditions.  Since we are forward-chaining,
what we want is information propagated backwards from the goals.
We now describe two types of information that can be quickly
propagated backwards in this way and can be used by \PGP\ to
significantly speed up the search.
}

\subsection{Unary and pairwise ``needed'' nodes}  One very
simple optimization is to delete nodes from the planning graph that do
not have any paths to the goal literals, by performing a backward
sweep through the graph.  This simple form of
relevance analysis effectively collapses multiple states together, and
is roughly equivalent to
the notion of relevance used by Knoblock \cite{Knoblock94b}.
For an even greater savings, we assign to each node
not removed a vector indicating which goal literals {\em are}
reachable from this node.  The planner uses
this information when at some state $S$ by looking at the vectors
assigned to each literal in $S$, and checking to see if any goal is
missing from all the vectors; if so, then it knows it may backtrack
immediately.  In fact, if there is only one non-noop action that
creates some goal, then the preconditions
to this action can be used instead of that goal for the purposes of
defining these vectors.  This can be viewed as a crude but  
computationally cheap version of the fact-generation trees of
Nebel et al.~\cite{NebelDK97}. 


A more interesting version of this information is a
pairwise notion of ``neededness''.   Suppose node $P$ {\em does} have one or more
paths to goal literals, but all of these paths use node $Q$ 
as well (e.g., all potentially useful actions that have $P$ as a
precondition also have $Q$ as a precondition); in that case, we can
add a ``$P$ needs $Q$'' edge to the graph, allowing
the planner to drop literal $P$
from its state if literal $Q$ is not also present.  Specifically, we
say that proposition $P$ {\em needs} proposition $Q$ if each action
with $P$ as a precondition 
either (a) has $Q$ as a precondition too, or (b) needs some action
that has $Q$ as a precondition.  Similarly, a non-noop action $A$ needs
noop $B$ if all add-effects of $A$ need the result of $B$ (and none
are equal to it); a noop action $A$ needs action $B$ if
the result of $A$ needs a proposition that can be created only through
$B$.\footnote{This asymmetry is the result of the planner only allowing
one non-noop action per time step.} 

For example, consider a domain in which a robot, initially with key in
hand, must move to the end of the hallway, unlock a door at the end,
and then drop the key in order to empty its hand for
some subsequent task.  In this case, the fact that the move-forward
action needs the noop-have-key action gets propagated back through
the entire graph, ensuring that the robot does not drop the key prematurely.

It is interesting to compare the information propagated here to the
``backward mutex'' constraints used by Kambhampati and Parker
\cite{KP99}.  They propagate the notion that ``$P$ and $Q$ are redundant''
in the sense that one can confidently remove one of them
from any state that contains both.  That information seems more
difficult to propagate appropriately in a probabilistic setting and we
have not attempted to do so.


\subsection{Value propagation}
The idea for this second kind of information is to store values on
nodes of the
graph that allow one to compute a ``permissible heuristic'' for an
$A^*$-style search.  This method empirically produces an even greater
savings than the one above.

Imagine that reaching a goal state (one in which all the problem goals
are satisfied) is worth $t_{max}$ dollars, but performing a non-noop
action costs \dollar 1. In this case, the {\em true value} of a state
that can reach the goals in $i$ steps is \dollar$(t_{max}-i)$.  Notice
that if a state $S$ at time step $t$ is worth less than \dollar$t$,
then this means it cannot possibly reach the goals by time $t_{max}$.
Thus, a magic oracle that returned the true value of any given state
would be quite useful.
The idea of {\em value propagation} is to propagate heuristic values
(hvalues) through the nodes of the graph such that the heuristic value
of any state $S$, defined to be the {\em sum} of the hvalues of the
nodes of the state, is guaranteed to be greater than or equal to the
true value of $S$.  
If the planner finds that the heuristic value of its current state at
time $t$ is less than \dollar$t$,
then it can confidently backtrack immediately. 

Specifically, we begin by dividing the final value $t_{max}$ evenly
among the problem goals at time $t_{max}$, breaking ties arbitrarily
(all hvalues will be integral).  
We propagate hvalues on propositions at time $t+1$ backwards to
actions at time $t$ as follows: the hvalue of a noop is the hvalue of
its effect; the hvalue of a non-noop action $a$ is $-1 + \sum_{e \in  
{\rm addeffect}(a)} hvalue(e)$,  where preconditions that are not 
deleted are viewed as add-effects for this purpose.  We view
probabilistic actions (which may have several possible outcomes) as if
they were user-controllable for this computation: that is, a probabilistic
action with $k$ possible outcomes is treated as $k$ separate   
deterministic actions, one for each possibility, each with its own
value.



Values on actions at time $t$ are then propagated to propositions at
time $t$ as follows.  We begin with the noops: each gives its value to its
precondition. We then consider each non-noop action in
turn.\footnote{The order in which the actions are examined can, in
principle, affect the values, but we have not attempted to optimize the
ordering in the planner.}  For each action, we compare its value to
the sum of the hvalues of its preconditions.  If its value is larger,
we give the difference to the preconditions; the semantics
is that the total value of the preconditions is the maximum of
performing or not performing this action.  As a
heuristic, we distribute the value evenly among just the preconditions
deleted by the action (breaking ties arbitrarily) if any exist; if
none exist, we distribute the value evenly among all
preconditions. (Actions with no 
preconditions are given a fake ``always-true'' precondition that is
true in the initial conditions and never deleted.)  An example is
given in Figure \ref{fig:value}.

\begin{figure}[t]
\centerline{\psfig{figure=blocksworld.eps,width=4.0in}} 
\caption{RHS of graph for simple blocksworld domain, ending at $t=4$. 
Some noops are not shown. Numbers indicate hvalues. Notice that the
planner will return from any 
state at time $t=2$ that doesn't have
{\tt clearB} (it will never reach the impossible state in which it is
holding A and B).\label{fig:value}}

\vspace{-0.3in}
\end{figure}

This method is {\em legal} in the sense that if a state 
at time $t$ has a sum of hvalues less than $t$, then it cannot
possibly reach the goals.  Unfortunately, it can at times be an
over-estimate, because of a double-counting that may occur as
values are propagated.


The two kinds of information described above each have a different
purpose.  The first kind asks {\em is} a node useful, and {\em for
what}?  The second focuses more on {\em how long} the path is
from some node to its eventual use.

\subsection{Why forward-chaining?}\label{whyforward}

Finding an optimal policy with a planning graph appears to be
considerably more difficult for a backwards search than a forwards
one.  Consider, for example, a domain in which the initial conditions
contain the literals $A$ and $B$, and the goal is to achieve $G$.
There are 2 operators: $OpA$ requires $A$, deletes $A$ and with
probability 0.5 adds the goal $G$; $OpB$ requires $B$, deletes $B$ and
with probability 0.5 adds $G$. See Figure \ref{fig:whyforward}.

\begin{figure}[t]
\centerline{\psfig{figure=no_backward.eps,width=2.5in}} 
\caption{Planning graph for the simple domain of section 
\ref{whyforward}.  Dotted lines represent deletes, and irrelevant 
nodes have been removed.\label{fig:whyforward}} 

\vspace*{-0.2in}
\end{figure}

For this domain, the plan $OpA, OpB$ has a 75\% chance of
success.  However, to find this plan by reasoning backwards in the planning
graph appears to require combining seemingly unrelated goal sets.
%$
%% For instance, consider the usual backward
%% chaining on goal sets.  Given the goal $G$ at time 3, one way to
%% achieve it is via a no-op, another is via $OpA$, and another is via
%% $OpB$.  Thus, at time 2 there are three goal sets under consideration:
%% $\{G\}$, $\{A\}$, and $\{B\}$, with probabilities 1.0, 0.5, and 0.5
%% respectively of achieving our final goal.  $\{A\}$ and $\{B\}$ are
%% both achievable with noops, while $\{G\}$ is achievable with either
%% $OpA$, $OpB$, or $noop-G$.  Thus, at time 1 the interesting goal sets
%% under consideration are $\{A\}$ and $\{B\}$, all with probability
%% $0.5$ of achieving our goal.  But, this doesn't lead to the optimal
%% plan.  
In particular, to produce the optimal plan, we need at time 2 to
consider the goal set $\{G\}$ (which achieves our goal via a noop) and
$\{B\}$ (which has probability 0.5 of achieving the goal via $OpB$)
together.  We then need to realize that if $OpA$ is  
performed from $\{A,B\}$ at time 1, then each of the two outcomes of
the action will lead to one of these goal sets at time 2.  (Note:
these are two distinct {\em goal sets}, not just two goals in the same
set.)  This kind of reasoning seems possible, but
it also seems that it would require time quadratic in the number of
goal sets at any given time step (or cubic if some action has three
possible outcomes). The problem stems from the fact that we are
dealing with {\em goal sets} (which are only subsets of states) rather
than the states themselves in our backward-chaining search, unlike in
bottom-up DP.  Perhaps some way can be found around these
difficulties, or some way to make this not too expensive in
``typical'' domains.  In any case, this is the reason we choose to use
forward chaining.

Smith and Weld \cite{SW98} and Weld et al.~\cite{WAS98} use a
different approach that allows for backward-chaining search on
goal-sets in the presence of uncertainty.  They handle uncertainty in
the framework of \GP\ by essentially creating one graph for each
``possible world''.  For instance, if one views the outcome of a
probabilistic action as being determined by the flip of an associated
coin, then there would be one graph for each possible sequence of coin
flips.  Ideally, one would like to use the same kind of search but at
the same time handling the (possibly exponentially many) possible
worlds within the context of a single planning graph.


\section{\TGP}

\TGP\ uses a backward chaining search (essentially the same as the
original \GP) and finds an optimal trajectory from the initial state
to the goals.  A {\em trajectory} is a sequence of actions and
outcomes leading from one state to another, such as ``I turn the key
in the ignition, the car starts, I drive to the airport, get there in
time for my plane, I catch my flight, and arrive at my destination.''
An optimal trajectory is the highest probability sequence of states
and actions leading to the goal.  When two trajectories
have the same utility, trajectories which do noops later are preferred
as in \GP.  This bias is especially important in a probabilistic
setting because it maximizes the amount of time available for
recovery in case the trajectory experiences a failure.

\TGP\ can be used as a subroutine to manufacture a complete policy by
simulating execution of the trajectory to detect the state and time of
unexpected outcomes not on the trajectory.  Optimal trajectories for
these unexpected outcomes can then be found and simulated forward to
find new unexpected outcomes.  The recursion terminates when there are
no more unexpected outcomes.  More naturally, \TGP\ can be used in an
online fashion 
after the optimal trajectory is discovered.  While the first action is
executing (in the real world), \TGP\ can be planning for subsidiary
trajectories.   Thus, the important time quantity to measure for \TGP\ is the
time to find the optimal trajectory rather than the time to find a
complete policy. 

\TGP\ starts by building a planning graph with probabilistic outcomes
included.  The backward-chaining search is done exactly as in \GP,
except instead of the recursion returning a binary value
(success/fail), it returns a real-valued success probability for the
best sub-trajectory.  In the \TGP\ search algorithm, the probability
of the trajectory is determined by recursively multiplying the
probability of a step succeeding by the probability of the partial
trajectory already explored.  The same set of optimizations that \GP\ 
uses are used by \TGP.  Mutual exclusions are more complicated because
it is possible for an operator to interfere with one outcome
of another probabilistic operator but not with a
second outcome.  In \TGP, a pair of operators is made exclusive when any
pair of outcomes interfere.  Instead, we could lose the notion of
``exclusive operators'' and replace it with a notion of ``exclusive
outcomes'' but we do not do that.
\TGP\ can also be run in an iterative deepening mode as for \GP.  In
order to do this, the desired trajectory probability must be given in
advance.  The algorithm terminates as soon as a trajectory with at
least the desired probability is found.

The \TGP\ algorithm is fast in comparison to \PGP\ because it only
outputs {\em partial policies}, solves an inherently less complex
problem and uses a backward chaining search which can take advantage
of the mutual exclusions propagated forward in the building the graph.
It is interesting to consider when \TGP\ will produce a (near)
optimal policy and when the choices it makes will be substandard.
This will be discussed in the following  examples.

\section{Examples and Empirical Results}
We now describe several example domains and give results of running
\PGP, \TGP, and other comparison planners on them.  The purpose of these
experiments is twofold: to examine the speed of the proposed planners,
and to explore the extent to which the plans produced by \TGP\ are
optimal or close to it.  \PGP\ and \TGP\ are written in C.   The
planners we compare to are  
\begin{itemize}
\item Top-down Dynamic Programming (Figure \ref{topdownDP}).  
%% Becuase \PGP\ is a strict 
%% improvement on this, one certainly expects \PGP\ to perform better,
%% but the question is how much: specifically, what reduction in
%% the number of states searched is achieved by the information propagated
%% by \PGP, described in Section \ref{sec:pgp}.
\item Buridan \cite{KHW95}: in compiled Lisp.
\item Blackbox \cite{KS99} (on deterministic domains): written in C.
\item SPI \cite{BDG95}: an infinite-horizon discounted MDP solver,
written in C.
\end{itemize}

\noindent{\bf Moats and Castles: }
This simple domain is an adaptation of one by Majercik and Littman
\cite{ML98}, in which the goal is to build a sand castle on the beach.
In our version, there are two operators. Dig-moat is a deterministic
action that increases the depth of a protective moat (there are 5
discrete depths), and build-castle is a probabilistic action for
creating the castle, whose success probability increases with the
depth of the moat.  The optimal finite-horizon plan for this problem
will consist of some number of dig actions, followed by a
remainder of builds, where the number of digs depends on the time
horizon and the specific success probabilities.  The problem as stated
has a very small state space; to make things more interesting, we 
consider having multiple castles, each with its own moat.

We consider this domain in part because it gives a simple illustration of
when \TGP\ does or does not produce optimal plans.  In particular, for
the case of one castle, the optimal {\em trajectory} is to dig as many
times as possible, followed by one final build operation (and then
noops up to the time horizon).  This may or may not be a trajectory of
the optimal policy; in particular, the optimal policy may have fewer
dig operations, if, for instance, deepening the moat has only a small
effect on the success probability of the build operation.

We describe performance results  in Table \ref{table:moat}.  For this
domain, when the time 
horizon is large, the information
propagated by \PGP\ does not provide much of a gain.  That
is because in this case, almost all states {\em can}, in principle,
lead to solving the goals, and the information propagated is only
intended to prune states with no chance of success. \TGP\ scales
better with time horizon but worse with number of castles, compared to
\PGP; the latter effect appears to occur because of interaction
between parallel and probabilistic actions.

\begin{table}[t]
\fbox{
\begin{tabular}{c|l|l|l|l}
	& 1 castle  & 2 castles & 3 castles  & 4 castles\\ \hline 
DP  & .01 [.01] sec   & .01  [.01] sec   & .01  [.09] sec    & .03 [0.54] sec\\
        & 44 [114] states & 448 [2300] states& 1977 [22113]
states& 5996 [138308] states \\ \hline 
PGP & .01 [.01] sec   & .01 [.01] sec   & .01 [.07] sec    & .01 [0.36]
sec\\
        & 40 [110] states & 256 [1900]  states& 909 [16389]
states& 1776 [89276] states \\ \hline 
TGP & .01 [.01] sec   & .01  [.01] sec   & .01 [.05] sec & .07 [0.45] sec\\
    &  37 [97] sets & 259 [954] steps & 1959 [9974] sets & 13855
[102569] steps\\ \hline
SPI & .05 sec   & 0.21 sec & 2.73 sec    & 36.3 sec\\ \hline
Bur & 1 sec [$>5$ min] & 6 sec [$>5$ min]& $>5$ min    & $>5$ min\\
    & 427 [$>$60k] plans & 4823 [$>$60k] plans & $>$60k plans
& $>$60k plans 
\end{tabular}}\\

\caption{\PGP\ (PGP), \TGP\ (TGP), top-down DP (DP), SPI, and \Bur
(Bur) on the moat and castles problem with varying numbers of
castles. 
SPI is run with discount factor 0.9.  The other planners are given
time horizon of 5 or 10 (for \Bur, this is done by providing a desired
success probability); values for horizon of 10 are given in square
brackets.  Running times are given on a PII-450 xeon with 512 MBytes
of memory. 
\label{table:moat}}

\vspace*{-0.4in}
\end{table}

\noindent{\bf Probabilistic Blocks: }
In the standard blocks-world domain, we can {\tt pickup} a block from
the table, {\tt putdown} a block onto the table, {\tt unstack} a block
from another block, and {\tt stack} a block on another block.  So,
for instance, to pick up a block from the table and place it on
another block takes two time steps.   Imagine we augment this domain
with a probabilistic operator {\tt faststack} that can move a block
from the table onto the top of another block in one time step, but it
only succeeds with a 70\% probability; with a 30\% probability it has
no effect.  This setting is interesting because the optimal action
depends on the time-to-go.  

\comment{
It also exhibits interesting
behavior if one refines one's objective to that of minimizing expected
time, subject to maximizing the probability of success.   For
instance, suppose the initial state is a stack of blocks ABCD (A 
is on top), and the goal is a stack BCDA.  The shortest policy with
100\% probability of success takes 12 time steps.  However, if the
goal is to minimize expected time, then given a horizon of 13 steps
there is a policy with expected time 10.9 by using the
{\tt faststack} operator so long as there is time remaining to ``fool
around''.  Given a horizon of 20 steps there is a
policy with expected time 10.3. 
}

Note that the optimal trajectory will always choose the deterministic
operators if there is sufficient time, otherwise it will choose {\tt
faststack}.  Thus, in this domain, \TGP\ does, in fact, lead to an
optimal policy.  Results for this domain are given in Table \ref{table:blocks}.

\begin{table}[t]
\fbox{
\begin{tabular}{c|l|l|l|l|l|l}
	& 2 blocks & 3 blocks & 7 blocks & 7 blocks & 7 blocks & 7 blocks\\
	& $(t=4)$  & $(t=8)$  & $(t=18)$ & $(t=20)$ & $(t=22)$& $(t=24)$\\ \hline
DP      & .01 sec  & .01 sec  & 8.27 sec & 14.53 sec & 20.88 sec & 25.43 sec \\
        & 18 states& 194 states& 974k states & 1607k states &
2239k states & 2646k states \\ \hline
PGP	& .01 sec  & .01 sec  & 1.34 sec & 4.97	sec  & 10.83 sec & 14.49 sec\\
	& 6 states & 111 states& 163k states & 599k states & 1211k
states & 1549k states\\ \hline
TGP	& .01 sec  & .01 sec  & .25 sec & .42	sec  & .53 sec & .61 sec\\
        & 11 sets  & 29 sets  & 126 sets & 718 sets& 1280 sets& 1323 sets \\ \hline 
SPI	& 1.17 sec & 28.54 sec& -- & -- & -- & -- \\ \hline
Bur	& 1 sec	   & --       & -- & -- & -- & -- \\ 
        & 783 plans& $>$100k plans &  $>$100k plans & $>$100k plans & $>$100k plans & $>$100k plans
\end{tabular}}\\

\caption{Results for the probabilistic blocks problem described in the
text.  The 
initial state is a tower ({\tt ABCD...}) and the goal 
is the same tower except that the block that used to be on top is now
on the bottom ({\tt BCD...A}).  SPI finds a policy that
applies from all possible starting states, so in a sense it is
unfairly penalized in this experiment (to partially alleviate
this, for SPI we discarded actions not used in any
reasonable trajectory from our initial state from the domain
description). 
\label{table:blocks}}
\vspace*{-0.2in}
\end{table}

\noindent{\bf 8-puzzle and Flat-tire: }
In order to compare to deterministic planners, we also considered
several deterministic domains, in particular the flat-tire problem of
Russell, and the 8-puzzle problem.   The 8-puzzle problem is
interesting because there is no special advantage to
backward-chaining on this problem.  We consider the goal of achieving
board state  {\tt 
ABCDEFGH\_} (reading left to right, top to
bottom) from two different initial states: one in which a solution
requires 18 steps and one in which a solution requires 30 steps (this
is the case of initial board {\tt HGFEDCBA\_}).
Results are given in Table \ref{table:deterministic}.  Note that \PGP\
is the fastest of all planners tested (even the deterministic ones) on
this problem.

\begin{table}[t]
\fbox{
\begin{tabular}{c|l|l|l}
	 & flat-tire    & 8-puzzle  & 8-puzzle \\ 
         & (19 step)    & (18 step) & (30 step) \\ \hline 
DP       & 0.3 sec      & 0.63 sec   & 27.61 sec \\
         & 48851 states & 41242 states& 1777759 states \\ \hline
PGP      & .05 sec     & 0.14 sec   & 6.56 sec   \\
         & 3661 states  & 2069 states& 437722 states \\ \hline
TGP      & .04 sec      & 0.8 sec   & 43.56 sec   \\
         & 411 sets & 461  sets       & 98946 sets\\ \hline
Blackbox & .08 sec   & 0.93 sec & timeout \\ \hline
BlackboxGP& .08 sec   & 0.93 sec & 45.56 sec \\ \hline
BlackboxWS& 0.18 sec & timeout & timeout
\end{tabular}}\\

\caption{Results on the flat-tire
domain, and the easy and hard 8-puzzle problems.  Blackbox was run in
its default mode, with {\tt -solver graphplan} (BlackboxGP), and with
{\tt -solver walksat} (BlackboxWS).
\label{table:deterministic}}
\vspace*{-0.3in}
\end{table}

\vspace*{-0.1in}

\section{Discussion and Conclusions}\label{sec:concl}

\vspace*{-0.1in}
\PGP\  performs a forward search to find an optimal
contingent plan, using information stored in
the graph to collapse and prune away unnecessary states. On problems
such as blocks-world, flat-tire, and 8-puzzle, this pruning provides a
substantial speedup. The value information seems to provide the
greatest savings in general, with the information on the eventual
purpose, if any, of each node in the graph providing a smaller but
still significant help.
\PGP\ is still 
in general slower than \GP, in part we believe because we have not yet
found the best way to propagate information backwards through the
planning graph.  One possible avenue would be to better integrate the
two kinds of information discussed above, for instance by separating
the hvalues into different ``flavors'' depending on which goal they
are intended for.  It would also be helpful to propagate more
probabilistic information, such as an upper-bound on the probability
of reaching the goals, which could then be used to prune search.
Finally, it would be interesting to explore whether knowledge of the
\TGP's more quickly-constructed policy could guide \PGP's search.

The planners implemented apply to problems for which the objective is
to maximize the probability of satsifying the problem goals within the
given time window, or the related goal of minimizing expected
completion time.  More general MDP problems are often given by
specifying rewards for performing certain (noop or non-noop) actions.
It appears that some of the kinds of information propagated here
should be useful in those more general settings, and it would be
interesting to see if this generalization could be made without
a sacrifice in performance.\\

\noindent
{\bf Acknowledgements.}
This
research is sponsored in part by NSF National Young
Investigator grant CCR-9357793, NSF grant CCR-9732705 and an
AT\&T / Lucent Special Purpose 
Grant in Science and Technology.
We would like to thank the anonymous reviewers for their detailed,
thoughtful, and helpful comments.

Source code is available at {\tt http://www.cs.cmu.edu/\~{}avrim/pgp.html}.

%%\bibliographystyle{alpha}
%%\bibliography{/afs/cs/usr/avrim/Bibs/planning}
\begin{thebibliography}{DKKN95}

{\small

\bibitem[ASW97]{ASW97}
C.~R. Anderson, D.~E. Smith, and D.~S. Weld.
\newblock Conditional effects in {G}raphplan.
\newblock unpublished manuscript, 1997.

\bibitem[BBG98]{BBG98}
C.~Boutilier, R.~I. Brafman, and C.~Geib.
\newblock Structured reachability analysis for {M}arkov {D}ecision {P}rocesses.
\newblock In {\em Proceedings of the Fourteenth Annual Conference on
  Uncertainty in Artificial Intelligence (UAI--98)}, pages 24--32, 1998.

\bibitem[BDG95]{BDG95}
C.~Boutilier, R.~Dearden, and M.~Goldszmidt.
\newblock Exploiting structure in policy construction.
\newblock In {\em IJCAI95}, pages 1104--1111, Montreal, 1995.

\bibitem[BF97]{BF97}
A.~Blum and M.~Furst.
\newblock Fast planning through planning graph analysis.
\newblock {\em Artificial Intelligence}, 90:281--300, 1997.

\bibitem[Byl97]{Bylander97}
T.~Bylander.
\newblock Linear programming heuristic for optimal planning.
\newblock In {\em Proceedings of the Fourteenth National Conference on
  Artificial Intelligence}, 1997.

\bibitem[DHW94]{DHW94}
D.~Draper, S.~Hanks, and D.~Weld.
\newblock Probabilistic planning with information gathering and contingent
  execution.
\newblock In {\em Proceedings of the 2nd International Conference on Artificial
  Intelligence Planning Systems}, pages 31--37, 1994.

\bibitem[DKKN95]{DKKN95}
T.~Dean, L.~P. Kaelbling, J.~Kirman, and A.~Nicholson.
\newblock Planning under time constraints in stochastic domains.
\newblock {\em Artificial Intelligence}, 76, 1995.

\bibitem[GK97]{GK97}
B.~C. Gazen and C.~A. Knoblock.
\newblock Combining the expressiveness of {UCPOP} with the efficiency of
  {G}raphplan.
\newblock In {\em Proceedings of the Fourth European Conference on Planning},
  1997.

\bibitem[KHW95]{KHW95}
N.~Kushmerick, S.~Hanks, and D.~Weld.
\newblock An algorithm for probabilistic planning.
\newblock {\em Artificial Intelligence}, 76:239--286, 1995.

\bibitem[KLP97]{KLP97}
S.~Kambhampati, E.~Lambrecht, and E.~Parker.
\newblock Understanding and extending {G}raphplan.
\newblock In {\em Proceedings of the Fourth European Conference on Planning},
  September 1997.

\bibitem[KNHD97]{KNHD97}
J.~Koehler, B.~Nebel, J.~Hoffman, and Y.~Dimopoulos.
\newblock Extending planning graphs to an {ADL} subset.
\newblock In {\em Proceedings of the Fourth European Conference on Planning},
  September 1997.

\bibitem[Kno94]{Knoblock94b}
C.~Knoblock.
\newblock Automatically generating abstractions for planning.
\newblock {\em Artificial Intelligence}, 68(2):243--302, 1994.

\bibitem[KP99]{KP99}
S.~Kambhampati and E.~Parker.
\newblock Making graphplan goal-directed.
\newblock In {\em ECP99}, September 1999.

\bibitem[KS99]{KS99}
H.~Kautz and B.~Selman.
\newblock Unifying {SAT}-based and graph-based planning.
\newblock In {\em IJCAI99}, 1999.

\bibitem[ML98]{ML98}
S.~M. Majercik and M.~L. Littman.
\newblock {MAXPLAN}: a new approach to probabilistic planning.
\newblock In {\em AIPS}, pages 86--93, 1998.

\bibitem[ML99]{ML99}
S.~M. Majercik and M.~L. Littman.
\newblock Contingent planning under uncertainty via stochastic satisfiability.
\newblock In {\em AAAI}, 1999.

\bibitem[NDK97]{NebelDK97}
B.~Nebel, Y.~Dimopoulos, and J.~Koehler.
\newblock Ignoring irrelevant facts and operations in plan generation.
\newblock In {\em Proceedings of the Fourth European Conference on Planning},
  pages 338--350, September 1997.

\bibitem[SW98]{SW98}
D.~E. Smith and D.~S. Weld.
\newblock Conformant graphplan.
\newblock In {\em AAAI98}, 1998.

\bibitem[WAS98]{WAS98}
D.~S. Weld, C.R Anderson, and D.~E. Smith.
\newblock Extending graphplan to handle uncertainty and sensing actions.
\newblock In {\em AAAI98}, 1998.
}

\end{thebibliography}

\end{document}
