\documentclass[11pt]{article}

\usepackage{jair}
\usepackage{theapa}
%\usepackage{aaai}
%\usepackage{times}
%\usepackage{epsfig}
%\usepackage{latexsym}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{ifthen}
\usepackage{array}
\usepackage{url}

\newcommand{\eqdef}{\stackrel{\hbox{\tiny{def}}}{=}}
\newcommand{\pair}[2]{{\langle #1,#2\rangle}}
\newcommand{\var}[1]{\mbox{${\mbox{\sf{#1}}}$}}
\newcommand{\denselist}{\itemsep 0pt\partopsep 0pt}
\newcommand{\argmin}{\operatornamewithlimits{argmin}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newenvironment{Proof}[1][]{{\emph{\ifthenelse{\equal{#1}{}}{Proof: }{Proof #1: }}}}{\hfill$\Box\!\!$}
\newcommand{\Omit}[1]{}

%\newcommand{\strips}{\textsc{strips}}
\newcommand{\strips}{Strips}
\newcommand{\seq}[1]{\langle#1\rangle}
\renewcommand{\prec}{\texttt{prec}}
\newcommand{\add}{\texttt{add}}
\newcommand{\del}{\texttt{del}}
\newcommand{\mdp}{MDP}
\newcommand{\pomdp}{\textsc{pomdp}}
\newcommand{\ppddl}{\textsc{ppddl}}
\newcommand{\mgpt}{mGPT}
\newcommand{\gpt}{GPT}
\newcommand{\hsp}{HSP}
\newcommand{\ipc}{\textsc{ipc-4}}
\newcommand{\icaps}{\textsc{icaps}}
\newcommand{\astar}{\textsc{a*}}
\newcommand{\ida}{\textsc{ida*}}
\newcommand{\adl}{\textsc{adl}}
\newcommand{\pddl}{\textsc{pddl}}

\newcommand{\lrtdp}{\texttt{lrtdp}}
\newcommand{\lrta}{\texttt{lrta}}
\newcommand{\rtdp}{\texttt{rtdp}}
\newcommand{\hdp}{\texttt{hdp}}
\newcommand{\hdpi}[1]{\texttt{hdp-#1}}
\newcommand{\vi}{\texttt{vi}}
\newcommand{\asp}{\texttt{asp}}

\newcommand{\zero}{\texttt{zero}}
\newcommand{\minmin}{\texttt{min-min}}
\newcommand{\minminlrtdp}{\texttt{min-min-lrtdp}}
\newcommand{\minminida}{\texttt{min-min-ida*}}
\newcommand{\atomforw}{\texttt{h-m}}
\newcommand{\atomforwn}[1]{\texttt{h-m-#1}}
\newcommand{\atomback}{\texttt{patterndb}}
\newcommand{\atombackn}[1]{\texttt{patterndb-#1}}
\newcommand{\ff}{\texttt{ff}}

\jairheading{24}{2005}{933--944}{12/04}{12/05}
\ShortHeadings{{\rm mGPT}: A Probabilistic Planner Based on Heuristic Search}{Bonet \& Geffner}
\firstpageno{933}

\begin{document}
\allowdisplaybreaks

\title{mGPT: A Probabilistic Planner Based on Heuristic Search}
\author{\name Blai Bonet \email bonet@ldc.usb.ve \\
        \addr Departamento de Computaci\'on \\ Universidad Sim\'on Bol\'{\i}var, Venezuela \\[1ex]
        \name H\'ector Geffner \email hector.geffner@upf.edu \\
        \addr ICREA \& Universitat Pompeu Fabra \\ Paseo de Circunvalaci\'on 8, Barcelona 08003, Spain}
\engineeringnote
\maketitle


\begin{abstract}
We describe the version of the \gpt\  planner used in the probabilistic
track of the 4th International Planning Competition (\ipc). This version, 
called \mgpt, solves Markov Decision Processes specified in the \ppddl\  language by 
extracting and using different classes of lower bounds along with 
various heuristic-search algorithms.
The lower bounds are extracted from deterministic relaxations
where the alternative probabilistic effects of an action are 
mapped into different, independent, deterministic actions. 
The heuristic-search algorithms use these lower bounds for focusing 
the updates and delivering a consistent value function over all 
states reachable from the initial state and  the greedy policy.
\end{abstract}


\section{Introduction}

\mgpt\  is a planner based on heuristic search for
solving Markov Decision Processes  ({\mdp}s)  specified in the high-level 
planning language \ppddl.  \mgpt\  captures a fragment of the functionality of 
the \gpt\  system that handles non-determinism and 
incomplete information, in both qualitative and 
probabilistic forms, including {\pomdp}s and Conformant 
planning \cite{bonet:aips2000}.

\mgpt\  supports several algorithms and admissible heuristic 
functions (lower bounds) that when combined generate
a wide range of solvers. The main algorithms are \lrtdp\  and \hdp.
Both are heuristic-search algorithms for solving MDPs 
that make use of lower bounds for computing a \emph{consistent}
value function $V$: a function with Bellman residuals  bounded by 
a user-provided parameter $\epsilon$ over all states reachable from
a given initial state  $s_0$ and the greedy policy based on $V$
\cite{bonet:lrtdp,bonet:hdp}.

The lower bounds are derived by solving relaxations of 
the input problem. Since the algorithms for solving the relaxations
are also based on heuristic search,
we have implemented ``stackable'' software components that
are created in sequence for computing complex heuristic
functions from simpler ones.

\Omit{
This document, that describe the features of the \mgpt\ planner,
is organized as follows. In the following two sections, we give
a brief description of the main algorithms and heuristics functions
implemented in \mgpt. Then, we describe how these algorithm and
heuristics are combined in order to generate a wide range of solvers.
We conclude with a discussion on the problem encodings used
in the competition and overall conclusions.
}


\section{Algorithms}

We divide the algorithms into two groups: those that deliver 
consistent value functions with respect to a user-provided
parameter $\epsilon$, and those that select actions in real time.
The first class of algorithms compute an $\epsilon$-consistent
value function $V$ for all states reachable from the initial
state $s_0$, and the greedy policy $\pi_V$ based on $V$.

In the following subsection, we give definitions of admissible and
consistent value functions, and greedy, partial and proper policies.
Then, we present the algorithms implemented by \mgpt.


\subsection{Consistent Value Functions, and Greedy, Partial and Proper Policies}

A value function $V$ is admissible if it is non-overestimating; i.e. if the
value $V(s)$ at each state $s$ is a lower bound on the optimal expected cost 
of starting at $s$. $V$ is $\epsilon$-consistent at state $s$ if
its Bellman  residual at $s$,
\begin{alignat}{1}
R(s)\ \eqdef\ 
   \bigg|V(s) - \min_{a\in A(s)}\ \bigg[ c(s,a) + \sum_{s'\in S} Pr(s'|s,a) V(s')\bigg]\bigg|\,,
\end{alignat}
is less than or equal to $\epsilon$. Here, $A(s)$ denotes the
actions that are applicable at $s$, $c(s,a)$ is the cost of applying
action $a$ in $s$, and $Pr(\cdot)$ is the probabilistic transition function.
If $V$ is 0-consistent at $s$, then we say that $V$ is consistent at $s$.

A state $s$ is reachable from the initial state $s_0$ and policy
$\pi$ if there exists a trajectory $s_0,s_1,\ldots,s_n$ such that
$s_n=s$ and $P(s_{k+1}|s_k,\pi(s_k))>0$ for all $0\leq k < n$.
In other words, if the state $s$ can be reached with positive probability
from $s_0$ in zero or more steps using the policy $\pi$.

It is known that the greedy policy $\pi_V$ based on the value
function $V$, defined as
\begin{alignat}{1}
\pi_V(s)\ \eqdef\ \argmin_{a\in A(s)}\ \bigg[c(s,a) + \sum_{s'\in S} Pr(s'|s,a) V(s')\bigg]\,,
\end{alignat}
is optimal when $V$ is $\epsilon$-consistent over \emph{all} states for a 
sufficiently small $\epsilon$. Yet, since our goal is to find an optimal
policy with respect to the initial state $s_0$ and the states reachable from
it, it is sufficient for $V$ to be admissible and $\epsilon$-consistent over
the states that are reachable from $s_0$ and $\pi_V$.

A partial policy $\pi$ is a policy that doesn't need to be defined for
all states. It is closed with respect to a state $s$ if $\pi$ is defined
over $s$ and all states reachable from $s$ and $\pi$, it is proper with
respect to $s$ if a goal state can be reached from every state reachable
from $s$ and $\pi$, and finally it is proper if it is proper with respect
to all states.


\subsection{Algorithms that Compute $\epsilon$-Consistent Value Functions}

For the first group of algorithms, \mgpt\ implements Value Iteration (\vi),
Labeled Real-Time Dynamic Programming (\lrtdp), and Heuristic Dynamic 
Programming (\hdp).

Value Iteration \cite{bertsekas:dp} is applied over the states
that can be reached from the given initial state and the available
operators, and yields an $\epsilon$-consistent value function over
all of them.\footnote{On undiscounted problems like those in probabilistic
planning, some conditions are neeeded in order for VI to finish with an
$\epsilon$-consistent value function \cite{bertsekas:dp}.}
\mgpt's \vi\ serves as a bottom-line reference for comparison with 
the other algorithms.

Labeled Real-Time Dynamic Programming \cite{bonet:lrtdp} is a 
heuristic-search algorithm that implements a labeling scheme on top of 
the \rtdp\ algorithm \cite{barto:rtdp}\ to improve its convergence.
\texttt{Lrtdp} works by performing simulated trials that start at the initial
state and end at ``solved'' states, selecting actions according to the
greedy policy $\pi_V$ and successor states according to their corresponding
transition probabilities. Initially, $V$ is the input heuristic function,
and the only solved states are the goal states. Then, each time an action
is picked at state $s$, the value of $s$ is updated by making it consistent
with the value of its successors. At the end of each trial, a labeling procedure
is called that checks whether new states can be labeled as solved: a state is
solved if its value and the value of all its descendents are $\epsilon$-consistent. 
The algorithm ends when the initial state is labeled solved. At that point
all states reachable from the initial state $s_0$ and the greedy policy $\pi_V$ are 
$\epsilon$-consistent. The labeling mechanism also guarantees that $\pi_V$
is a proper partial policy with respect to $s_0$.

Heuristic Dynamic Programming \cite{bonet:hdp} is the second heuristic-search
algorithm supported in \mgpt\  for solving MDPs. \texttt{Hdp} performs systematic depth-first
searches over the set of states reachable from the initial state $s_0$ and
the greedy policy $\pi_V$  looking for $\epsilon$-inconsistent states  and
updating their values.  On top of this search, a labeling scheme based on
Tarjan's strongly-connected components  procedure \cite{tarjan:scc},
identifies the states that are solved and that do not need to be revisited.
The initial value function is given by a heuristic function, and the algorithm ends
when the initial state is solved. As with \lrtdp, the labeling mechanism
guarantees that $\pi_V$ is proper with respect to $s_0$.


\subsection{Algorithms for Real-Time Action Selection}

The second class of algorithms do not attempt to solve the given \mdp; they
rather select actions in real-time after a limited amount of processing without
offering  any guarantees on the quality of the resulting policies. 
Algorithms in this group include an extension of the Action Selection for 
Planning algorithm (\asp) \cite{bonet:asp} for probabilistic domains, which 
is basically an \rtdp\ algorithm with lookahead. \texttt{Asp}, like \rtdp, performs
value function updates over states and so cannot get trapped into a loop.
Thus, although the policy delivered by \asp\ is suboptimal, it is a proper
policy; i.e. a policy that is \emph{guaranteed} to reach a goal state.


\section{Heuristics}

All these algorithms assume that the initial value function
is given by a heuristic function that provides good cost estimates,
and in particular, \lrtdp\ and \hdp\ expect this heuristic 
to be admissible. As described by \citeA{pearl:heuristics}, 
informative admissible heuristics can be obtained by solving suitable
relaxations of the input problem. Two such relaxations are supported 
in \mgpt: the min-min relaxation, and the \strips\ relaxation.
The first defines a (deterministic) shortest-path problem in the 
original state space; the second is used to define (deterministic) 
shortest-path problems in atom space.\footnote{Atoms refer to the 
propositional symbols used in the representation language, \ppddl\ 
in our case, to define the problem. The number of atoms is polynomial in 
the size of the input, while the size of the state space is, in general, 
exponential in the number of atoms.}
Thus, while the first is solved in time polynomial in the number of states, 
the shortest-path problems defined by the second are solved in time polynomial
in the number of atoms.
Both methods yield lower bounds on the expected cost to the goal from a given
state, yet the bounds produced by the min-min relaxation are stronger than
those produced by the \strips\ relaxation.


\subsection{Min-Min State Relaxation}

The idea behind the min-min relaxation is to transform the input
probabilistic problem, described by its Bellman equations
\begin{alignat}{1}
\label{eq:stoc}
V^*(s)\ \eqdef\ \min_{a\in A(s)}\ \bigg[c(s,a) + \sum_{s'\in S} Pr(s'|s,a) V^*(s')\bigg]\,,
\end{alignat}
into a deterministic shortest-path problem with Bellman equations of the form,
\begin{alignat}{1}
\label{eq:det}
V_{min}^*(s)\ \eqdef\ \min_{a\in A(s)}\, c(s,a) + \min\,\{ V_{min}^*(s') : P(s'|s,a)>0\}\,.
\end{alignat}
%One method to go from \eqref{eq:stoc} to \eqref{eq:det} is to transform
%each stochastic action $a\in A(s)$ into multiple deterministic actions $a_{s'}$,
%one per each $s'\in S$ with $P(s'|s,a)>0$.

At the level of the representation language, the min-min relaxation is
built by transforming each probabilistic operator of the form:
\begin{alignat}{1}
o\ =\ \langle\,\varphi,\,[\,p_1:\alpha_1,\ldots,p_n:\alpha_n\,]\,\rangle\,,
\end{alignat}
where $\varphi$ is the precondition of $o$ and each $\alpha_i$ is the $i$th
probabilistic effect (with probability $p_i$), into a set of \emph{independent and deterministic}
operators of the form:
\begin{alignat}{1}
o_i\ =\ \langle\,\varphi,\alpha_i\,\rangle\,,\quad 1\leq i\leq n\,.
\end{alignat}
Thus, in the min-min relaxation one can actually choose the most convenient
non-determinis\-tic effect of an operator,  and hence, the cost of the relaxation
is a lower bound on the expected cost of the original probabilistic
problem.

The min-min relaxation is a deterministic problem that can be solved by means of
standard path-finding algorithms. For example, it can be solved with Dijkstra's
algorithm, \astar, \ida, or a deterministic version of \lrtdp\ (i.e. a labeled 
\lrta\ algorithm \cite{korf:lrta}).

\mgpt\ provides two methods for computing the min-min heuristic from this relaxation:
\minminida, which uses \ida, and \minminlrtdp, which uses \lrtdp. Both versions are 
\emph{lazy} in the sense that the heuristic values of states are computed as needed
when the planner requires them.

\subsection{Strips Relaxation}

The \strips\ relaxation in turn converts the deterministic problem obtained
from the min-min relaxation into a Strips problem, and then obtains 
lower bounds for the original MDP by computing lower bounds for the
resulting Strips problem using the methods developed in classical 
planning \cite<e.g.,>{bonet:hsp-aij,haslum:heuristic,hoffmann:ff,edelkamp:pdbs,nguyen:heuristics}.
These methods run in polynomial time in the number of atoms yet,
unlike the min-min relaxation, require casting the
min-min relaxation into Strips format, a conversion that, like the 
conversion of ADL into Strips \cite{gazen:adl}, may require exponential
time and space (see below).

In \mgpt, the \strips\ relaxation is obtained directly from the original
problem, by first transforming the probabilistic operator into the form:
\begin{alignat}{1}
\label{eq:prev}
o\ =\ \langle\,\prec,\,[\,p_1:(\add_1,\del_1),\ldots,p_n:(\add_n,\del_n)\,]\,\rangle\,,
\end{alignat}
where $\prec, \add_i,\del_i$ are \emph{conjunctions} of literals that
represents the precondition, the $i$th add list, and the $i$th delete
list of operator $o$ respectively, and $p_i$ are probabilities that sum
to 1. In order to take the operators into form \eqref{eq:prev}, all 
disjunctive preconditions, conditional effects, and quantifiers are 
removed as described by \citeA{gazen:adl}.

Once all operators have the form \eqref{eq:prev}, the \strips\
relaxation is generated by splitting the  operators into
$n$ independent Strips operators of the form:
\begin{alignat}{1}
o_i\ =\ \langle\,\prec,\add_i,\del_i\,\rangle\,,\quad1\leq i\leq n\,.
\end{alignat}

The following heuristics are implemented in \mgpt\ upon the \strips\ 
relaxation. The first two are lower bounds on  the optimal cost of the \strips\
relaxation and hence on the optimal (expected) cost of the original MDP, the third
one is not necessarily a lower bound on either cost.

\begin{itemize}
\item The $h^m$ heuristics (\atomforw) \cite{haslum:heuristic} are heuristics that
      recursively approximate the cost of achieving a set of atoms $C$ from the
      initial state by the cost of achieving the most costly subset of size $m$ in $C$.
      They are computed by a shortest-path algorithm over a graph with nodes standing for 
      sets of at most $m$ atoms, and result in values $h^m(s)$ that estimate the cost of 
      reaching a goal state from $s$.
      %(The computation of each value $h^m(s)$ consists
      %in solving one such shortest-path algorithm in atom space.)
      We use the option \atomforwn{k}\ in \mgpt\ to refer to the $h^m$ heuristic with $m=k$.
\item Pattern database heuristics (\atomback) \cite{edelkamp:pdbs} compute optimal costs
      of relaxations of the Strips problem defined by some of the multi-valued variables
      that are \emph{implicit} in the problem (e.g. the location of a block in the blocksworld
      domain is an implicit multi-valued variable whose possible values are either the table or
      the top of any other block). This heuristic is also precomputed only once, at the beginning,
      and provides a lower bound on the cost of an arbitrary state to the goal.
      A pattern database is computed by projecting the Strips problem with respect to a set of
      atoms $A$ (those that define the multi-valued variables) and then solving
      the resulting problem optimally with Dijkstra's algorithm. Multiple
      pattern databases can be combined either by taking max or sum. In the latter
      case, the pattern database is referred to as additive.\footnote{Some conditions are required
      for adding two pattern databases such that the result remains admissible. 
      A sufficient condition is that $A \cap B = \emptyset$ if the sets $A$ and $B$
      are those used to build the projections respectively.}
      We use additive pattern databases as defined by \citeA{haslum:newh} where some
      constraints of the original problem are preserved into the projection;
      something that often results in stronger heuristics. \texttt{Patterndb-k}
      refers to a pattern database heuristic defined by $k$ multi-valued variables.
\item The FF (\ff) heuristic implements the heuristic function used
      in the FF planner \cite{hoffmann:ff}. It is computed by building
      the so-called \emph{relaxed} planning graph and finding a plan in it.
      The heuristic is then the number of operators in such a plan.
      The relaxed planning graph is the version of the graph constructed by
      Graphplan \cite{blum:graphplan-aij} when delete lists are ignored.
      It can be shown that computing the \ff\ heuristic can be done
      in polynomial time in the size of the input problem \cite{hoffmann:ff}.
      This heuristic however is informative but non-admissible. 
\end{itemize}
As it is shown below, these heuristics can be plugged directly into
the planning algorithm or they can be used to compute more informative
heuristics. For example, the \atomback\ heuristic can be used within
\ida\ to solve the min-min relaxation, which gives a stronger heuristic
than the \atomback\ heuristic. Thus, \mgpt\ implements algorithms and
heuristics as stackable software components so that an element in the
stack is used to solve the elements above it.


\section{Implementation}

This section gives some details on the implementation of \mgpt\ 
together with examples on its use. The \mgpt\ system is implemented
in C++ upon a preliminary parser offered by the organizers of \ipc.

\subsection{Hash Tables}

Perhaps the most important component of modern search-based planners
is the internal representation of states and hash tables. Since \mgpt\ 
uses different search algorithms and hash tables to solve a given 
instance (e.g. when more informative heuristics are computed from less
informative ones), good internal representations and hash table 
implementation are critical for good performance.

After grounding all atoms and operators, a state is represented
by the ordered list of the atoms that hold true in the state.
A state $s$ can appear associated with different data in multiple 
hash tables simultaneously. Thus, instead of having multiples ``copies''
of $s$, \mgpt\ implements a system-wide \emph{state-hash-table} that
stores the representation of the states referenced in all hash
tables so that entries in such tables simply contain a reference
into the state-hash-table. In this way, the planner saves time and space.

Another issue that has large impact on performance 
is the average number of collisions in each hash table.
Two points are relevant for keeping the number of collisions low:
the hashing function and the size of the hash table. For the 
former, we have seen that cryptographic hashing functions like
\textsc{md4} behave very well even though they are slower than
more traditional choices. For the latter, \mgpt\ uses hash tables
whose size is equal to a large prime number \cite{cormen:algorithms}.

\subsection{Algorithms and Heuristics}

Each algorithm in \mgpt\ is implemented as a subclass of the abstract
\texttt{algorithm} class whose members are a reference to a problem and,
in some cases, a reference to a hash table and a parameter $\epsilon$.
Similarly, each heuristic in \mgpt\ is implemented as a subclass of
the abstract \texttt{heuristic} class whose members are a reference
to a problem and a function that maps states to non-negative values.
Simple heuristics like the constant-zero function are straightforward,
others like \minminlrtdp\ are implemented by a class whose members
are, in addition to above, references to a hash table and to an \lrtdp\
algorithm.

\subsection{Examples}

The main parameters on a call to \mgpt\  are ``\texttt{-a <algorithm>}''
that specifies  the algorithm to use, ``\texttt{-h <heuristic>}'' 
that specifies  the heuristic function, and ``\texttt{-e <epsilon>}'' that specifies
the threshold $\epsilon$ for the consistency check. A typical call looks like:
\begin{verbatim}
   mGPT -a lrtdp -h h-m-1 -e .001 <domain> <problem>
\end{verbatim}
which instructs \mgpt\ to use the \lrtdp\ algorithm with the \atomforwn{1}\  
heuristic and $\epsilon=0.001$ over the domain and problem files specified.

The \atomforwn{1}\  heuristic is admissible but very weak. 
The following example shows how to compute the \minminlrtdp\ heuristic 
using \atomforwn{1}\  as the base heuristic:
\begin{verbatim}
   mGPT -a lrtdp -h "h-m-1|min-min-lrtdp" -e .001 <domain> <problem>
\end{verbatim}
The pipe symbol is used to instruct the planner how heuristics are to be
computed using other heuristics.

Another possibility is to use \mgpt\ as a reactive planner in which
decisions are taken on-line with respect to a heuristic function that
is improved over time. For example,
\begin{verbatim}
   mGPT -a asp -h ff <domain> <problem>
\end{verbatim}
uses the \asp\ algorithm with the \ff\ heuristic, while
\begin{verbatim}
   mGPT -a asp -h "zero|min-min-ida*" <domain> <problem>
\end{verbatim}
uses the \asp\ algorithm with the \minminida\  heuristic
computed from the constant-zero heuristic.
Other combinations of algorithms and heuristics are 
possible. \mgpt\  also accepts parameters to control 
initial hash size, a weight on the heuristic function, 
values for dead-end states,  verbosity level, lookahead settings
for \asp, etc.

\section{The Competition}

The competition suite consisted of 7 probabilistic
domains named blocksworld, exploding-blocksworld, 
boxworld, fileworld, tireworld, towers-of-hanoise, 
and zeno.
Blocksworld and exploding-blocksworld are variations
of the standard blocksworld domain for classical
planning. Boxworld is a logistics-like transportation
domain. Fileworld is a file/folder domain where
the uncertainty is only present at the initial situation
where the destination of each file is set.
Tireworld and towers-of-hanoise are variations of
the classical tireworld domain and  towers-of-hanoi.
Zeno is a traveling domain with a fuel resource.

Some of the domains come in two variations: a goal-oriented
version where the goal is to be achieved with certainty
while minimizing expected costs, and a reward-oriented
version that involves rewards. The \mgpt\ planner handles
the first type of tasks only.

In the competition we used the \lrtdp\ algorithm with the
\atombackn{1} heuristic, a parameter $\epsilon=0.001$, and a
weight $W=5$ for the heuristic function.
In some cases, when the \atombackn{1} heuristic was too poor,
the planner switched automatically to the \asp\ algorithm with
the \ff\ heuristic.

%The results obtained were rather poor in a number of domains
%for reasons that have little to do with the introduction of
%probabilities in planning and more with the domains and
%their encodings.
%In the following, we present the results with a discussion
%on the difficulties encountered by \mgpt.

\subsection{Results}

The competition was held through a client/server model.
Each planner was evaluated in each problem over a number
of runs under supervision of the server. The planner initiated
the session by connecting to the server and then interacted
with it by exchanging messages.
Each run consisted of actions sent by the planner whose 
effects were transmitted back from the server to the planner.
Thus, the current state of the problem was maintained both
by the planner and the server.

Table~\ref{tab:results} shows the results for \mgpt\ over the
competition problems. For each problem, 30 runs were executed.
The table shows the number of runs, the number of failed runs
(i.e. those that finished without reaching a goal state), the
number of successful runs (i.e. those that finished at goal states),
and the time and reward averages per run.\footnote{The competition
format was reward-based while our presentation here is cost-based.
It is straightforward to go from one format to the other.}
For the blocksworld, the problem \texttt{blocksworld-xx} means
a problem with \texttt{xx} blocks, for boxworld, the problem
\texttt{boxworld-cxx-byy} means a problem with \texttt{xx} cities
and \texttt{yy} boxes.

\begin{table}
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|}
\hline
\multicolumn{1}{|c|}{problem name} & runs & failed & successful & time & reward \\
\hline
\texttt{blocksworld-5}     &  30 &   0 &  30 &    43 & 494.1 \\
\texttt{blocksworld-8}     &  30 &   0 &  30 &    60 & 487.7 \\
\texttt{blocksworld-11}    &  30 &   0 &  30 &   130 & 465.7 \\
\texttt{blocksworld-15}    &  30 &   0 &  30 & 7,706 & 397.2 \\
\texttt{blocksworld-18}    & --- & --- & --- &   --- &   --- \\
\texttt{blocksworld-21}    & --- & --- & --- &   --- &   --- \\
\texttt{exploding-bw}      & --- & --- & --- &   --- &   --- \\
\texttt{boxworld-c5-b10}   &  30 &   0 &  30 & 6,370 & 183.6 \\
\texttt{boxworld-c10-b10}  & --- & --- & --- &   --- &   --- \\
\texttt{boxworld-c15-b10}  & --- & --- & --- &   --- &   --- \\
\texttt{fileworld-30-5}    &  30 &   0 &  30 & 2,220 &  57.6 \\
\texttt{towers-of-hanoise} & --- & --- & --- &   --- &   --- \\
\texttt{tireworld-g}       &  30 &  14 &  16 &    48 & 266.6 \\
\texttt{tireworld-r}       &  30 &   0 &  30 &    39 &     0 \\
\texttt{zeno}              &  30 &   0 &  30 &   162 &   500 \\
\hline
\end{tabular}
\end{center}
\caption{Results for the \mgpt\ planner over the competition problems.
The table shows problem name, number of runs, number of failed and successful
runs (see text), and time and reward averages. A dash means that \mgpt\ was
not able to solve the problem. Times are in milliseconds.}
\label{tab:results}
\end{table}

As it can be seen from the table, \mgpt\ did not solve \texttt{exploding-bw},
the larger instances of \texttt{blocksworld} and \texttt{boxworld}, and it
also failed on approximately half of the instances in \texttt{tireworld-g}.
The difficulties encountered by \mgpt\ in solving these problems
often had not so much to do with the probabilities involved, but
with the domains, and in particular, with the encodings.
The basic algorithms used by \mgpt\ try to solve the problems
by computing a value function with $\epsilon$-residuals over 
the relevant states (those reachable from the initial state
by an optimal policy).
For this, \mgpt\ computes an admissible heuristic function by
solving either the min-min relaxation, the Strips relaxation, or both.
A problem faced by this approach is that in many instances neither
of these relaxations could be solved.
Here, we give a detailed explanation of the problems
encountered by \mgpt\ over the different domains.
It is worth noting that many of these difficulties would
surface in any \strips\ planner as well, even if the
probabilities are ignored.
\begin{itemize}\denselist
\item Blocksworld and exploding blocksworld: the operator encodings have preconditions
containing universally-quan\-tified negative literals, as
the result of not using a `clear' predicate. For example,
\vspace{-.5em}
{\small\begin{verbatim}
(:action pick-up-block-from
  :parameters (?top - block ?bottom)
  :precondition (and (not (= ?top ?bottom))
                     (forall (?b - block) (not (holding ?b)))
                     (on-top-of ?top ?bottom)
                     (forall (?b - block) (not (on-top-of ?b ?top))))
  :effect (and (decrease (reward) 1)
               (probabilistic
                 0.75 (and (holding ?top) (not (on-top-of ?top ?bottom)))
                 0.25 (when (not (= ?bottom table))
                        (and (not (on-top-of ?top ?bottom))
                             (on-top-of ?top table)))))
)         
\end{verbatim}}
\vspace{-.5em}
This complex encoding is not standard in planning and makes our atom-based heuristics
almost useless. \mgpt\ could solve the instances with 5, 8, 11 and 15
blocks but not those with 18 and 21 blocks. For exploding blocksworld,
\mgpt\ was unable to solve it as the parser is incomplete and does not
parse some complex constructs.
\item Boxworld: the encoding contains a `\texttt{drive-truck}' operator 
that moves the truck to its intended destination with probability 0.8 and to
one of three ``wrong destinations''  with probability 0.2/3 each.
The encoding specifies the unintended effects by means of nested conditional
effects of the form
\vspace{-.5em}
{\small\begin{verbatim}
(:action drive-truck
  :parameters (?t - truck ?src - city ?dst - city)
  :precondition (and (truck-at-city ?t ?src) (can-drive ?src ?dst))
  :effect (and (not (truck-at-city ?t ?src))
               (probabilistic
                 0.2 (forall (?c1 - city)
                       (when (wrong-drive1 ?src ?c1)
                         (forall (?c2 - city)
                           (when (wrong-drive2 ?src ?c2)
                             (forall (?c3 - city)
                               (when (wrong-drive3 ?src ?c3)
                                 (probabilistic
                                   1/3 (truck-at-city ?t ?c1)
                                   1/3 (truck-at-city ?t ?c2)
                                   1/3 (truck-at-city ?t ?c3))))))))
                 0.8 (truck-at-city ?t ?dst)))
)
\end{verbatim}}
\vspace{-.5em}
Our \strips\ relaxation, like any planner that converts ADL-style
operators into Strips, suffers an exponential blow up in this domain:
with $10$ cities, there are more than a thousand operators for each
grounded ADL-operator.
This set included problems with $5$, $10$ and $15$ cities.
\item Fileworld: in this domain, there are $30$ files that need to
be filed into one of $5$ different folders: the exact destination
determined probabilistically.
The optimal policy for this problem, and any proper policy, must
\emph{prescribe an action for more than $5^{30}$ states}, all of them
relevant.
The consequence is a problem with millions of relevant states that need to
be stored into the hash table if the task is to compute a proper policy.
The \atombackn{1} heuristic for this problem is not informative, as
revealed by an analysis of the values stored in the pattern database,
and thus \mgpt\ switched automatically to the \asp\ algorithm
with the \ff\ heuristic.
\item Towers-of-hanoise: as in the blocksworld domain, the encoding is
complex with operators that have disjunctions and universally-quantified
negative literals in the preconditions, and complex conditional effects.
Yet the problem that prevented \mgpt\ from solving any problem in this
domain is a bug in the code that implements conditional effects which
did not surface in the other domains.
\Omit{
\mgpt\ faced an additional problem with this encoding since it evaluates
the conditions, of the conditional effects, in the same state where the
effects are executed; something that might generate different results,
even inconsistent ones, if the effects are executed in different orders.
For example, consider the following operator that moves disk \texttt{?d1}
from stick \texttt{?s1} onto stick \texttt{?s2} (the arrows are used as
references in the text and are not part of the operator):
\vspace{-.65em}
{\small\begin{verbatim}
(:action single-move-big-moved
  :parameters (?d1 - disk ?d2 - disk ?s1 - stick ?s2 - stick)
  :precondition (and (not (failed))
                     (not (= ?d1 ?d2))
                     (not (= ?s1 ?s2))
                     (moved-big)
        1--->        (forall (?x - disk) (not (on-top-of ?x ?d1)))
                     (on-stick ?d1 ?s1)
        2--->        (or (on-top-of ?d1 ?d2)
                         (forall (?x - disk) (not (on-top-of ?d1 ?x))))
                     (forall (?x - disk)
                       (not (and (on-stick ?x ?s2) (bigger ?d1 ?x)))))
  :effect (probabilistic
            0.95 (and (when (on-top-of ?d1 ?d2) (not (on-top-of ?d1 ?d2)))
                      (forall (?x - disk)
        4--->           (when (and (on-stick ?x ?s2)
                              (forall (?y - disk) (not (on-top-of ?y ?x))))
                          (on-top-of ?d1 ?x)))
                      (not (on-stick ?d1 ?s1))
        3--->         (on-stick ?d1 ?s2))
            0.05 (failed))
)
\end{verbatim}}
\vspace{-.65em}
The disk \texttt{?d2} provides a handle to the disk \emph{possibly} below \texttt{?d1}
since it could be at the bottom of the stick; hence the disjunction on the precondition
marked with the second arrow.
The operator works as expected if the effects are executed in the given order.
However, suppose that the effect \texttt{(on-stick ?d1 ?s2)} (marked with the third
arrow) is executed before the conditional effects within the \texttt{forall} effect
(marked with the fourth arrow). Then, when $\texttt{?x} = \texttt{?d1}$ the conditional
effect triggers since the condition \texttt{(on-stick ?d1 ?s2)} is true and no
disk is on top of \texttt{?d1} (by the precondition marked with the first arrow),
and hence the effect \texttt{(on-top-of ?d1 ?d1)} is executed resulting in an 
inconsistent state. Similar situations appear in other operators for this domain.}
\item Tireworld: there are two versions: a goal-based version
called \texttt{tireworld-g} and a reward-based version called \texttt{tireworld-r}.
The domain contains multiple dead ends at locations where the car gets a
flat tire and no spare tire is available. Some of the dead ends are unavoidable;
i.e. there is no proper policy for this problem.
All trials for the reward-based version end successfully since there is no
requirement to reach a goal position, rather the objective is to
maximize the accumulated reward.
\mgpt\ treated both versions as goal-based problems as it does not deal
directly with reward-based problems.
\end{itemize}

%\subsection{Discussion}
%\mgpt's first step is to build a deterministic relaxation that is solved in
%order to obtain a lower bound for the original problem. Many of the deterministic
%relaxations produced could not be solved at all or produced very poor values.
%We believe that the deterministic versions of the problems and encodings considered
%are likely to cause difficulties for classical planners as well, for the same
%reasons that caused difficulties to \mgpt. In the future, we expect to see
%simpler domains whose deterministic versions are solvable by classical planners
%yet its stochastic dynamics pose a challenge to probabilistic planners.


\section{Conclusions}

The \mgpt\ planner entered into the probabilistic planning competition 
combines heuristic-search algorithms with methods for obtaining lower
bounds from deterministic relaxations.
The results obtained at the competition were mixed with some of the
difficulties having to do with the selection of domains and encodings
which do not match the capabilities of \mgpt: \mgpt\ tries to
compute proper solutions using heuristics derived from the Strips
relaxations.
As we have described, some of the domains could not be solved
due to the number of relevant states, and others due to the 
complexity of the \strips\ relaxations themselves.

For the definition of good benchmarks for \mdp\ solvers, it is
crucial to define what constitutes a solution and what is the
bottom line for assessing performance.
In classical planning, for example, the solutions are plans and 
the bottom line is given by blind-search algorithms; progress in
the field can then be measured by the distance to this bottom line.
In the probabilistic setting, this is more difficult as it is not
always clear what it means to solve a problem.
This, however, needs to be defined in some way, otherwise performance
comparisons are not meaningful.
Indeed, in the classical setting, one no longer compares
optimal with non-optimal planners since both types of planners
are very different: one provides guarantees that apply to all solutions,
while the other provides guarantees that apply to one solution only.
In the probabilistic setting this is even more subtle
as there are different types of guarantees.
For example, if we restrict ourselves to the class of MDPs 
that constitute the simplest generalization of the  classical
setting --- the task of reaching the goal with certainty
while minimizing the expected number of \emph{steps} from a given
initial state $s_0$ ---  there are methods that yield solutions (policies) 
that ensure that the goal will be reached with certainty in a finite number
of steps (not necessarily optimal), and methods with no such guarantees.
Both types of methods are necessary in practice, yet it is crucial to make
a distinction among them and to identify useful benchmarks in each class.
For methods that yield optimal policies, or at least policies
with finite expected costs, standard dynamic programming methods 
like value iteration provide a useful bottom-line reference for assessing
performance.  In any case, we believe that useful benchmarks need to be
defined taking into account the types of tasks that the various algorithms
aim to solve, and the types of guarantees, if any, that they provide in
their solutions.

\medskip

\gpt\ and \mgpt\ are available for download at \url{http://www.ldc.usb.ve/~bonet}.


\subsection*{Acknowledgements}
\mgpt\ was built upon a parser developed by John Asmuth from
Rutgers University and H{\aa}kan Younes from Carnegie Mellon University.
We also thank David E. Smith for comments that helped us to
improve this note.

\bibliographystyle{theapa}
%\bibliography{../../../control}



\begin{thebibliography}{}

\bibitem[\protect\BCAY{Barto, Bradtke,\ \BBA\ Singh}{Barto
  et~al.}{1995}]{barto:rtdp}
Barto, A., Bradtke, S., \BBA\ Singh, S. \BBOP1995\BBCP.
\newblock \BBOQ Learning to act using real-time dynamic programming\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 72}, 81--138.

\bibitem[\protect\BCAY{Bertsekas}{Bertsekas}{1995}]{bertsekas:dp}
Bertsekas, D. \BBOP1995\BBCP.
\newblock {\Bem Dynamic Programming and Optimal Control, (2 Vols)}.
\newblock Athena Scientific.

\bibitem[\protect\BCAY{Blum\ \BBA\ Furst}{Blum\ \BBA\
  Furst}{1997}]{blum:graphplan-aij}
Blum, A.\BBACOMMA\  \BBA\ Furst, M. \BBOP1997\BBCP.
\newblock \BBOQ Fast planning through planning graph analysis\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 90}, 281--300.

\bibitem[\protect\BCAY{Bonet\ \BBA\ Geffner}{Bonet\ \BBA\
  Geffner}{2000}]{bonet:aips2000}
Bonet, B.\BBACOMMA\  \BBA\ Geffner, H. \BBOP2000\BBCP.
\newblock \BBOQ Planning with incomplete information as heuristic search in
  belief space\BBCQ\
\newblock In Chien, S., Kambhampati, S., \BBA\ Knoblock, C.\BEDS, {\Bem Proc.
  6th International Conf. on Artificial Intelligence Planning and Scheduling},
  \BPGS\ 52--61, Breckenridge, CO. AAAI Press.

\bibitem[\protect\BCAY{Bonet\ \BBA\ Geffner}{Bonet\ \BBA\
  Geffner}{2001}]{bonet:hsp-aij}
Bonet, B.\BBACOMMA\  \BBA\ Geffner, H. \BBOP2001\BBCP.
\newblock \BBOQ Planning as heuristic search\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 129\/}(1--2), 5--33.

\bibitem[\protect\BCAY{Bonet\ \BBA\ Geffner}{Bonet\ \BBA\
  Geffner}{2003a}]{bonet:hdp}
Bonet, B.\BBACOMMA\  \BBA\ Geffner, H. \BBOP2003a\BBCP.
\newblock \BBOQ Faster heuristic search algorithms for planning with
  uncertainty and full feedback\BBCQ\
\newblock In Gottlob, G.\BED, {\Bem Proc. 18th International Joint Conf. on
  Artificial Intelligence}, \BPGS\ 1233--1238, Acapulco, Mexico. Morgan
  Kaufmann.

\bibitem[\protect\BCAY{Bonet\ \BBA\ Geffner}{Bonet\ \BBA\
  Geffner}{2003b}]{bonet:lrtdp}
Bonet, B.\BBACOMMA\  \BBA\ Geffner, H. \BBOP2003b\BBCP.
\newblock \BBOQ Labeled {RTDP}: {I}mproving the convergence of real-time
  dynamic programming\BBCQ\
\newblock In Giunchiglia, E., Muscettola, N., \BBA\ Nau, D.\BEDS, {\Bem Proc.
  13th International Conf. on Automated Planning and Scheduling}, \BPGS\
  12--21, Trento, Italy. AAAI Press.

\bibitem[\protect\BCAY{Bonet, Loerincs,\ \BBA\ Geffner}{Bonet
  et~al.}{1997}]{bonet:asp}
Bonet, B., Loerincs, G., \BBA\ Geffner, H. \BBOP1997\BBCP.
\newblock \BBOQ A robust and fast action selection mechanism for planning\BBCQ\
\newblock In Kuipers, B.\BBACOMMA\  \BBA\ Webber, B.\BEDS, {\Bem Proc. 14th
  National Conf. on Artificial Intelligence}, \BPGS\ 714--719, Providence, RI.
  AAAI Press / MIT Press.

\bibitem[\protect\BCAY{Cormen, Leiserson,\ \BBA\ Rivest}{Cormen
  et~al.}{1990}]{cormen:algorithms}
Cormen, T., Leiserson, C., \BBA\ Rivest, R. \BBOP1990\BBCP.
\newblock {\Bem Introduction to Algorithms}.
\newblock MIT Press.

\bibitem[\protect\BCAY{Edelkamp}{Edelkamp}{2001}]{edelkamp:pdbs}
Edelkamp, S. \BBOP2001\BBCP.
\newblock \BBOQ Planning with pattern databases\BBCQ\
\newblock In Cesta, A.\BED, {\Bem Proc. 6th European Conf. on Planning}, \BPGS\
  13--24, Toledo, Spain. Springer: {L}{N}{C}{S}.

\bibitem[\protect\BCAY{Gazen\ \BBA\ Knoblock}{Gazen\ \BBA\
  Knoblock}{1997}]{gazen:adl}
Gazen, B.\BBACOMMA\  \BBA\ Knoblock, C. \BBOP1997\BBCP.
\newblock \BBOQ Combining the expressiveness of {U}{C}{P}{O}{P} with the
  efficiency of {G}raphplan\BBCQ\
\newblock In Steel, S.\BBACOMMA\  \BBA\ Alami, R.\BEDS, {\Bem Proc. 4th
  European Conf. on Planning}, \BPGS\ 221--233, Toulouse, France. Springer:
  {L}{N}{C}{S}.

\bibitem[\protect\BCAY{Haslum, Bonet,\ \BBA\ Geffner}{Haslum
  et~al.}{2005}]{haslum:newh}
Haslum, P., Bonet, B., \BBA\ Geffner, H. \BBOP2005\BBCP.
\newblock \BBOQ New admissible heuristics for domain-independent planning\BBCQ\
\newblock In Veloso, M.\BBACOMMA\  \BBA\ Kambhampati, S.\BEDS, {\Bem Proc. 20
  National Conf. on Artificial Intelligence}, \BPGS\ 1163--1168, Pittsburgh,
  PA. AAAI Press / MIT Press.

\bibitem[\protect\BCAY{Haslum\ \BBA\ Geffner}{Haslum\ \BBA\
  Geffner}{2000}]{haslum:heuristic}
Haslum, P.\BBACOMMA\  \BBA\ Geffner, H. \BBOP2000\BBCP.
\newblock \BBOQ Admissible heuristic for optimal planning\BBCQ\
\newblock In Chien, S., Kambhampati, S., \BBA\ Knoblock, C.\BEDS, {\Bem Proc.
  6th International Conf. on Artificial Intelligence Planning and Scheduling},
  \BPGS\ 140--149, Breckenridge, CO. AAAI Press.

\bibitem[\protect\BCAY{Hoffmann\ \BBA\ Nebel}{Hoffmann\ \BBA\
  Nebel}{2001}]{hoffmann:ff}
Hoffmann, J.\BBACOMMA\  \BBA\ Nebel, B. \BBOP2001\BBCP.
\newblock \BBOQ The {FF} planning system: {F}ast plan generation through
  heuristic search\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 14},
  253--302.

\bibitem[\protect\BCAY{Korf}{Korf}{1990}]{korf:lrta}
Korf, R. \BBOP1990\BBCP.
\newblock \BBOQ Real-time heuristic search\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 42\/}(2--3), 189--211.

\bibitem[\protect\BCAY{Nguyen\ \BBA\ Kambhampati}{Nguyen\ \BBA\
  Kambhampati}{2000}]{nguyen:heuristics}
Nguyen, X.\BBACOMMA\  \BBA\ Kambhampati, S. \BBOP2000\BBCP.
\newblock \BBOQ Extracting effective and admissible state-space heuristics from
  the planning graph\BBCQ\
\newblock In Kautz, H.\BBACOMMA\  \BBA\ Porter, B.\BEDS, {\Bem Proc. 17th
  National Conf. on Artificial Intelligence}, \BPGS\ 798--805, Austin, TX. AAAI
  Press / MIT Press.

\bibitem[\protect\BCAY{Pearl}{Pearl}{1983}]{pearl:heuristics}
Pearl, J. \BBOP1983\BBCP.
\newblock {\Bem Heuristics}.
\newblock Morgan Kaufmann.

\bibitem[\protect\BCAY{Tarjan}{Tarjan}{1972}]{tarjan:scc}
Tarjan, R.~E. \BBOP1972\BBCP.
\newblock \BBOQ Depth first search and linear graph algorithms\BBCQ\
\newblock {\Bem SIAM Journal on Computing}, {\Bem 1\/}(2), 146--160.

\end{thebibliography}


\end{document}

