\documentclass[11pt,twoside]{article}

\usepackage{jair}
\usepackage{theapa}
\usepackage{epsfig}
\usepackage{amsfonts}
\usepackage{ifthen}

\jairheading{9}{1998}{1--36}{1/98}{8/98}
\ShortHeadings{Complexity of Probabilistic Planning}
{Littman, Goldsmith \& Mundhenk}
\firstpageno{1}

\typeout{Set switch "nofigures" false when LaTeXing with figures and bibliography}
\newboolean{nofigures}
% comment out the following line to set  nofigures  false
% \setboolean{nofigures}{true}

\newcommand{\stack}[2]{\begin{array}{c}#1\\#2\end{array}}
\newcommand{\help}[1]{\begin{quote}\centerline{------}{\bf
#1}\\\centerline{------}\end{quote}}

\newcommand{\Mb}{\mathbb{M}}

\newcommand{\cA}{{\cal A}}
\newcommand{\cM}{{\cal G}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cQ}{{\cal Q}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cC}{{\cal C}}
% \newcommand{\mdp}{{\sc mdp}}
% \newcommand{\mdps}{{\sc mdp}s}
% \newcommand{\pomdp}{{\sc pomdp}}
% \newcommand{\pomdps}{{\sc pomdp}s}
\newcommand{\classfont}{\rm }
\newcommand{\GapL}{{\classfont GapL}}
\newcommand{\GapP}{{\classfont GapP}}
\newcommand{\PL}{{\classfont PL}}
\newcommand{\NLOGSPACE}{{\classfont NL}}
\newcommand{\LOGSPACE}{{\classfont L}}
\newcommand{\PH}{{\classfont PH}}
\newcommand{\sharpL}{{\classfont \#L}}
\newcommand{\sharpP}{{\classfont \#P}}
\newcommand{\sharpPSPACE}{{\classfont \#PSPACE}}
\newcommand{\PTIME}{{\classfont P}}
\newcommand{\NP}{{\classfont NP}}
% \newcommand{\NC}{{\classfont NC}}
\newcommand{\coNP}{\mbox{co-}\NP}
\newcommand{\PP}{{\classfont PP}}
\newcommand{\PSPACE}{{\classfont PSPACE}}
\newcommand{\EXPTIME}{{\classfont EXP}}
\newcommand{\EXPSPACE}{{\classfont EXPSPACE}}
\newcommand{\NPPP}{\NP\ora{\PP}}
\newcommand{\coNPPP}{\coNP\ora{\PP}}
\newcommand{\langfont}{\sc}       % Use inside \mbox-es
\newcommand{\MAJSAT}{\mbox{\langfont Majsat}}
\newcommand{\SAT}{\mbox{\langfont Sat}}
\newcommand{\EMAJSAT}{\mbox{\langfont E-Majsat}}
% \newcommand{\ora}[1]{$^{{#1}}$}
\newcommand{\ora}[1]{^{{#1}}}
\newcommand{\argmax}{\mathop{\rm argmax}}
\newcommand{\as}{{\sf assign}}
\newcommand{\st}{{\sf start}}
\newcommand{\ch}{{\sf check}}
\newcommand{\ed}{{\sf end}}

\newcommand{\tablecaption}{\caption}
\newcommand{\namecite}[1]{\citeauthor{#1}~\citeyear{#1}}
\newcommand{\namecitenoparens}[1]{\citeauthor{#1},~\citeyearnoparens{#1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newenvironment{proof}{\noindent{\bf Proof: }}{\hspace*{\fill}
\rule{2mm}{2mm} \vspace{0.15in}}
\newenvironment{sketch}{\noindent{\bf Proof sketch: }}{\hspace*{\fill}
\rule{2mm}{2mm} \vspace{0.15in}}

\begin{document}
\title{The Computational Complexity of Probabilistic Planning}

\author{\name Michael L. Littman \email mlittman@cs.duke.edu \\
	\addr Department of Computer Science, Duke University \\
	Durham, NC 27708-0129 USA
	\AND
       \name Judy Goldsmith \email  goldsmit@cs.engr.uky.edu \\
       \addr Department of Computer Science, University of Kentucky \\
       Lexington, KY 40506-0046 USA
       \AND
       \name Martin Mundhenk \email mundhenk@ti.uni-trier.de \\
       \addr FB4 - Theoretische Informatik, Universit\"{a}t Trier \\
	D-54286 Trier, GERMANY}

\maketitle

\begin{abstract}
We examine the computational complexity of testing and finding small
plans in probabilistic planning domains with both flat and
propositional representations.  The complexity of plan evaluation and
existence varies with the plan type sought; we examine totally ordered
plans, acyclic plans, and looping plans, and partially ordered plans
under three natural definitions of plan value.  We show that problems
of interest are complete for a variety of complexity classes: $\PL$,
$\PTIME$, $\NP$, $\coNP$, $\PP$, $\NPPP$, $\coNPPP$, and $\PSPACE$.
In the process of proving that certain planning problems are complete
for $\NPPP$, we introduce a new basic $\NPPP$-complete problem,
\EMAJSAT, which generalizes the standard Boolean satisfiability
problem to computations involving probabilistic quantities; our
results suggest that the development of good heuristics for \EMAJSAT\
could be important for the creation of efficient algorithms for a wide
variety of problems.
\end{abstract}

\bibliographystyle{theapa}

\section{Introduction}

Recent work in artificial-intelligence planning has addressed the
problem of finding effective plans in domains in which operators have
probabilistic
effects~\cite{drummond90,mansell93,draper94,koenig94a,goldman94,kushmerick95,Boutilier95,dearden97,kaelbling98,boutilier98}.
Here, an ``effective'' or ``successful'' plan is one that reaches a
goal state with sufficient probability.  In {\em probabilistic
propositional planning\/}, operators are specified in a Bayes network
or an extended STRIPS-like notation, and the planner seeks a recipe
for choosing operators to achieve a goal configuration with some
user-specified probability.  This problem is closely related to that
of solving a Markov decision process~\cite{puterman94} when it is
expressed in a compact representation.

In previous work~\cite{goldsmith96,littman97b}, we examined the
complexity of determining whether an effective plan exists for
completely observable domains; the problem is $\EXPTIME$-complete in
its general form and $\PSPACE$-complete when limited to
polynomial-depth plans. (A polynomial-depth, or polynomial-horizon,
plan is one that takes at most a polynomial number of actions before
terminating.)  For these results, plans are permitted to be
arbitrarily large objects---there is no restriction that a valid plan
need have any sort of compact (polynomial-size) representation.

Because they place no restrictions on the size of valid plans, these
earlier results are not directly applicable to the problem of {\em
finding\/} valid plans.  It is possible, for example, that for a given
planning domain, the only valid plans require exponential space (and
exponential time) to write down.  Knowing whether or not such plans
exist is simply not very important because they are intractable to
express.

In the present paper, we consider the complexity of a more practical
and realistic problem---that of determining whether or not a plan
exists in a given restricted form and of a given restricted size.  The
plans we consider take several possible forms that have been used in
previous planning work: totally ordered plans, partially ordered
plans, (totally ordered) conditional plans, and (totally order)
looping plans.  In all cases, we limit our attention to plans that can
be expressed in size bounded by a polynomial in the size of the
specification of the problem.  This way, once we determine that a plan
exists, we can use this information to try to write it down in a
reasonable amount of time and space.

In the deterministic planning literature, several authors have
addressed the computational complexity of determining whether a valid
plan exists, of determining whether a plan exists of a given cost, and
of finding the valid plans themselves under a variety of
assumptions~\cite{chapman87,bylander94,erol95,backstrom95,backstrom95b}.
These results provide lower bounds (hardness results) for analogous
probabilistic planning problems since deterministic planning is a
special case.  In deterministic planning, optimal plans can be
represented by a simple sequence of operators (a totally ordered
plan).  In probabilistic planning, a good conditional plan will often
perform better than any totally ordered (unconditional) plan;
therefore, we need to consider the complexity of the planning process
for a richer set of plan structures.

For ease of discussion, we only explicitly describe the case of
planning in completely observable domains.  This means that the state
of the world is known at all times during plan execution, in spite of
the uncertainty of state transitions.  We know that the state of the
system is sufficient information for choosing actions
optimally~\cite{puterman94}, however, representing such a universal
plan is often impractical in propositional domains in which the size
of the state space is exponential in the size of the domain
representation.  For this reason, we consider other types of plan
structures based on simple finite-state machines.
% Because we do not assume that actions are chosen based on complete
% information on the state of the system,
Because the type of plans we consider do not necessarily use the full
state of the system to make every decision, our results carry over to
partially observable domains, although we do not explore this fact in
detail in the present work.
% zzz

The computational problems we look at are complete for a variety of
complexity classes ranging from $\PL$ (probabilistic logspace) to
$\PSPACE$.  Two results are deserving of special mention because they
concern problems closely related to ones being actively addressed by
artificial-intelligence researchers; first, the problem of evaluating
a totally ordered plan in a compactly represented planning domain is
$\PP$-complete.\footnote{The class $\PP$ is closely related to the
somewhat more familiar $\sharpP$; \namecite{toda91} showed that
$\PTIME\ora{\sharpP}=\PTIME\ora{\PP}$.
% {from} which it follows that $\NP\ora{\sharpP}=\NPPP$.  
Roughly speaking, this means that $\sharpP$ and $\PP$ are equally
powerful when used as oracles.  The counting class $\sharpP$ has
already been recognized by the artificial-intelligence community as an
important complexity class in computations involving probabilistic
quantities, such as belief-network inference~\cite{roth96}.}
% Of course, probabilistic computations are central to the area of
% uncertainty in artificial intelligence.
A compactly represented planning domain is one that is described by a
two-stage temporal Bayes network~\cite{boutilier98} or similar
notation.

Second, the problem of determining whether a valid totally ordered
plan exists for a compactly represented planning domain is
$\NPPP$-complete.  Whereas the class $\NP$ can be thought of as the
set of problems solvable by guessing the answer and checking it in
polynomial time, the class $\NPPP$ can be thought of as the set of
problems solvable by guessing the answer and checking it using a
probabilistic polynomial-time ($\PP$) computation.  It is likely that
$\NPPP$ characterizes many problems of interest in the area of
uncertainty in artificial intelligence; this paper and earlier
work~\cite{goldsmith96,mundhenk97,mundhenk97b} give initial evidence
of this.


\subsection{Planning-Domain Representations}

A probabilistic planning domain $M=\langle\cS, s_0, \cA, t,
\cM\rangle$ is characterized by a finite set of states $\cS$, an
initial state $s_0\in\cS$, a finite set of operators or actions $\cA$,
and a set of goal states $\cM\subseteq\cS$.  The application of an
action $a$ in a state $s$ results in a probabilistic transition to a
new state $s'$ according to the probability transition function $t$,
where $t(s,a,s')$ is the probability that state $s'$ is reached from
state $s$ when action $a$ is taken.  The objective is to choose
actions, one after another, to move from the initial state $s_0$ to
one of the goal states with probability above some threshold
$\theta$.\footnote{It is also possible to formulate the objective as
one of maximizing expected total discounted reward~\cite{Boutilier95},
but the two formulations are essentially polynomially
equivalent~\cite{condon92}.  The only difficulty is that compactly
represented domains may require discount factors exponentially close
to one for this equivalence to hold.  This is discussed further in
Section~\ref{s:applications}.} The state of the system is known at all
times (fully observable) and so can be used to choose the action to
apply.

We are concerned with two main representations for planning domains:
{\em flat\/} representations, which enumerate states explicitly, and
{\em propositional\/} representations (sometimes called compact,
structured, or factored representations), which view states as
assignments to a set of Boolean state variables or propositions.
Propositional representations can represent many domains exponentially
more compactly than can flat representations.

In the flat representation, the transition function $t$ is represented
by a collection of $|\cS|\times|\cS|$ matrices,\footnote{We assume
that the number of bits used to represent the individual probability
values isn't too large.} one for each action.  In the propositional
representation, this type of $|\cS|\times|\cS|$ matrix would be huge,
so the transition function must be expressed another way.  In the
probabilistic planning literature, two popular representations for
propositional planning domains are probabilistic state-space operators
(PSOs)~\cite{kushmerick95} and two-stage temporal Bayes networks
(2TBNs)~\cite{Boutilier95}.  Although these representations differ in
the type of planning domains they can express
naturally~\cite{boutilier98}, they are computationally equivalent; a
planning domain expressed in one representation can be converted in
polynomial time to an equivalent planning domain expressed in the
other with at most a polynomial increase in representation
size~\cite{littman97b}.

In this work, we focus on a propositional representation called the
sequential-effects-tree representation (ST)~\cite{littman97b}, which
is a syntactic variant of 2TBNs with conditional probability tables
represented as trees~\cite{Boutilier95,boutilier98}.  This
representation is equivalent to 2TBNs and PSOs and simplifies the
presentation of our results.  In ST, the effect of each action on each
proposition is represented as a separate decision tree.  For a given
action $a$, the set of decision trees for the different propositions
is ordered, so the decision tree for one proposition can refer to both
the new and old values of previous propositions; this allows ST to
represent any probability distribution.
% ; while this does not
% increase the expressibility over a representation where all decision
% trees are interpreted in parallel, it does simplify the proofs
% considerably.
The leaves of a decision tree describe how the associated proposition
changes as a function of the state and action, perhaps
probabilistically.  Section~\ref{s:example} gives a simple example of
this representation.

As in other propositional representations, the states in the set of
goal states $\cM$ are not explicitly enumerated in ST.  Instead, we
define a {\em goal set\/}, which is a set of propositions such that
any state in which all the goal-set propositions are true is
considered a goal state.  The set of actions $\cA$ is explicitly
enumerated in ST, just as it is in the flat representation.

The ST representation of a planning domain $M=\langle\cS, s_0, \cA, t,
\cM\rangle$ can be defined more formally as $\mathbb{M} = \langle
\mathbb{P}, \mathbb{I}, \cA, \mathbb{T}, \mathbb{G}\rangle$ (we use
blackboard-bold font to stand for an ST representation on a domain).
Here, $\mathbb{P}$ is a finite set of distinct propositions.  The set
of states $\cS$ is the power set of $\mathbb{P}$; the propositions in
$s\in\cS$ are said to be ``true'' in $s$.  The set $\mathbb{I}
\subseteq \mathbb{P}$ is the initial state.  The set $\mathbb{G}$ is
the goal set, so the set of goal states $\cM$ is the set of states $s$
such that $\mathbb{G} \subseteq s$.

The transition function $t$ is represented by a function $\mathbb{T}$,
which maps each action in $\cA$ to an ordered sequence of
$|\mathbb{P}|$ binary decision trees.  Each of these decision trees
has a distinct label proposition, decision propositions at the nodes
(optionally labeled with the suffix ``{\bf :new}''), and probabilities
at the leaves.  The $i$th decision tree $\mathbb{T}(a)_i$ for action
$a$ defines the transition probabilities $t(s,a,s')$ as follows.  For
the $i$th decision tree, let {\bf p}$_i$ be its label proposition.
Define $\rho_i$ to be the value of the leaf node found by traversing
decision tree $\mathbb{T}(a)_i$, taking the left branch if the
decision proposition is in $s$ (or $s'$ if the decision proposition
has the ``{\bf :new}'' suffix) and the right branch otherwise.
Finally, we let
\begin{equation}
t(s,a,s') = \prod_i \left\{ \begin{array}{ll}
 \rho_i, & \mbox{if {\bf p}$_i \in s'$,}\\
 1-\rho_i, & \mbox{otherwise.} 
 \end{array} \right.
\label{e:tprob}
\end{equation}
This definition of $t$ constitutes a well-defined probability
distribution over $s'$ for each $a$ and $s$.

To insure the validity of the representation, we only allow ``{\bf
p:new}'' to appear as a decision proposition in $\mathbb{T}(a)_i$ if
{\bf p} is the label proposition for some decision tree
$\mathbb{T}(a)_j$ for $j < i$.  For this reason, the order of the
decision trees in $\mathbb{T}(a)$ is significant.  To put this another
way, a proposition only has a new value after this new value has been
defined by some decision tree.

The complexity results we derive for ST apply also to PSOs, 2TBNs, and
all other computationally equivalent representations.  They also hold
for the ``succinct representation,'' a propositional representation
popular in the complexity-theory literature, which captures the set of
% zzz references?
transition matrices as a function, most commonly represented by a
Boolean circuit that computes that function.  ST can straightforwardly
be represented as a Boolean circuit, and, in the proof of
Theorem~\ref{th:PL-complete2}, we show how to represent particular
Boolean circuits in ST.  Thus, although we have not shown that the
succinct representation is formally equivalent to ST, the two
representations are closely related; the proofs we give for ST need to
be changed only slightly to work for the succinct
representation~\cite{goldsmith97,goldsmith97b,mundhenk97b}.  Our
results require that we restrict the succinct representation to
generate transition probabilities with at most a polynomial number of
bits; the results may be different for other circuit-based
representations that can represent probabilities with an exponential
number of bits~\cite{mundhenk97}.


\subsection{Example Domain}
\label{s:example}

To help make these domain-representation ideas more concrete, we
present the following simple probabilistic planning domain based on
the problem of building a sand castle at the beach.  There are a total
of four states in the domain, described by combinations of two Boolean
propositions, {\bf moat} and {\bf castle} (propositions appear in
boldface).  The proposition {\bf moat} signifies that a moat has been
dug in the sand, and the proposition {\bf castle} signifies that the
castle has been built.  In the initial state, both {\bf moat} and {\bf
castle} are false, and the goal set is $\{ {\bf castle} \}$.

There are two actions: {\sf dig-moat} and {\sf erect-castle} (actions
appear in sans serif).  Figure~\ref{f:st} illustrates these actions in
ST.  Executing {\sf dig-moat} when {\bf moat} is false causes {\bf
moat} to become true with probability $1/2$; if {\bf moat} is already
true, {\sf dig-moat} leaves it unchanged.  The {\bf castle}
proposition in not affected.  The {\sf dig-moat} action is depicted in
the left half of Figure~\ref{f:st}.

The second action is {\sf erect-castle}, which appears in the right
half of Figure~\ref{f:st}.  The decision trees are numbered to allow
sequential dependencies between their effects to be expressed.  The
first decision tree is for {\bf castle}, which does not change value
if it is already true when {\sf erect-castle} is executed.  Otherwise,
the probability that it becomes true is dependent on whether {\bf
moat} is true; the castle is built with probability $1/2$ if {\bf
moat} is true and only probability $1/4$ if it is not.  The idea here
is that building a moat first protects the castle from being destroyed
prematurely by the ocean waves.

The second decision tree is for the proposition {\bf moat}.  Because
{\sf erect-castle} cannot make {\bf moat} become true, there is no
effect when {\bf moat} is false.  On the other hand, if the moat
exists, it may collapse as a result of trying to erect the castle.
The label {\bf castle:new} in the diagram refers to the value of the
{\bf castle} proposition {\em after\/} the first decision tree is
evaluated.  If the castle was already built when {\sf erect-castle} was
selected, the moat remains built with probability $3/4$.  If the
castle had not been built, but {\sf erect-castle} successfully builds
it, {\bf moat} remains true.  Finally, if {\sf erect-castle} fails to
make {\bf castle} true, {\bf moat} becomes false with probability
$1/2$ and everything is destroyed.

\ifthenelse{\boolean{nofigures}}
{ }
{
\begin{figure}
\centerline{\epsfig{file=block.ps,width=4.25in}}
\caption{Sequential-effects-tree (ST) representation for the
sand-castle domain} 
\label{f:st}
\end{figure}
}

Note that given an ST representation of a domain, we can perform a
number of useful operations efficiently.  First, given a state $s$ and
action $a$, we can generate a next state $s'$ with the proper
probabilities.  This is accomplished by calculating the value of the
propositions of $s'$ one at a time in the order given in the
representation of $a$, flipping coins with the probabilities given in
the leaves of the decision trees.  Second, given a state $s$, action
$a$, and state $s'$, we can compute $t(s,a,s')$, the probability that
state $s'$ is reached from state $s$ when action $a$ is taken, via Equation~\ref{e:tprob}.

\subsection{Plan Types and Representations}

We consider four classes of plans for probabilistic domains.  {\em
Totally ordered plans\/} are the most basic type, being a finite
sequence of actions that must be executed in order; this type of plan
ignores the state of the system.  {\em Acyclic plans\/} generalize
totally ordered plans to include conditional execution of actions.
{\em Partially ordered plans\/} are a different way of generalizing
totally ordered plans in which the precise sequence is left
flexible~\cite{mccallester91}.  {\em Looping plans\/} generalize
acyclic plans to the case in which plan steps can be
repeated~\cite{smith95,lin95}.  This type of plan is also referred to
as a plan graph or policy graph~\cite{kaelbling98}.

In the following sections, we prove computational complexity results
concerning each of these plan types.  The remainder of this section
provides formal definitions of the plan types, illustrated in
Figure~\ref{f:plans} with examples for the sand-castle domain.

In its most general form, a plan (or policy, controller or
transducer) is a program that outputs actions and takes as input
information about the outcome of these actions.  In this work, we
consider only a particularly restricted finite-state-controller-based
plan representation.

A {\em plan\/} $P$ for a planning domain $M=\langle\cS, s_0, \cA, t,
\cM\rangle$ can be represented by a structure $(V,v_0,E,\pi,\delta)$
consisting of a directed (multi) graph $(V,E)$ with initial node
$v_0\in V$, a labeling $\pi:V\rightarrow\cA$ of plan nodes---called
{\em plan steps\/}---to domain actions, and a labeling of edges with
state sets $\delta:E\rightarrow\mathcal{P}(\cS)$ such that for every
$v\in V$ with outgoing edges, $\bigcup_{v'\in V:(v,v')\in E}
\delta(v,v') = \cS$ and $\delta(v,v_1) \cap \delta(v,v_2) = \emptyset$
for all $v_1, v_2 \in V$, $v_1 \neq v_2$.  Some plan steps have no
outgoing edges at all---these are the {\em terminal steps\/}.  Actions
for terminal steps are not executed.  Note that the function $\delta$
can be represented in a direct manner for flat domains, but for
propositional domains, a more compact representation is needed.  We
assume that for propositional domains, edge labels are given as
conjunctions of literals.

The behavior of plan $P$ in domain $M$ is as follows.  The initial
time step is $t=0$.  At time step $t\ge 0$, the domain is in state
$s_t$ and the plan is at step $v_t$ ($s_0$ is defined by the planning
domain, $v_0$ by the plan).  Action $\pi(v_t)$ is executed, resulting
in a transition to domain state $s_{t+1}$ with probability
$t(s_t,\pi(v_t),s_{t+1})$.  Plan step $v_{t+1}$ is chosen so that
$s_{t+1} \in \delta(v_t,v_{t+1})$; the function $\delta$ tells the
plan where to ``go'' next.  At this point, the time-step index $t$ is
incremented and the process repeats.  This continues until a terminal
step is reached in the plan.

One can understand the behavior of domain $M$ under plan $P$ in
several different ways.  The possible sequences of states of $M$ can
be viewed as a tree: each node of the tree at depth $t$ is a state
reachable from the initial state at time step $t$.  Alternatively, one
can view the state of $M$ at time step $t$ under plan $P$ as a
probability distribution over $\cS$.  At time step $0$, with
probability $1$ the process is in state $s_0$.  The probability that
$M$ is in state $s'$ at time step $t+1$, $\Pr(s', t+1)$, is the sum of
the probabilities of all length $t+1$ paths from $s_0$ to $s'$, i.e.,
\[
\sum_{s_0,s_1,s_2,\ldots,s_t,s_{t+1}=s'} \;\;
               \prod_{j=1}^{t} t(s_j, a_j,s_{j+1}),
\]
where $a_j$ is the action selected by plan $P$ at time $j$ given the
observed sequence of state transitions $s_0,\ldots,s_j$.  This view is
useful in some of the later proofs.

Next, we formalize the probability that domain $M$ reaches a goal
state under plan $P$.  We need to introduce several notions.  A
``legal'' sequence of states and steps applied is called a {\em
trajectory\/}, i.e., for $M$ and $P$ this is a sequence
$\alpha=\langle (s_i,v_i) \rangle_{i=0}^{k}$ of pairs with
\begin{itemize}
\item
$t(s_i,\pi(v_i),s_{i+1}) > 0$ for $0\le i\le k-1$,
\item
$s_{i+1} \in \delta(v_i,v_{i+1})$ for $0\le i\le k-1$, and
\item
$v_0,\ldots,v_{k-1}$ are not terminal steps.
\end{itemize}

A {\em goal trajectory\/} is a trajectory that ends in a goal state of
$M$, $s_k\in\cM$.  Note that each goal trajectory is finite.  Thus, we
can calculate the probability of a goal trajectory $\alpha=\langle
(s_i,v_i) \rangle_{i=0}^{k}$ as $\Pr(\alpha)=\prod_{i=0}^{k-1}
t(s_i,\pi(v_i),s_{i+1})$, given that $s_k\in \cM$.  The probability
that $M$ reaches a goal state under plan $P$ is the sum of the
probabilities of goal trajectories for $M$,
$$
\Pr(M \mbox{ reaches a goal state under } P):= 
   \sum_{\alpha \mbox{ \scriptsize goal trajectory}}   \Pr(\alpha);
$$
we call this the {\em value\/} of the plan.

We characterize a plan $P=(V,v_0,E,\pi,\delta)$ on the basis of the
size and structure of its underlying graph $(V,E)$.  If the graph
$(V,E)$ contains no cycles, we call it an {\em acyclic plan\/},
otherwise it is a {\em looping plan\/}.  It follows that an acyclic
plan has a terminal step, and that a terminal step will be reached
after no more than $|V|$ actions are taken; such plans can only be
used for finite-horizon control.  A {\em totally ordered plan\/}
(sometimes called a ``linear plan'' or a ``straight line'' plan) is an
acyclic plan with no more than one outgoing edge for each node in $V$.
Such a plan is a simple path.

In this work, we also consider {\em partially ordered plans\/}
(sometimes called ``nonlinear'' plans) that express an entire family
of totally ordered plans.  In this representation, the steps of the
plan are given as a partial order (specified, for example, as a
directed acyclic graph).  This partial order represents a {\em set\/}
of totally ordered plans: all totally ordered sequences of plan steps
consistent with the partial order that consist of {\em all\/} steps of
the partially ordered plan.  Each of these totally ordered plans has a
value, and these values need not all be the same.  As such, we have a
choice in defining the value for a partially ordered plan.  In this
work, we consider the optimistic, pessimistic, and average
interpretations.  Let $\Omega(P)$ be the set of totally ordered
sequences consistent with partial order plan $P$.  Under the {\em
optimistic\/} interpretation,
$$
\mbox{The value of $P$} := \max_{p \in \Omega(P)}
     \Pr(M \mbox{ reaches a goal state under } p).
$$
Under the {\em pessimistic\/} interpretation,
$$
\mbox{The value of $P$} := \min_{p \in \Omega(P)}
     \Pr(M \mbox{ reaches a goal state under } p).
$$
Under the {\em average\/} interpretation,
$$
\mbox{The value of $P$} := \frac{1}{|\Omega(P)|} \sum_{p \in \Omega(P)}
     \Pr(M \mbox{ reaches a goal state under } p).
$$

To illustrate these notions, Figure~\ref{f:plans} gives plans of each
type for the sand-castle domain described earlier.  Initial nodes are
marked an incoming arrow, and terminal steps are represented as filled
circles.  The 3-step totally ordered plan in Figure~\ref{f:plans}(a)
successfully builds a sand castle with probability $0.4375$.  An
acyclic plan is given in Figure~\ref{f:plans}(b), which succeeds with
probability $0.46875$ and executes {\sf dig-moat} an average of $1.75$
times.  Note that it succeeds more often and with fewer actions on
average than the totally ordered plan in Figure~\ref{f:plans}(a).

Figure~\ref{f:plans}(c) illustrates a partially ordered plan for the
sand-castle domain.  While this plan bears a superficial resemblance
to the acyclic plan in Figure~\ref{f:plans}(b), it has a different
interpretation.  In particular, the plan in Figure~\ref{f:plans}(c)
represents a set of totally ordered plans with five (non-terminal)
plan steps (3 {\sf dig-moat} steps and 2 {\sf erect-castle} steps).
In contrast to the solid arrows in Figure~\ref{f:plans}(b), which
indicate flow of control, the dashed arrows in Figure~\ref{f:plans}(c)
represent ordering constraints: each {\sf erect-castle} step must be
preceded by at least two {\sf dig-moat} steps, for example.

Although there are $\left(\begin{array}{c}5\\2\end{array}\right) = 10$
distinct ways of arranging the five plan steps in
Figure~\ref{f:plans}(c) into a totally ordered plan, only two distinct
totally ordered plans are consistent with the ordering constraints:
$$\mbox{\sf dig-moat} \rightarrow \mbox{\sf dig-moat} \rightarrow
\mbox{\sf dig-moat} \rightarrow \mbox{\sf erect-castle} \rightarrow
\mbox{\sf erect-castle}\rightarrow\bullet$$ (success probability $0.65625$) and
$$\mbox{\sf dig-moat} \rightarrow \mbox{\sf dig-moat} \rightarrow
\mbox{\sf erect-castle} \rightarrow \mbox{\sf dig-moat} \rightarrow
\mbox{\sf erect-castle}\rightarrow\bullet$$ (success probability
$0.671875$).  Thus, the optimistic success probability of this
partially ordered plan is $0.671875$, the pessimistic $0.65625$.  Note
that the pessimistic interpretation is closely related to the standard
interpretation in deterministic partial order
planning~\cite{mccallester91}, in which a partially ordered plan is
considered successful only if {\em all\/} its consistent totally
ordered plans are successful.  The average success probability is
$0.6614583$, here, because there are 4 orderings that yield the poorer
plan described above, and 2 that yield the better one.

The looping plan in Figure~\ref{f:plans}(d) does not terminate until
it succeeds in building a sand castle, which it will do with
probability $1.0$ eventually.  Of course, not all looping plans
succeed with probability $1$; the totally ordered plan in
Figure~\ref{f:plans}(a) and the acyclic plan in
Figure~\ref{f:plans}(b) are special cases of such looping plans, for
instance.

\begin{figure*}
\centerline{\epsfig{file=plans.ps,width=5.5in}}
\caption{Example plans for the sand-castle domain}
\label{f:plans}
\end{figure*}

We define $|P|$ the {\em size of a plan\/} $P$ to be the number of
steps it contains.  We define $|M|$ the {\em size of a domain\/} $M$
to be the sum of the number of actions and states for a flat domain
and the sum of the sizes of the ST decision trees for a propositional
domain.

We consider the following decision problems.  The {\em plan-evaluation
problem\/} asks, given a domain $M$, a plan $P$ of size $|P|\leq|M|$,
and threshold $\theta$, whether its value is greater than $\theta$,
i.e., whether $$\Pr(M \mbox{ reaches a goal state under }P) >
\theta.$$ Note that the condition that $|P|\leq|M|$ is just a
technical one---we simply want to use $|M|$ to represent the size of
the problem.  Given an instance in which $|P|$ is larger than $|M|$,
we simply imagine ``padding out'' $|M|$ to make it larger.  The
important thing is that we are considering plans that are roughly the
size of the description of the domain, and not the size of the number
of states (which might be considerably larger).

The {\em plan-existence problem\/} asks, given domain $M$, threshold
$\theta$, and size bound $z\leq|M|$, whether there exists a plan $P$
of size $z$ with value greater than $\theta$.  Note that because we
bound the size of the target plan, the complexity of plan generation
is no more than that of plan existence; the technique of
self-reduction can be used to construct a valid plan using
polynomially many calls to an oracle for the decision problem.

Each of these decision problems has a different version for each type
of domain (flat and propositional) and each type of plan category
(looping, acyclic, totally ordered, and partially ordered under each
of the three interpretations).  We address all of these problems in
the succeeding sections.


\subsection{Complexity Classes}\label{sec-defis}

For definitions of complexity classes, reductions, and standard
results from complexity theory, we refer the reader to
\namecite{papadimitriou94}.

Briefly, we are looking only at the complexity of decision problems
(those with yes/no answers).  The class $\PTIME$ consists of problems
that can be decided in polynomial time; that is, given an instance of
the problem, there is a program for deciding whether the answer is yes
or no that runs in polynomial time.  The class $\NP$ contains the
problems with polynomial-time checkable polynomial-size certificates:
for any given instance and certificate, it can be checked in time
polynomial in the size of the instance whether the certificate proves
that the instance is in the $\NP$ set.  This means that, if the answer
to the instance is ``yes,'' this can be shown in polynomial time given
the right key.  The class $\coNP$ is the opposite---if the answer is
``no,'' this can be shown in polynomial time given the right key.

A problem $X$ is $\cC$-hard for some complexity class $\cC$ if every
problem in $\cC$ can be reduced to it; to put it another way, a fast
algorithm for $X$ can be used as a subroutine to solve any problem in
$\cC$ quickly.  A problem is $\cC$-complete if it is both $\cC$-hard
and in $\cC$; these are the hardest problems in the class.

In the interest of being complete, we next give more detailed
descriptions of the less familiar probabilistic and counting
complexity classes we use in this work.

The class $\sharpL$~\cite{alvarez93} is the class of functions $f$
such that, for some nondeterministic logarithmically space-bounded
machine $N$, the number of accepting paths of $N$ on $x$ equals
$f(x)$.  The class $\sharpP$ is defined analogously as the class of
functions $f$ such that, for some nondeterministic {\em
polynomial-time\/}-bounded machine $N$, the number of accepting paths
of $N$ on $x$ equals $f(x)$.  Typical complete problems are computing
the determinant for $\sharpL$ and computing the permanent for
$\sharpP$.

A function $f$ is defined to be in $\GapL$ if it is the {\em
difference\/} $f=g-h$ of $\sharpL$ functions $g$ and $h$.  While
$\sharpL$ functions have nonnegative integer values by definition,
$\GapL$ functions may have negative integer values (for example, if
$g$ always returns zero).

Probabilistic logspace~\cite{gill77}, $\PL$, is the class of sets $A$
for which there exists a nondeterministic logarithmically
space-bounded machine $N$ such that $x\in A$ if and only if the number
of accepting paths of $N$ on $x$ is greater than its number of
rejecting paths.  In the original definition of $\PL$, there is no
time bound on computations; \namecite{borodin83b} later showed $\PL
\subseteq \PTIME$.  \namecite{jung85} proved that any set computable
in probabilistic logspace is computable in probabilistic logspace
where the $\PL$ machine has a simultaneous polynomial-time bound.  In
apparent contrast to $\PTIME$-complete sets, sets in $\PL$ are
decidable using very fast parallel computations~\cite{borodin83b}.

Probabilistic polynomial time, $\PP$, is defined analogously.  A
classic $\PP$-complete problem is \MAJSAT: given a Boolean formula in
conjunctive normal form (CNF), does the majority of assignments satisfy
it?  According to \namecite{balcazar88}, the $\PP$-completeness of
\MAJSAT\ was shown in a combination of results from \namecite{gill77}
and \namecite{simon75}.

For polynomial-space-bounded computations, $\PSPACE$ equals
probabilistic $\PSPACE$, and $\sharpPSPACE$ is the same as the class
of polynomial-space-computable functions~\cite{ladner89}.

Note that $\LOGSPACE$, $\NLOGSPACE$, $\sharpL$, $\PL$ and $\GapL$ are
to logarithmic space what $\PTIME$, $\NP$, $\sharpP$, $\PP$, and
$\GapP$ are to polynomial time.  Also, the notion of completeness we
use in this paper relies on many-one reductions.  In the case of
$\PL$, the reduction functions are logarithmic space; in the case of
$\NP$ and above, they are polynomial time.

For any complexity classes $\cC$ and $\cC'$ the class $\cC\ora{\cC'}$
consists of those sets that are {\em $\cC$-Turing reducible\/} to sets
in $\cC'$, i.e., sets that can be accepted with resource bounds
specified by $\cC$, using some problem in $\cC'$ as a subroutine
(oracle) with instantaneous output.  For any class $\cC\subseteq
\PSPACE$, it is the case that $\NP\ora{\cC}\subseteq\PSPACE$, and
therefore $\NP\ora{\PSPACE}=\PSPACE$.

% Another useful result is that the class $\NPPP$ equals the
% ``$\le_m^{\NP}$'' closure of $\PP$~\cite{toran91}, which can be seen
% as the closure of $\PP$ under polynomial-time disjunctive reducibility
% with an exponential number of queries (each of the queries computable
% in polynomial time from its index in the list of queries).

The primary oracle-defined class we consider is $\NPPP$.  It equals
the ``$\le_m^{\NP}$'' closure of $\PP$~\cite{toran91}, which can be
seen as the closure of \PP\ under polynomial-time disjunctive
reducibility with an exponential number of queries (each of the
queries computable in polynomial time from its index in the list of
queries).  To simplify our completeness results for this class, we
introduce a decision problem we call \EMAJSAT\ (``exists'' \MAJSAT),
which generalizes the standard $\NP$-complete satisfiability problem
and the $\PP$-complete \MAJSAT.  An \EMAJSAT\ instance is defined by a
CNF Boolean formula $\phi$ on $n$ Boolean variables $x_1,\ldots,x_n$
and a number $k$ between $1$ and $n$.  The task is to decide whether
there is an initial partial assignment to variables $x_1,\ldots,x_k$
so that the majority of assignments that extend that partial
assignment satisfies $\phi$.  We prove that this problem is
$\NPPP$-complete in the Appendix.

The complexity classes we consider satisfy the following containment
properties and relations to other well-known classes:
$$
 	\LOGSPACE \subseteq \NLOGSPACE \subseteq \PL \subseteq \PTIME \subseteq
 	\stack{\NP}{\coNP}  \subseteq \PP \subseteq
 	\stack{\NPPP}{\coNPPP} \subseteq \PSPACE \subseteq \EXPTIME.
$$
Because $\PTIME$ is properly contained in $\EXPTIME$,
$\EXPTIME$-complete problems are provably intractable; the other
classes may equal $\PTIME$, although that is not generally believed to
be the case.

Several other observations are worth making here.  It is also known
that $\PH \subseteq \NPPP$, where $\PH$ represents the polynomial
hierarchy.  In a crude sense, $\PH$ is close to $\PSPACE$, and, thus,
our $\NPPP$--completeness results place important problems close to
$\PSPACE$.  However, some early empirical results~\cite{littman97g}
show that random problem instances from $\PP$ have similar properties
to random problem instances from $\NP$, suggesting that $\PP$ might be
close enough to $\NP$ for $\NP$-type heuristics to be effective.

\subsection{Results Summary}

Tables~\ref{t:flat} and~\ref{t:succinct} summarize our results, which
are explained in more detail in later sections.

The general flavor of our main results and techniques can be conveyed
as follows.  To show that a plan-evaluation problem is in a particular
complexity class $\cC$, we take the cross product of the steps of the
plan and the states of the domain and then look at the complexity of
evaluating the absorption probability of the resulting Markov chain
(i.e., the directed graph with probability-labeled edges).  The
complexity of the corresponding plan-existence problem is then bounded
by $\NP\ora{\cC}$, because the problem can be solved by guessing the
correct plan non-deterministically and then evaluating it; in many
cases, it is $\NP\ora{\cC}$-complete.  The appropriate complexity
class $\cC$ depends primarily on the representation of the
cross-product Markov chain.

\begin{table}
\centerline{
\begin{tabular}{|l|ccl|}
\hline
Plan Type        & {\bf Plan Evaluation} & {\bf Plan Existence} & Reference \\
\hline
unrestricted    & --- & $\PTIME$-complete & P \& T~\citeyear{papadimitriou87}\\
polynomial-depth & --- & $\PTIME$-complete& P \& T~\citeyear{papadimitriou87}\\
looping		& $\PL$-complete & $\NP$-complete & Section \ref{s:looping} \\
acyclic		 & $\PL$-complete & $\NP$-complete & Section \ref{s:acyclic}\\
totally ordered	 & $\PL$-complete & $\NP$-complete & Section \ref{s:acyclic}\\
partially ordered, optimistic
	& $\NP$-complete & $\NP$-complete & Section \ref{s:po} \\
partially ordered, average
	&  $\PP$-complete & $\NP$-complete & Section \ref{s:po} \\
partially ordered, pessimistic
 	& $\coNP$-complete & $\NP$-complete & Section \ref{s:po}\\
\hline 
\end{tabular}
}
\tablecaption{Complexity results for flat representations (P \&
T~(1987) is Papadimitriou and Tsitsiklis~(1987))}
\label{t:flat}
\end{table}

\begin{table}
\centerline{
\begin{tabular}{|l|ccl|}
\hline
Plan Type        & {\bf Plan Evaluation} & {\bf Plan Existence} & Reference \\
\hline
unrestricted    & --- & $\EXPTIME$-complete & \namecite{littman97b} \\
polynomial-depth & --- & $\PSPACE$-complete & \namecite{littman97b} \\
% & & & Goldsmith et al.~\citeyear{goldsmith96}\\
looping	& $\PSPACE$-complete & $\PSPACE$-complete & Section \ref{s:looping} \\
acyclic & $\PP$-complete & $\NPPP$-complete	& Section \ref{s:acyclic} \\
totally ordered & $\PP$-complete & $\NPPP$-complete	& Section \ref{s:acyclic} \\
partially ordered, optimistic
	& $\NPPP$-complete & $\NPPP$-complete & Section \ref{s:po} \\
partially ordered, average
	& $\PP$-complete & $\NPPP$-complete & Section \ref{s:po} \\
partially ordered, pessimistic
	& $\coNPPP$-complete & $\NPPP$-complete & Section \ref{s:po}\\
\hline
\end{tabular}
}
\tablecaption{Complexity results for propositional representations}
\label{t:succinct}
\end{table}

Exceptions to this basic pattern are the results for partially ordered
plans in Section~\ref{s:po}.  These appear to require a distinct set
of techniques.

It is also worth noting that, although propositional domains can be
exponentially more compact than flat domains, the computational
complexity of solving problems in propositional domains is not always
exponentially greater; in one instance, evaluating partially ordered
plans under the average interpretation, the complexity is actually the
same for flat and propositional domains!

We also prove results concerning plan evaluation and existence for
compactly represented plans ($\PP$-complete and $\NPPP$-complete,
Corollary~\ref{c:succinct-prob-plans}), plan existence of ``large
enough'' looping plans in flat domains ($\PTIME$-complete,
Theorem~\ref{th:loop}), plan evaluation and existence for looping
plans in deterministic propositional domains ($\PSPACE$-complete,
Theorems~\ref{th:PSPACE-complete1} and~\ref{th:PSPACE-complete2}), and
plan existence for polynomial-size looping plans in partially
observable domains ($\NP$-complete, Section~\ref{s:witness}).

\section{Acyclic Plans}
\label{s:acyclic}

In this section, we treat the complexity of generating and evaluating
acyclic and totally ordered plans.

\begin{theorem}\label{th:PL-complete}
The plan-evaluation problem for acyclic and totally ordered plans in
flat domains is $\PL$-complete.
\end{theorem}

\begin{proof}
First, we show $\PL$-hardness for totally ordered plans.
\namecite{jung85} proved that a set $A$ is in $\PL$ if and only if
there exists a logarithmically space-bounded and polynomially
time-bounded nondeterministic Turing machine $N$ with the following
property: For every input $x$, machine $N$ must have at least half of
its computations on input $x$ be accepting if and only if $x$ is in
$A$.  The machine $N$ can be transformed into a probabilistic Turing
machine $R$ such that for each input $x$, the probability that $R(x)$
accepts $x$ equals the fraction of computations of $N(x)$ that
accepted.  Given $R$, a planning domain $M$ can be described as
follows.  The state set of $M$ is the set of configurations of $R$ on
input $x$.  Note that a configuration consists of the contents of the
logarithmically space-bounded tape, the state, the location of the
read/write heads, and one symbol each from the input and output tapes.
Thus, a configuration can be represented with logarithmically many
bits, and there are only polynomially many such configurations.  The
state-transition probabilities of $M$ under the unique action $a$ are
the configuration transition probabilities of $R$.  All states
obtained from accepting configurations are goal states.  The totally
ordered plan consists of a ``step counter'' for $R$ on input $x$, and
each of its plan steps takes the only action $a$.  The probability
that the planning domain under this plan reaches a goal state is
exactly the probability that $R(x)$ reaches an accepting
configuration.  Thus, evaluating this totally ordered plan is
$\PL$-hard.

Since totally ordered plans are acyclic plans, this also proves
$\PL$-hardness of the plan-evaluation problem for acyclic plans.

Next, we show that the plan-evaluation problem is in $\PL$ for acyclic
plans.  Let $M=\langle \cS, s_0, \cA, t, \cM\rangle$ be a planning
domain, let $P=\langle V, v_0, E, \pi, \delta \rangle$ be an acyclic
plan, and let threshold $\theta$ be given.  We show how our question,
whether the probability that $M$ under $P$ reaches a goal state with
probability greater than $\theta$, can be equivalently transformed
into the question of whether a $\GapL$ function is greater than $0$.
The transformation can be done in logarithmic space.  As shown by
\namecite{allender96}, it follows that our question is in $\PL$.

At first, we construct a Markov chain $C$ from $M$ and $P$, which
simulates the execution or ``evaluation'' of $M$ under $P$.  Note that
a Markov chain can be seen as a probabilistic domain with only one
action in its set of actions.  Since there is no choice of actions, we
do not mention them in this construction.  The state space of $C$ is
$\cS\times V$, the initial state is $(s_0,v_0)$, the set of goal
states is $\cM\times V$, and the transition probabilities $t_C$ for
$C$ are
\[
t_C((s,v),(s',v'))=\left\{
\begin{array}{ll}
t(s,\pi(v),s'), &\mbox{ if $s'\in\delta(v,v')$}, \\
1, &\mbox{ if $v$ is a terminal step node, and $(s,v)=(s',v')$}, \\
% 1, &\mbox{ if $s\in\cM$, $\forall v\in V: (q,v)\not\in E$, 
%                                        and $(s,q)=(s',q')$}, \\
% 1, &\mbox{ if $s\in\cM$, $s=s'$, and $s\in\delta(q,q')$}, \\
0, &\mbox{ otherwise.}
\end{array}
\right.  
\]

Let $m$ be the number of plan steps of $P$ (i.e., $|V|$, the number of
nodes in the graph representing $P$).  Since states of $C$ that
contain a terminal step of $P$ are sinks in $C$, it follows that
$$
\Pr(\mbox{$M$ reaches a goal state under $P$})=
  \Pr(\mbox{$C$ reaches a goal state in exactly $m$ steps}).
$$
Let 
$$
p_C(s,m):=\Pr(\mbox{$C$ reaches a goal state in exactly $m$ steps
                        from initial state $s$}).
$$
Then,
$p_C((s_0,v_0),m)$ is the probability we want to calculate.
The standard inductive definition of $p_C$ used to evaluate plans by
dynamic programming is
\begin{eqnarray*}
p_C(s,0) &=&\left\{\begin{array}{ll}
                           1,\mbox{ if $s$ is a goal state of $C$,}\\
                           0,\mbox{ otherwise,}\\
                   \end{array}
            \right. \\
p_C(s,k+1) &=&\sum_{s'\in\cS\times V} t_C(s,s')\cdot p_C(s',k), \;\;\;\;0 \le
                           k \le m-1.
\end{eqnarray*}
Let $h$ be the maximum length of the representation of a
state-transition probability $t_C$.
Then, for
\begin{eqnarray*}
p_h(s,0) &=&\left\{\begin{array}{ll}
                           1,\mbox{ if $s$ is a goal state of $C$,}\\
                           0,\mbox{ otherwise,}\\
                   \end{array}
            \right. \\
p_h(s,k+1) &=&\sum_{s'\in\cS\times V} 2^h\cdot t_C(s,s')\cdot
                           p_h(s',k), \;\;\;\;0 \le k \le m-1,
\end{eqnarray*}
it follows that 
$p_C((s_0,v_0),m)=p_h((s_0,v_0),m)\cdot 2^{-hm}$.
Note that $p_h((s_0,v_0),m)$ is an integer value.
Therefore, $p_C((s_0,v_0),m)>\theta$
if and only if $p_h((s_0,v_0),m)- \lfloor 2^{hm}\theta \rfloor >0$.
In order to show that $p_C((s_0,v_0),m)>\theta$ is 
decidable in $\PL$,
it suffices to show that $p_h((s_0,v_0),m)$ is in $\GapL$.
Therefore, we ``unwind'' the inductive definition of $p_h$.
Let $T$ be the integer matrix obtained from $t_C$ with
$T_{(s,s')}=t_C(s,s')\cdot 2^{h}$.  We introduce the integer-valued
$T$ to show that $p_h$ can be composed from $\GapL$ functions using
compositions under which $\GapL$ is closed; as $t_C$ is not integer
valued, it cannot be used to show this.
We can write
$$
p_h(s,m) = \sum_{s'\in\cS\times V} (T^m)_{(s,s')}\cdot p_h(s',0).
$$

We argue that $p_h$ is in $\GapL$.  Each entry $T_{(s,s')}$ is
logspace computable from the domain $M$ and plan $P$.  Therefore, the
powers of the matrix are in $\GapL$, as shown by \namecite{vinay91}.
Because $\GapL$ is closed under multiplication and 
summation of polynomially many summands, it follows that $p_h\in
\GapL$. 
%%%XXX Should we cite the result that GapL is closed under mult?
%
Finally, we use closure properties of $\GapL$ from
\namecite{allender96}; since $\GapL$ is closed under subtraction, it
follows that the plan-evaluation for acyclic plans is in $\PL$.

Because totally ordered plans are acyclic plans, the plan-evaluation
problem for totally ordered plans is also in $\PL$.
\end{proof}

The technique of forming a Markov chain by taking the cross product of
a domain and a plan will be useful later.  
Plan-existence problems require a different set of techniques.

\begin{theorem}\label{th:NP-complete}
The plan-existence problem for acyclic and totally ordered plans in
flat domains is $\NP$-complete.
\end{theorem}

\begin{proof}
First, we show containment in $\NP$.  Given a planning domain $M$, a
threshold $\theta$, and a size bound $z\leq|M|$, guess a plan of the correct
form of size at most $z$ and accept if and only if $M$ reaches a goal
state with probability greater than $\theta$ under this plan.  Note that
checking whether a plan has the correct form can be done in polynomial
time.  Because the plan-evaluation problem is in $\PL$
(Theorem~\ref{th:PL-complete}), it follows that the plan-existence
problem is in $\NP$ (i.e., it is in $\NP\ora{\PL}$ = $\NP$).

To show the $\NP$-hardness of the plan-existence problem, we give a
reduction from the $\NP$-complete satisfiability problem for Boolean
formulae in conjunctive normal form.  We construct a planning domain
that evaluates a Boolean formula with $n$ variables, where a
$(n+2)$-step plan describes an assignment of values to the variables.
In the first step, a clause is chosen randomly.  At step $i+1$, the
planning domain ``checks'' whether the plan satisfies the appearance
of variable $i$ in that clause.  If so, the clause is marked as
satisfied.  After $n+1$ steps, if no literal was satisfied in that
clause, then no goal state is reached through this clause, otherwise,
a transition is made to the goal state.  Therefore, the goal state
will be reached with probability $1$ (greater than $1-1/m$) if and
only if all clauses are satisfied---the plan describes a satisfying
assignment.

We formally define the reduction, which is similar to one presented by
\namecite{papadimitriou87}.  Let $\phi$ be a CNF formula with $n$
variables $x_1,\ldots,x_n$ and $m$ clauses $C_1,\ldots,C_m$.  Let the
sign of an appearance of a variable in a clause be $-1$ if the
variable is negated, and $1$ otherwise.  Define the planning domain
$M(\phi)=\langle \cS,s_0,\cA,t,\cM \rangle$ where
$$
\begin{array}{ccl}
\cS & = & \{\mbox{sat}(i,j), \mbox{unsat}(i,j)\mid 1\leq i\leq n+1, 1\leq j\leq m\} 
                             \cup \{s_0,s_{\rm acc},s_{\rm rej}\}, \\
\cA & = & \{\as(i,b) \mid 1 \leq i \leq n, b \in \{-1,1\}\}\cup\{\st, \ed\}, \\
\cM & = & \{s_{\rm acc}\}, \\[1ex]
t(s,a,s') & = & \left\{ \begin{array}{ll}
\frac{1}{m}, & \mbox{ if } s=s_0, a=\st, s'=\mbox{unsat}(1,j), 1\le j\le m, \\
1, & \mbox{ if } s=s_0, a\neq\st, s'=s_{\rm rej}, \\
1, & \mbox{ if } s=\mbox{unsat}(i,j), a=\as(i,b), s'=\mbox{sat}(i+1,j), i \le n,\\
    & \quad      \mbox{ $x_i$ appears in $C_j$ with sign $b$},\\
1, & \mbox{ if } s=\mbox{unsat}(i,j), a=\as(i,b), s'=\mbox{unsat}(i+1,j), i \le n,\\
    & \quad     \mbox{ $x_i$ does not appear in $C_j$ with sign $b$},\\
1, & \mbox{ if } s=\mbox{unsat}(i,j), a=\as(i',b)\mbox{ or }a=\st\mbox{ or }a=\ed,\\
    & \quad s'=s_{\rm rej}, i'\neq i \le n, b\in\{-1,1\},\\
1, & \mbox{ if } s=\mbox{unsat}(n+1,j), s'=s_{\rm rej},\\
1, & \mbox{ if } s=\mbox{sat}(i,j), a=\as(i,b), s'=\mbox{sat}(i+1,j), i \le n,\\
1, & \mbox{ if } s=\mbox{sat}(i,j), a=\as(i',b)\mbox{ or }a=\st\mbox{ or }a=\ed,\\
    & \quad	s'=s_{\rm rej}, i'\neq i \le n,\\
1, & \mbox{ if } s=\mbox{sat}(n+1,j), a=\ed, s'=s_{\rm acc},\\
1, & \mbox{ if } s=\mbox{sat}(n+1,j), a\neq\ed, s'=s_{\rm rej},\\
1, & \mbox{ if } s=s'=s_{\rm rej} \mbox{ or } s=s'=s_{\rm acc}, \\
0, & \mbox{ otherwise.}
\end{array} \right. 
\end{array}
$$

The meaning of the states in this domain is as follows.  When the
domain is in state $\mbox{sat}(i,j)$ for $1\leq i\leq n$, $1\leq j\leq
m$, it means the formula has been satisfied, and we are currently
checking variable $i$ in clause $j$.  State $\mbox{sat}(n+1,j)$ for
all $1\leq j\leq m$ means that we've finished verifying clause $j$ and
it was satisfied.  The meanings are similar for the ``unsat'' states.
Of course, $s_0$ is the initial state and $s_{\rm acc}$ and $s_{\rm
rej}$ are the accepting and rejecting states, respectively.

The actions in this domain are $\st$ and $\ed$, which mark the
beginning and end of the assignment, and $\as(i,b)$ for $1 \leq i \leq
n$, $b \in \{-1,1\}$, which assign the truth value $b$ to variable
$i$.  Figure~\ref{f:flatnp} gives the domain generated by this
reduction from a simple Boolean formula.  By the description of the
reduction, $M(\phi)$ can be computed from $\phi$ in time polynomial in
$|\phi|$.

\ifthenelse{\boolean{nofigures}}
{ }
{
\begin{figure}
\centerline{\input{SAT.pstex_t}}
% \centerline{\epsfig{file=atnp.ps,width=4.25in}}
\caption{A domain generated from the Boolean formula $(x_1\vee\neg
x_2)\wedge(\neg x_1 \vee x_3)$}
\label{f:flatnp}
\end{figure}
}

By construction, $M(\phi)$ under $z=(n+2)$-step plan $P$ can only
reach goal state $s_{\rm acc}$ if $P$ has the form
$$\st\rightarrow\as(1,b_1)\rightarrow\as(2,b_2)\rightarrow\cdots
\rightarrow\as(n,b_n)\rightarrow\ed\rightarrow\bullet.$$ $P$ reaches $s_{\rm acc}$ with
probability $1$ if and only if $b_1,\ldots,b_n$ is a satisfying
assignment for the $n$ variables in $\phi$.  This shows that Boolean
satisfiability polynomial-time reduces to the plan-existence problem
for totally ordered and acyclic plans, showing that it is $\NP$-hard.
\end{proof}

Note that if we bound the plan depth (horizon) instead of the plan
size, the plan-existence problem for acyclic plans in flat domains is
\PTIME-complete~\cite{goldsmith97,papadimitriou87}.  Limiting the plan
size makes the problem more difficult because it is possible to force
the planner to take the same action from different states; figuring
out how to do this without sacrificing plan quality is very
challenging.

In propositional domains, plan evaluation is harder because of the
large number of states.

\begin{theorem}\label{th:PP-complete}
The plan-evaluation problem for acyclic and totally ordered plans in
propositional domains is $\PP$-complete.
\end{theorem}

\begin{proof}
To show $\PP$-hardness for totally ordered plans, we give a reduction
{from} the $\PP$-complete problem \MAJSAT: given a CNF Boolean formula
$\phi$, does the majority of assignments satisfy it?

Given $\phi$, we construct a planning domain $\Mb(\phi)$ and a 1-step
plan such that the plan achieves the goal with probability greater
than $\theta=1/2$ if and only if the majority of assignments satisfies
$\phi$.  The planning domain $\Mb(\phi)$ consists of a single action
{\sf evaluate}, which is also the 1-step plan to be evaluated.  There
are $n+m+2$ propositions in $\Mb(\phi)$; {\bf x}$_1$ through {\bf
x}$_n$, which correspond to the $n$ variables of $\phi$; {\bf
clause}$_1$ through {\bf clause}$_m$, which correspond to the $m$
clauses of $\phi$; {\bf satisfied}, which is also the sole element of
the goal set; and {\bf done}, which insures that {\sf evaluate} is
only executed once (this is important when this domain is used later
in Theorem~\ref{th:NPPP-complete} to show the complexity of plan
existence).  In the initial state, all propositions are false.

The {\sf evaluate} action generates a random assignment to the
variables of $\phi$, evaluates the clauses ({\bf clause}$_i$ is true
if any of the literals in the $i$th clause is true), and evaluates the
entire formula ({\bf satisfied} is true if all the clauses are true).
Figure~\ref{f:eval} gives an ST representation of {\sf evaluate}, in
which $x_{a^i}, x_{b^i}, \ldots$ represent the variables in clause
$i$.

\ifthenelse{\boolean{nofigures}}
{ }
{
\begin{figure}
\centerline{\epsfig{file=e.ps,width=4.5in}}
\caption{Sequential-effects-tree representation for {\sf evaluate}}
\label{f:eval}
\end{figure}
}

By construction, $\phi$ is in \MAJSAT\ if and only if $\Mb(\phi)$
reaches a goal state with probability greater than $\theta = 1/2$ under
the plan consisting of the single action {\sf evaluate}.

We next show membership in $\PP$ for acyclic plans.  We do this by
showing that a planning domain $\Mb$ and an acyclic plan $P$ induce a
computation tree consisting of all paths through $\Mb$ under $P$.
Evaluating this computation tree can be accomplished by a $\PP$
machine.

% An alternate proof might be to create a huge circuit by taking the
% cross product of proposition and plan step and setting it up so that
% a variable is true if a goal is reached.

Let $b$ be a bound on the number of bits used to specify probabilities
in the leaves of the decision trees representing $\Mb$.\footnote{We
represent numbers in polynomial-precision binary representation.  In
principle, this could introduce round-off errors if planning problems
are specified in some other form.}  Consider a
{\em computation tree\/} defined as follows.  It has root labeled
$\langle s_0, v_0 \rangle$.  If, in the planning domain $\Mb$, the
probability of reaching state $s'$ from $s$ given action $\pi(v)$ is
equal to $\nu$, then $\langle s, \pi(v)\rangle$ will have $\nu\cdot
2^b$ children labeled $\langle s',\delta(v,s')\rangle$.  Each of the
identically labeled child nodes is independent but is defined
identically to the others.  Thus, the number of paths with a given set
of labels corresponds to the probability of that trajectory through
the domain and plan multiplied by $(2^b)^h$, where $h$ is the depth of
the plan.

The number of accepting computations is, therefore, more than
$\theta\cdot (2^b)^h$ if and only if the probability of achieving the
goal is more than $\theta$.  Note that $b$ is inherent in the planning
domain, rather than in $h$.  A $\PP$ machine accepts if more than half
of the final states are accepting, so if $\theta \neq 1/2$, it will be
necessary to pad the computation tree by introducing ``dummy''
branches that accept or reject in the right proportions.
\end{proof}

The plan-existence problem is essentially equivalent to guessing and
evaluating a valid plan.

\begin{theorem}\label{th:NPPP-complete}
The plan-existence problem for acyclic and totally ordered plans in
propositional domains is $\NPPP$-complete.
\end{theorem}

\begin{proof}
Containment in $\NPPP$ for both totally ordered and for acyclic plans
follows from the fact that a polynomial-size plan can be guessed in
polynomial time and checked in $\PP$ (Theorem~\ref{th:PP-complete}).

Hardness for $\NPPP$ for both totally ordered and acyclic plans can be
shown using a reduction from \EMAJSAT, shown $\NPPP$-hard in the
Appendix.  The reduction echoes the one used in the $\PP$-hardness
argument in the proof of Theorem~\ref{th:PP-complete}.

Given a CNF Boolean formula $\phi$ with variables $x_1,\ldots,x_n$,
and a number $k$, we construct a planning domain $\Mb(\phi,k)$ such
that a plan exists that can reach the goal with probability greater
than $\theta = 1/2$ if and only if there is an assignment to the
variables $x_1,\ldots,x_k$ such that the majority of assignments to
the remaining variables satisfies $\phi$.  The planning domain
$\Mb(\phi,k)$ consists of the action {\sf evaluate} from
Theorem~\ref{th:PP-complete} and one action,
{\sf set-x}$_i$, for each of the first $k$ variables.
%{\sf set-x}$_1$ through {\sf set-x}$_k$.  
Just as in the proof of Theorem~\ref{th:PP-complete}, there are
$n+m+2$ propositions in $\Mb(\phi,k)$, all initially false: {\bf
x}$_1$ through {\bf x}$_n$, which correspond to the $n$ variables of
$\phi$; {\bf clause}$_1$ through {\bf clause}$_m$, which correspond to
the $m$ clauses of $\phi$; {\bf satisfied}; and {\bf done}, which
insures that {\sf evaluate} is only executed once.  The goal set
contains {\bf satisfied} and {\bf done}.
% are the goal set.  In the initial state, all propositions are false.

For $1 \le i \le k$, action {\sf set-x}$_i$ makes proposition {\bf
x}$_i$ true.  Analogously to Theorem~\ref{th:PP-complete}, the {\sf
evaluate} action generates a random assignment to the remaining
variables of $\phi$, evaluates the clauses ({\bf clause}$_i$ is true
if any of the literals in the clause is true), and evaluates the
entire formula ({\bf satisfied} is true if all the clauses are true),
and sets {\bf done} to true.  If {\bf done} is true, no further action
can make {\bf satisfied} true.

If the pair $\phi, k$ is in $\EMAJSAT$, then there exists an
assignment $b_1\ldots b_k$ to the first $k$ variables of $\phi$ such
that the majority of assignments to the rest of the variables
satisfies $\phi$.  Therefore, the plan applying steps {\sf set-x}$_i$
for all $i$ with $b_i=1$ followed by an {\sf evaluate} action reaches
a goal state with probability greater than $\theta=1/2$.

Conversely, assume $\Mb(\phi,k)$ under
totally ordered plan $P$ reaches a goal state with probability greater
than $1/2$.  Since the {\sf evaluate} action is the only action
setting {\bf done} to true, and since no action reaches the goal once
{\bf done} is set to true, we can assume without loss of generality
that $P$ consists of a sequence of steps {\sf set-x}$_i$ that ends
with {\sf evaluate}.  By construction, the assignment to
$x_1,\ldots,x_k$ assigning $1$ exactly to those variables set by $P$
is an assignment under which the majority of the assignments to the
rest of the variables satisfies $\phi$, and therefore $\phi,k$ is in
$\EMAJSAT$.

Since every totally ordered plan is acyclic, the same hardness holds
for acyclic plans.
\end{proof}

In the above results, we consider both flat and compactly represented
(propositional) 
planning domains but only flat plans.  Compactly represented plans are
also quite useful.  
\begin{quote}
A {\em compact acyclic plan\/} is an acyclic plan in which the names
of the plan steps are encoded by a set of propositional variables and
the step-transition function $\delta$ between plan steps is
represented by a set of decision trees, just as in ST.  We require
that the plan has depth polynomial in the size of the representation,
even though the total number of steps in the plan might be exponential
due to the logarithmic succinctness of the encodings.
\end{quote}

Because the plan-domain cross-product technique used in the proof of
Theorem~\ref{th:PP-complete} generalizes to compact acyclic plans, the
same complexity results apply.  This also holds true for a {\em
probabilistic acyclic plan\/}, which is an acyclic plan that can make
random transitions between plan steps (i.e., the step-transition
function $\delta$ is stochastic).  These insights can be combined to
yield the following corollary of Theorems~\ref{th:PP-complete}
and~\ref{th:NPPP-complete}.

\begin{corollary}\label{c:succinct-prob-plans}
The plan-evaluation problem for compact probabilistic acyclic plans in
propositional domains is $\PP$-complete and the plan-existence problem
for compact probabilistic acyclic plans in propositional domains is
$\NPPP$-complete.
\end{corollary}

We mention probabilistic plans here for two reasons.  First, the
behavior of some planning structures (such as partially ordered plan
evaluation under the average interpretation, discussed in
Section~\ref{s:po}) can be thought of as generating probabilistic
plans.  Second, there are many instances in which simple probabilistic
plans perform nearly as well as much larger and more complicated
deterministic plans; this notion is often exploited in the field of
randomized algorithms.  Work by \namecite{platzman81} (described by
\namecitenoparens{lovejoy91}) shows how the idea of randomized plans can come
in handy for planning in partially observable domains.

\section{Looping Plans}
\label{s:looping}

Looping plans can be applied to infinite-horizon control.  The
complexity of plan existence and plan evaluation in flat domains
(Theorems~\ref{th:PL-complete} and~\ref{th:NP-complete}) does not
depend on the presence or absence of loops in the plan.

\begin{theorem}\label{th:PL-complete2}
The plan-evaluation problem for looping plans in flat domains is
$\PL$-complete.
\end{theorem}

\begin{proof}
Given a domain $M$ and a looping plan $P$, we can construct a product
Markov chain $C$ as in the proof of Theorem~\ref{th:PL-complete}.  As
in the proof of Theorem~6 of \namecite{allender96}, this chain can be
constructed such that it has exactly one accepting and exactly one
rejecting state; both of these states are absorbing.  The probability
that $M$ reaches a goal state under $P$ equals the probability that
$C$ reaches its accepting state if started in its initial state, which
is the product of the initial states of $M$ and $P$.  In the proof of
Theorem~6 of \namecite{allender96}, it is shown that the construction
of the Markov chain and the computation of whether it reaches its
final state with probability greater than $\theta$ can be performed in
$\PL$.

$\PL$-hardness is implied by Theorem~\ref{th:PL-complete},
since acyclic plans are a special case of looping plans.
\end{proof}

\begin{theorem}\label{th:loop}
The plan-existence problem for looping plans in flat domains is
$\NP$-complete in general, but $\PTIME$-complete if 
the size of the desired plan is at least the size of the state or
action space (i.e., $z \ge \min(|\cS|,|\cA|)$).
\end{theorem}

\begin{sketch}
$\NP$-completeness follows from the proof of
Theorem~\ref{th:NP-complete}; containment and hardness still hold if
plans are permitted to be looping.

However, this is only true if we are forced to specify a plan whose
size is small with respect to the size of the domain.  If our looping
plan is allowed to have a number of states that is at least as large
as the number of states or actions in the domain, the problem can be
solved in polynomial time.

It is known that for Markov decision processes such as these the
maximum probability of reaching a goal state equals the maximum
probability of reaching a goal state under any infinite-horizon {\em
stationary policy\/}, where a stationary policy is a mapping from
states to actions that is used repeatedly to choose actions at each
time step.  It is known that such an optimal stationary policy can be
computed in polynomial time via linear programming~\cite{condon92}.
Any stationary policy for a domain $M=\langle \cS, s_0, \cA, \cM, t
\rangle$ can be written as a looping plan, although, of course, not
all looping plans correspond to stationary policies.

We show that for any fixed stationary policy $p:\cS\rightarrow\cA$,
there are two simple ways a looping plan $P=(V,v_0,E,\pi,\delta)$ can
be represented.  First, let $V=\cA$, $v_0=p(s_0)$, $\pi(v)=v$, and
$\delta(v,v')=\{s\in\cS\mid p(s)=v'\}$.  It follows that whenever $M$
reaches state $s$, then the action applied according to the looping
plan is the same as according to $P$.

Second, let $V=\cS$, $v_0=s_0$, $\pi(v)=p(v)$, and
$\delta(v,v')=\{v'\}$.  It follows that whenever $M$ reaches state
$s$, the plan will be at the node corresponding to that state and,
therefore, the appropriate action for that state will be applied by
the looping plan.  Therefore, the maximum probability of reaching a
goal state can be obtained by either of these looping plans.

Since the best stationary policy can be computed in polynomial time,
the best looping plan can be computed in polynomial time, too.
$\PTIME$-hardness follows from a theorem of
\namecite{papadimitriou87}.
\end{sketch}

In propositional domains, the complexity of plan existence and plan
evaluation of looping plans is quite different from the acyclic case.
Looping plan evaluation is very hard.

\begin{theorem}\label{th:PSPACE-complete1}
The plan-evaluation problem for looping plans in both deterministic
and stochastic propositional domains is $\PSPACE$-complete.
\end{theorem}

\begin{proof}
Recall that the plan-evaluation problem for flat domains is in $\PL$
(Theorem~\ref{th:PL-complete}).  For a planning domain with $c^n$
states and a representation of size $n$, a looping plan can be
evaluated in probabilistic space ${\cal O}(\log(c^n))$
(Theorem~\ref{th:PL-complete2}), which is to say probabilistic space
polynomial in the size of the input.  This follows because the ST
representation of the domain can be used to compute entries of the
transition function $t$ in polynomial space.  Since probabilistic
$\PSPACE$ equals $\PSPACE$, this shows that the plan-evaluation problem
for looping plans in stochastic propositional domains is in $\PSPACE$.

% To see that the evaluation can be carried out in the space described,
% observe the following: given two states in the system, $s_1$ and
% $s_2$, each a setting of the $n$ variables, and a state in the plan
% (of comparable length), one can easily compute the probability of the
% transition from $s_1$ to $s_2$ under this plan.  (It will be $0$ if
% the specified action does not lead to $s_2$, and otherwise the product
% of the probabilities for each bit.)  This takes space polynomial in
% the size of the input, i.e., logarithmic in the size of the state
% space.

It remains to show $\PSPACE$-hardness for deterministic propositional
domains.  Let $N$ be a deterministic polynomial-space-bounded Turing
machine.  The moment-to-moment computation state (configuration) of
$N$ can be expressed as a polynomial-length bit string that encodes
the contents of the Turing machine's tape, the location of the
read/write head, the state of $N$'s finite-state controller, and
whether or not the machine is in an accepting state.

For any input $x$, we describe how to construct in polynomial time a
deterministic planning domain $\Mb(x)$ and a single-action looping
plan that reaches a goal state of $\Mb(x)$ if and only $x$ is accepted
by Turing machine $N$.

Given a description of $N$ and $x$, one can, in time polynomial in the
size of the descriptions of $N$ and $x$, produce a description of a
Turing machine $T$ that computes the transition function for $N$.  In
other words, $T$ on input $c$, a configuration of $N$, outputs the
next configuration of $N$.  (In fact, $T$ can even check whether $c$
is a valid configuration in the computation of $N(x)$ by simulating
that computation.)  By an argument similar to that used in Cook's
theorem, $T$ can be modeled by a polynomial-size circuit.  This
circuit takes as input the bit string describing the current
configuration of $N$ and outputs the next configuration.

Next, we argue that the computation of this circuit can be expressed
by an action {\sf compute} in ST representation.  There is one
proposition in $\Mb(x)$ for each bit in the configuration, plus one
for each gate of the circuit.  The three standard gates, ``and,''
``or,'' and ``not'' are all easily represented as decision trees.  By
ordering the decision trees in {\sf compute} according to a
topological sort of the gates of the circuit, a single {\sf compute}
action can compute precisely the same output as the circuit.
Figure~\ref{f:circuit} illustrates this conversion for a simple
circuit, which gives the form of the ``not'' ($i_1$), ``and'' ($i_2$),
and ``or'' ($i_3$) gates.

\ifthenelse{\boolean{nofigures}}
{ }
{
\begin{figure}
\centerline{\epsfig{file=circ.ps,width=4.5in}}
\caption{A circuit and its representation as a sequential-effects tree}
\label{f:circuit}
\end{figure}
}

We can now describe the complete reduction.  The planning domain
$\Mb(x)$ consists of the single action {\sf compute} and the set of
propositions described in the previous paragraph.  The initial state
is the initial configuration of the Turing machine $N$, and the goal
set is the proposition corresponding to whether or not the
configuration is an accepting state for $N$.

Because all transitions are deterministic and only one action can be
chosen, it follows that the goal state is reached with probability $1$
(greater than $1/2$, for example) under the plan that repeatedly
chooses {\sf compute} until an accepting state is reached if and only
if polynomial-space machine $N$ on input $x$ accepts.
\end{proof}

A similar argument shows that looping plan existence is not actually
any harder than looping plan evaluation.

\begin{theorem}\label{th:PSPACE-complete2}
The plan-existence problem for looping plans in both deterministic and
stochastic propositional domains is $\PSPACE$-complete.
\end{theorem}

\begin{proof}
Hardness for $\PSPACE$ follows from the same construction as in the
proof of Theorem~\ref{th:PSPACE-complete1}: either the one-step
looping plan is successful, or it is not.  No other plan yields a
better result.

Recall that we are only interested in determining whether there is a
plan of size $z$, 
where $z$ is bounded by the size of the domain,
that reaches
the goal with a given probability.  The problem is in $\PSPACE$
because the plan can be guessed in polynomial time and checked in
$\PSPACE$ (Theorem~\ref{th:PSPACE-complete1}).  Because
$\NP\ora{\PSPACE}=\PSPACE$, the result follows.
\end{proof}

As we mentioned earlier, the {\em unrestricted\/} infinite-horizon
plan-existence problem is $\EXPTIME$-complete~\cite{littman97b}; this
shows the problem of determining unrestricted plan existence is
$\EXPTIME$-hard only because some domains require plans that are
larger than polynomial-size looping plans.

Because Theorem~\ref{th:PSPACE-complete2} shows $\PSPACE$-completeness
for determining plan existence in deterministic domains, it is closely
related to the $\PSPACE$-completeness result of \namecite{bylander94}.
The main difference between the two results is that our theorem
applies to more compact plans (polynomial instead of exponential) with
more complex operator descriptions (conditional effects instead of
preconditions with add and delete lists) that can include loops.
Also, as the proofs above show, $\PSPACE$-hardness is retained even in
planning domains with only one action, so it is the looping that makes
looping plans hard to work with.



\section{Partially Ordered Plans}
\label{s:po}

Partially ordered plans are a popular representation because they
allow planning algorithms to defer a precise commitment to the
ordering of plan steps until it becomes necessary in the planning
process.  A $k$-step partially ordered plan corresponds to a set of
$k$-step totally ordered plans---all those that are consistent with
the given partial order.  The evaluation of a partially ordered plan
can be defined to be the evaluation of the best, worst, or average
member of the set of consistent totally ordered plans; these are the
optimistic, pessimistic, and average interpretations, respectively.

The plan-evaluation problem for partially ordered plans is different
{from} that of totally ordered plans.  This is because a single
partial order can encode all totally ordered plans.  Hence, evaluating
a partially ordered plan involves figuring out the best (in case of
optimistic interpretation) or the worst (for pessimistic
interpretation) member, or the average (for average interpretation) of
this combinatorial set.

\begin{theorem}\label{th:opt}
The plan-evaluation problem for partially ordered plans in flat
domains is $\NP$-complete under the optimistic interpretation.
\end{theorem}

\begin{sketch}
Membership in $\NP$ follows from the fact that we can guess any
totally ordered plan consistent with the given partial order
and accept if and only if the domain reaches a goal state
with probability more than $\theta$.  Remember that this evaluation
can be performed in $\PL$ 
(Theorem~\ref{th:PL-complete}), and therefore 
deterministically in polynomial time.

The hardness proof is a variation of the construction used in
Theorem~\ref{th:NP-complete}.  The partially-ordered
plan to evaluate has the form given
in Figure~\ref{f:po}; the consistent total orders are of the form
$$\st\rightarrow\as(1,b_1)\rightarrow\as(1,-b_1)\rightarrow\as(2,b_2)\rightarrow\as(2,-b_2)\rightarrow$$
$$\cdots\rightarrow\as(n,b_n)\rightarrow\as(n,-b_n)\rightarrow\ed\rightarrow\bullet,$$
where $b_i$ is either $1$ or $-1$.
Each of the possible plans can be interpreted as an
assignment to $n$ Boolean variables by ignoring every second assignment
action.
%%%XXX The next part is redundant.  Is that on purpose?
The construction in Theorem~\ref{th:NP-complete} shows how to turn a
CNF formula $\phi$ into a planning domain $M(\phi)$, and it can easily
be modified to ignore every second action.
% This implies that the plan
% given by the best total order consistent with the given partial order
% reaches the goal with probability 1 if and only if $\phi$ is
% satisfiable.
Thus, the best totally ordered plan consistent with the given
partially ordered plan reaches the goal with probability $1$ if and
only if it reaches the goal with probability greater than $1-2^{-m}$
if and only if it satisfies all clauses of $\phi$ if and only if
$\phi$ is satisfiable.
\end{sketch}

\ifthenelse{\boolean{nofigures}}
{ }
{
\begin{figure}
\centerline{\epsfig{file=po.ps,height=2.5in}}
% \centerline{\input{poSAT.pstex_t}}
\caption{A partially ordered plan that can be hard to evaluate}
\label{f:po}
\end{figure}
}

\begin{theorem}\label{th:pess}
The plan-evaluation problem for partially ordered plans in flat
domains is $\coNP$-complete under the pessimistic interpretation.
\end{theorem}

\begin{sketch}
Both the proof of membership in $\coNP$ and the proof of hardness are
very similar to the proof of Theorem~\ref{th:opt}.  We show a
reduction from the $\coNP$-complete set $\overline{\SAT}$ of
unsatisfiable formulae in CNF.  The plan to evaluate has the form
given in Figure~\ref{f:po} and is interpreted as above.  As in the
proof of Theorem~\ref{th:NP-complete}, we construct a planning domain
$M'(\phi)$, but we take $\cM = \{s_{\rm rej}\}$ as goal states, where
the state $s_{\rm rej}$ is reached with probability greater than $0$
if and only if the assignment does not satisfy one of the clauses of
formula $\phi$.  A formula is unsatisfiable if and only if under every
assignment at least one of the clauses is not satisfied.  Therefore,
the probability that $M'(\phi)$ reaches a goal state under a given
totally ordered plan is greater than $0$ if and only if the plan
corresponds to an unsatisfying assignment.  Finally, the minimum of
that probability over all consistent partially ordered plans is
greater than $0$ if and only if $\phi$ is unsatisfiable.
\end{sketch}

\begin{theorem} \label{th:open}
The plan-evaluation problem for partially ordered plans in flat
domains is $\PP$-complete under the average interpretation.
\end{theorem}

\begin{proof}
Under the average interpretation, we must decide whether the average
evaluation over all consistent totally ordered plans is greater than
threshold $\theta$.  This can be decided in $\PP$ by guessing uniformly
a totally ordered plan and checking its consistency with the given
partially ordered plan in polynomial time.  If the guessed totally
ordered plan is consistent, it can be evaluated in polynomial time
(Theorem~\ref{th:PL-complete}) and accepted or rejected
% with the appropriate probability. zzz?
as appropriate.  If the guessed plan is inconsistent, the computation
accepts with probability $\theta$ and rejects with probability
$1-\theta$, leaving the average over the consistent orderings
unchanged with respect to the threshold $\theta$.

The $\PP$-hardness is shown by a reduction from the $\PP$-complete
$\MAJSAT$.  Let $\phi$ be a formula in CNF.  We show how to construct
a domain $M(\phi)$ and a partially ordered plan $P(\phi)$ such that
$\phi\in\MAJSAT$ if and only if the average performance of $M(\phi)$
under a totally ordered plan consistent with $P(\phi)$ is greater than
$1/2$.

Let $\phi$ consist of the $m$ clauses $C_1,\ldots,C_m$,
which contain $n$ variables $x_1,\ldots,x_n$.
Domain $M(\phi)=\langle \cS, s_0, \cA, t, \cM \rangle$ has actions 
$$
\cA = \{\as(i,b) \mid i\in\{1,\ldots, n\}, b\in\{-1,1\}\}
    \cup \{\st, \ch, \ed\} .
$$
Action $\as(i,b)$ will be interpreted as ``assign sign $b$ to $x_i$.''
The partially ordered plan $P(\phi)$ has plan steps
$$
V = \{\sigma(i,b,h) \mid i\in\{1,\ldots, n\}, b\in\{-1,1\}, h\in\{1,\ldots,m\}\}
           \cup \{\st, \ch, \ed\} 
$$
and mapping $\pi:V\rightarrow\cA$ with
$$
\pi(\sigma)=\sigma \mbox{ for $\sigma\in \{\st, \ch, \ed\}$, and\ \ } 
\pi(\sigma(i,b,h)) = \as(i,b).
$$
The order $E$ requires that a consistent plan has \st\ as the first and
\ed\ as the last step.  The steps in between are arbitrarily ordered.
More formally,
$$
E=\{(\st,q) \mid q\in V-\{\st,\ed\}\}
         \cup\{(q,\ed) \mid q\in V-\{\st,\ed\}\} .
$$

Now, we define how the domain $M(\phi)$ acts on a given totally
ordered plan $P$ consistent with $P(\phi)$.  Domain $M(\phi)$ consists
of the cross product of the following polynomial-size deterministic
domains $M_s$ and $M_{\phi}$, to which a final probabilistic
transition will be added.

Before we describe $M_s$ and $M_{\phi}$ precisely, here are their
intuitive definitions.  The domain $M_s$ is satisfied by plans that
have the form of an assignment to the $n$ Boolean variables with the
restriction that the assignment is repeated $m$ times (for easy
checking).  The domain $M_{\phi}$ is satisfied by plans that
correspond to satisfying assignments.  The composite of these two
domains is only satisfied by plans that correspond to satisfying
assignments.  We will now define these domains formally.

First, $M_s$ checks whether the totally ordered plan matches the
regular expression
\begin{eqnarray*}
\lefteqn{\st \; (\as(1,0)^m|\as(1,1)^m)} \\
&&\cdots\;(\as(n,0)^m|\as(n,1)^m) \\
&&\ch \; ((\as(1,0)|\as(1,1))\cdots(\as(n,0)|\as(n,1)))^m.
\end{eqnarray*}
Note that the $m$ here is a constant.  Let ``{good}'' be the state
reached by $M_s$ if the plan matches that expression.  Otherwise, the
state reached is ``bad''.  To clarify, the actions before \ch\ are
there simply to ``use up'' the extra steps not used in specifying the
assignment in the partially ordered plan.

Next, $M_{\phi}$ checks whether the sequence of actions following the
\ch\ action satisfies the clauses of $\phi$ in the following sense.
Let $a_1\cdots a_k$ be this sequence.  $M_{\phi}$ interprets each
subsequence $a_{1+(j-1)n} \cdots a_{n+(j-1)n}$ with
$a_{l+(j-1)m}=\as(x,b_l)$ as assignment $b_1,\ldots,b_n$ to the
variables $x_1,\ldots,x_n$, and checks whether this assignment
satisfies clause $C_j$.  If all single clauses are satisfied in this
way, then $M_{\phi}$ reaches state ``satisfied''.

Note that $M_s$ and $M_{\phi}$ are defined so that they do not deal
with the final \ed\ action.  $M(\phi)$ consists of the product domain
of $M_s$ and $M_{\phi}$ with the transitions for action \ed\ as
follows.  If $M$ is in state $({\rm bad},q)$ for any state $q$ of
$M_{\phi}$, then action \ed\ lets $M$ go probabilistically to state
``accept'' or to state ``reject'', with probability $1/2$ each; if $M$
is in state $({\rm good},{\rm satisfied})$, the $M$ under action \ed\
goes to state ``accept'' (with probability $1$); otherwise, $M$ under
action \ed\ goes to state reject (with probability $1$).  The set of
goal states of $M$ consists of the only state ``accept''.

We analyze the behavior of $M(\phi)$ under any plan $P$ consistent
with $P(\phi)$.  If $M_s$ under $P$ reaches state ``bad'', then
$M(\phi)$ under $P$ reaches a goal state with probability $1/2$.  Now,
consider a plan $P$ under which $M_s$ reaches the state
``good''---called a {\em good\/} plan.  Then $P$ matches the above
regular expression.  Therefore, for every $i\in\{1,\ldots,m\}$ there exists
$b_i\in\{-1,1\}$ such that all steps $s(i,b_i,h)$ are between \st\ and
\ch.  Thus, all steps between \ch\ and \ed\ are
$$
s(1,1-i_1,1) \cdots s(n,1-i_n,1)s(1,1-i_1,2) \cdots s(n,1-i_n,m)
$$
Consequently, the sequence of actions defined by 
the labeling of these plan steps
are 
$$
(\as(1,i_1) \as(2,i_2) \cdots \as(n,i_n))^m.
$$
This means, that $M_\phi$ checks whether all clauses of $\phi$ 
are satisfied by the assignment $i_1\cdots i_n$,
i.e., $M_{\phi}$ checks whether $i_1\cdots i_n$ satisfies $\phi$.
Therefore, $M(\phi)$ accepts under plan $P$ with probability $1$,
if the plan represents a satisfying assignment,
and with probability $0$ otherwise.

% Note that this construction makes use of the fact that each step of
% the p.o. plan V is used once and only once.  So after check the same
% assignment repeats m times.  (Very clever, Martin!)

Note that each assignment corresponds to exactly one good plan.
Therefore, the average over all good plans that $M(\phi)$ accepts
equals the fraction of satisfying assignments of $\phi$.  Since
$M(\phi)$ accepts under ``bad'' plans with probability $1/2$,
this yields that the average over all plans consistent with
$P(\phi)$ of the acceptance probabilities of $M(\phi)$ is greater
than $1/2$ if and only if $\phi\in\MAJSAT$.
\end{proof}

The complexity of the plan-existence problem for partially ordered
plans is identical to that for totally ordered plans.

\begin{theorem} \label{th:poexist}
The plan-existence problem for partially ordered plans in flat domains
is $\NP$-complete under the pessimistic, optimistic and average
interpretations.  
The plan-existence problem for partially ordered
plans in propositional domains is $\NPPP$-complete under the
pessimistic, optimistic and average interpretations.
\end{theorem}

\begin{proof}
First, note that a totally ordered plan is a special type of partially
ordered plan and its evaluation is unchanged under the pessimistic,
optimistic, or average interpretation.  In particular, because there
is only one ordering consistent with a given totally ordered plan, the
best, worst, and average orderings are all the same.  Therefore, if
there exists a totally ordered plan with value greater than $\theta$, then
there is a partially ordered plan with value greater than $\theta$ (the
same plan), under all three interpretations.

Conversely, if there is a partially ordered plan with value greater than
$\theta$ under any of the three interpretations, then there is a totally
ordered plan with value greater than $\theta$.  This is because the value
of the best, worst, and average ordering of a partially ordered plan
is always a lower bound on the value of the best consistent totally
ordered plan.

Given this strong equivalence, the complexity of plan existence for
partially ordered plans is a direct corollary of
Theorems~\ref{th:NP-complete} and~\ref{th:NPPP-complete}.
\end{proof}

The pattern for partially ordered plan evaluation in flat domains is
that the average interpretation is no easier to decide than either the
optimistic or pessimistic interpretations.  In propositional domains,
the pattern is the opposite: the average interpretation is no harder
to decide than either the optimistic or pessimistic interpretations.

\begin{theorem} \label{th:conppp}
The plan-evaluation problem for partially ordered plans in
propositional domains is $\NPPP$-complete under the optimistic
interpretation, $\coNPPP$-complete under the pessimistic interpretation,
and $\PP$-complete under the average interpretation.
\end{theorem}

\begin{sketch}
For the optimistic interpretation, membership in $\NPPP$ follows from
the fact that we can guess a single sufficiently good consistent total
order and evaluate it in $\PP$ (Theorem~\ref{th:PP-complete}).
Hardness for $\NPPP$ can be shown using a straightforward reduction
from \EMAJSAT\ (as in the proof of Theorem~\ref{th:NPPP-complete}).

For the pessimistic interpretation, membership in $\coNPPP$ follows
{from} the fact that we can guess the {\em worst\/} consistent total
order and evaluate it in $\PP$ (Theorem~\ref{th:PP-complete}).
Hardness for $\coNPPP$ can be shown by reducing to it the $\coNPPP$
version of \EMAJSAT\ ($\overline{\EMAJSAT}$); the proof is a simple
adaptation of the techniques used, for example, in
Theorem~\ref{th:NPPP-complete} above.

For the average interpretation, the problem can be shown to be in
$\PP$ by combining the argument in the proof of Theorem~\ref{th:open}
showing how to average over consistent totally ordered plans with the
argument in the proof of Theorem~\ref{th:PP-complete} showing how to
evaluate a plan in a propositional domain in $\PP$.  Alternatively, we
could express the evaluation of a partially ordered plan under the
average interpretation as a compact probabilistic acyclic plan;
Corollary~\ref{c:succinct-prob-plans} states that such plans can be
evaluated in $\PP$.  $\PP$-hardness follows directly from
Theorem~\ref{th:PP-complete}, because totally ordered plans are a
special case of partially ordered plans and evaluating totally ordered
plans is $\PP$-hard.
\end{sketch}

\section{Applications}
\label{s:applications}

To help illustrate the utility of our results, this section cites
several planners from the literature and analyzes the computational
complexity of the problems they attack.  We do not give detailed
explanations of the planners themselves; for this, we refer the reader
to the original papers.  We focus on three planning systems: {\sc
witness} (Brown University), {\sc buridan} (University of Washington),
and {\sc treeplan} (University of British Columbia).  In the process
of making connections to these planners, we also describe how our work
relates to the discounted-reward criterion, partial observability,
other domain representations, partial order conditional planning,
policy-based planning, and approximate planning.

\subsection{Witness}
\label{s:witness}

The {\sc witness} algorithm~\cite{cassandra94,kaelbling98} solves
flat partially observable Markov decision processes using a
dynamic-programming approach.  The basic algorithm finds optimal
unrestricted solutions to finite-horizon problems.
\namecite{papadimitriou87} showed that the plan-existence problem for
polynomial-horizon partially observable Markov decision processes is
$\PSPACE$-complete.

As an extension to their finite-horizon algorithm,
\namecite{kaelbling98} sketch a method for finding optimal looping
plans for some domains.  Although this is not presented as a formal
algorithm, it is not unreasonable to say that the pure form of
the problem that this extended version of {\sc witness} attacks is one
of finding a valid polynomial-size looping plan for a partially
observable domain.  The similarities between this problem and that
described in Section~\ref{s:looping} are that the domains are flat and
that the plans are identical in form.  The apparent differences are
that {\sc witness} optimizes a reward function instead of probability
of goal satisfaction and that {\sc witness} works in partially
observable domains whereas our results are defined in terms of
completely observable domains.  Both of these apparent differences are
insignificant, however, from a computational complexity point of view.

First, {\sc witness} attempts to maximize the expected total
discounted reward over an infinite horizon (sometimes called
optimizing a time-separable value function).  As argued by
\namecite{condon92}, any problem defined in terms of a sum of
discounted rewards can be recast as one of goal satisfaction.  The
argument proceeds roughly as follows.  Let $0 < \gamma < 1$ be the
discount factor and $R(s,a)$ be the immediate reward received for
taking action $a$ in state $s$.

Define
$$R'(s,a) = \frac{R(s,a) - \min_{s',a'} R(s',a')} 
			{\max_{s',a'} R(s',a') - \min_{s',a'} R(s',a')}.$$
%
From this, we have that $0\le R'(s,a) \le 1$ for all $s$ and
$a$ and that the value of any plan with respect to the revised reward
function is a simple linear transformation of its true value.  Now, we
% \nu = \sum_{t=0}^\infty \gamma^t R(s_t,a_t)
% \sum_{t=0}^\infty \gamma^t R'(s_t,a_t)
%  = \sum_{t=0}^\infty \gamma^t \gamma \frac{R(s,a) - \min_{s',a'} R(s',a')} 
% 			{\max_{s',a'} R(s',a') - \min_{s',a'} R(s',a')}
%  = 1/(\max_{s',a'} R(s',a') - \min_{s',a'} R(s',a')) 
% 	\sum_{t=0}^\infty \gamma^t \gamma (R(s,a) - \min_{s',a'} R(s',a'))
%  = 1/(\max_{s',a'} R(s',a') - \min_{s',a'} R(s',a')) 
% 	\sum_{t=0}^\infty \gamma^t \gamma R(s,a) 
% 	- \sum_{t=0}^\infty \gamma^t \gamma \min_{s',a'} R(s',a'))
%  = 1/(\max_{s',a'} R(s',a') - \min_{s',a'} R(s',a')) 
% 	\sum_{t=0}^\infty \gamma^t \gamma R(s,a) 
% 	- \sum_{t=0}^\infty \gamma^t \gamma \min_{s',a'} R(s',a'))
%  = c_1 \gamma \nu - c_2
introduce an auxiliary state $g$ to be the goal state and create a new
transition function $t'$ such that $t'(s,a,g) = (1-\gamma)R'(s,a)$ and
$t'(s,a,s') = (1-(1-\gamma)R'(s,a))t(s,a,s')$ for $s' \neq g$; $t'$ is
a well-defined transition function and 
% sum_s' U g t'(s,a,s') 
% = sum_s' t'(s,a,s') + t'(s,a,g)
% = sum_s' (1-R'(s,a))t(s,a,s') + R'(s,a)
% = sum_s' (t(s,a,s')-t(s,a,s')R'(s,a)) + R'(s,a)
% = sum_s' t(s,a,s')-sum_s' t(s,a,s')R'(s,a) + R'(s,a)
% = 1 - R'(s,a) + R'(s,a) = 1
the probability of goal satisfaction for any plan under
transition function $t'$ is precisely the same as the expected total
discounted reward under reward function $R'$ and transition function
$t$.  Thus, any problem stated as one of optimizing the expected total
of discounted immediate rewards can be turned into an equivalent
problem of optimizing goal satisfaction with only a slight change to
the transition function and one additional state.  This means there is
no fundamental computational complexity difference between these two
different types of planning objectives.

The second apparent difference between the problem solved by the
extended {\sc witness} algorithm and that described in
Section~\ref{s:looping} is that of partial versus complete
observability.  In fact, our results do address partial observability,
albeit indirectly.
% Notice that the results presented here apply unchanged to partially
% observable domains.
In our formulation of the plan-existence problem, plans are
constrained to make no conditional branches (in the totally ordered
and partially ordered cases), or to branch only on distinctions made
by the step-transition function $\delta$ (in the acyclic and looping
cases); these two choices correspond to unobservable and partially
observable domains, respectively.  In a partially observable domain,
the plan-existence problem becomes one of finding a valid
polynomial-size finite-state controller subject to the given
observability constraints.  Nothing in our complexity proofs depends
on the presence or absence of additional observability constraints.
Therefore, it is a direct corollary of Theorem~\ref{th:NP-complete}
that the plan-existence problem for polynomial-horizon plans in
unobservable domains is $\NP$-complete~\cite{papadimitriou87} and of
Theorem~\ref{th:loop} that the plan-existence problem for
polynomial-size looping plans in partially observable domains is
$\NP$-complete (this is a new result).

It is interesting to note that the computational complexity of
searching for size-bounded plans in partially observable domains is
generally substantially less than that of solving the corresponding
unconstrained partially observable Markov decision process.  For
example, we found that the plan-existence problem for acyclic plans in
propositional domains is $\NPPP$-complete
(Theorem~\ref{th:NPPP-complete}).  The corresponding unconstrained
problem is that of determining the existence of a history-dependent
policy for a polynomial-horizon, compactly represented partially
observable Markov decision process, which is $\EXPSPACE$-complete
(Theorem~4.15 of \namecitenoparens{goldsmith96}, or Theorem~6.8 of
\namecitenoparens{mundhenk97b}).  The gap here is enormous: $\EXPSPACE$ is to
$\EXPTIME$ what $\PSPACE$ is to $\PTIME$, and $\EXPTIME$ is already
provably intractable in the worst case.  In contrast to
$\EXPSPACE$-complete problems, it is conceivable that good heuristics
for $\NPPP$-complete problems can be created by extensions of recent
advances in heuristics for $\NP$-complete problems.  Therefore, there
is some hope of devising effective planning algorithms by building on
the observations in this paper and searching for optimal size-bounded
plans instead of optimal unrestricted plans; in fact, recent planners
for both propositional domains~\cite{majercik97b,majercik98b} and
flat domains~\cite{hansen98b} are motivated by these results.

Table~\ref{t:po} summarizes complexity results for planning in
partially observable domains.  The results for size-bounded plans are
corollaries of Theorems~\ref{th:NP-complete}, \ref{th:NPPP-complete},
\ref{th:loop}, and \ref{th:PSPACE-complete2} of this paper.  The
results for unrestricted plans are due to \namecite{papadimitriou87}
(flat, polynomial), \namecite{goldsmith96} (propositional,
polynomial), and \namecite{hanks96} (infinite-horizon).  This last
result is derived by noting the isomorphism of the infinite-horizon
problem to the emptiness problem for probabilistic finite-state
automata, which is undecidable~\cite{rabin63}.

\begin{table}
\centerline{
\begin{tabular}{|ll|ll|}
\hline
Domain Type &  Horizon Type        & {\bf Size-Bounded Plan} & {\bf Unrestricted Plan} \\
\hline
flat          &	polynomial & $\NP$-complete%(Theorem~\ref{th:NP-complete})
			   & $\PSPACE$-complete%~\cite{papadimitriou87}	
\\
propositional &	polynomial &$\NPPP$-complete%(Theorem~\ref{th:NPPP-complete})
			   & $\EXPSPACE$-complete%~\cite{goldsmith96}
\\
flat &		infinite   & $\NP$-complete% (Theorem~\ref{th:loop})\\
			   & undecidable%~\cite{hanks96}
\\
propositional &	infinite   & $\PSPACE$-complete% \ref{th:PSPACE-complete2})\\
			   & undecidable%~\cite{hanks96}
\\
\hline 
\end{tabular}
}
\tablecaption{Complexity results for plan existence in partially
observable domains}
\label{t:po}
\end{table}


\subsection{Buridan}

The {\sc buridan} planner~\cite{kushmerick95} finds partially ordered
plans for propositional domains in the PSO representation.  There are
two identifiable differences between the problem solved by {\sc
buridan} and the problem analyzed in Section~\ref{s:po}: the
representation of planning problems and the fact that {\sc buridan} is
not restricted to find polynomial-size plans.  We address each of
these differences below.

Although, on the surface, PSO is different from ST, either can be
converted into the other in polynomial time with at most a polynomial
increase in domain size.  In particular, the effect of an action in
PSO is represented by a single decision tree consisting of proposition
nodes (like ST) and random nodes (easily simulated in ST using
auxiliary propositions).  At the leaves are a list of propositions
that become true and another list of propositions that become false
should that leaf be reached.  This type of correlated effect is also
easily represented in ST using the chain rule of probability theory to
decompose the probability distribution into separate probabilities for
each proposition and careful use of the ``{\bf :new}'' suffix.  Thus,
any PSO domain can be converted to a similar size ST domain quickly.

Similarly, a domain in ST can be converted to PSO with at most a
polynomial expansion.  This conversion is too complex to sketch here,
but follows from the proof of equivalence between ST and a simplified
representation called IF~\cite{littman97b}.  Given the polynomial
equivalence between ST and PSO, any complexity results for ST carry
over to PSO.\footnote{To be more precise, this is true for complexity
classes closed under log-space reductions.}

The results described in this paper concern planning problems in which
a bound is given on the size of the plan sought.  Although
\namecite{kushmerick95} do not explicitly describe their planner as
one that prefers small plans to large plans, the design of the planner
as one that searches through the space of plans makes the notion of
plan size central to the algorithm.  Indeed, the public-domain {\sc
buridan} implementation uses plan size as part of a best-first search
procedure for identifying a sufficiently successful plan.  This means
that, all other things being equal, shorter plans will be found before
larger plans.  Furthermore, to assure termination, the planner only
considers a fixed number of plans before halting, thus putting a limit
indirectly on the maximum allowable plan size.  So, although {\sc
buridan} does not attempt to solve precisely the same problem that we
considered, it is fair to say that the problem we consider is an
idealization of the problem attacked by {\sc buridan}.  Regardless,
our lower bounds on complexity apply to {\sc buridan}.

% from the buridan code:
% (defun RANK-default (plan)
%   ;; the standard ranking function, carried over directly from SNLP
%  (let ((steps (length (plan-steps plan)))
%        (unsafe (length (plan-unsafe plan)))
%        (open (length (plan-open plan)))
%	(links (length (plan-links plan))))
%    (+ unsafe open steps links)))

\namecite{kushmerick95} looked at generating sufficiently successful
plans under both the optimistic interpretation and the pessimistic
interpretation.  They also explicitly examined the plan-evaluation
problem for partially ordered plans under both interpretations.
Therefore, Theorems~\ref{th:poexist} and~\ref{th:conppp} apply to {\sc
buridan}.
% zzz clunky with previous paragraph.

The more sophisticated {\sc c-buridan} planner~\cite{draper94} extends
{\sc buridan} to plan in partially observable domains and to produce
plans with conditional execution.  The results of our work also shed
light on the computational complexity of the problem addressed by {\sc
c-buridan}.  \namecite{draper94} devised a representation for
partially ordered acyclic (conditional) plans.  In this
representation, each plan step generates an {\em observation label\/}
as a function of the probabilistic outcome of the step.  Each step
also has an associated set of {\em context labels\/} dictating the
circumstances under which that step must be executed.  A plan step is
executed only if its context labels are consistent with the
observation labels produced in earlier steps.  In its totally ordered
form, this type of plan can be expressed as a compact acyclic plan;
Corollary~\ref{c:succinct-prob-plans} can be used to show that the
plan-evaluation and plan-existence problems for a totally ordered
version of {\sc c-buridan}'s conditional plan representation in
propositional domains are $\PP$-complete and $\NPPP$-complete,
respectively.

In our results above, we consider evaluating and searching for plans
that are partially ordered and plans that have conditional execution,
but not both at once.  Nonetheless, the same sorts of techniques
presented in this paper can be applied to analyzing the problems
attacked by {\sc c-buridan}.  For example, consider the plan-existence
problem for {\sc c-buridan}'s partially ordered conditional plans
under the optimistic interpretation.  This problem asks whether there
is a partially ordered conditional plan that has some total order that
reaches the goal with sufficient probability.  This is equivalent to
asking whether there is a totally ordered conditional plan that
reaches the goal with sufficient probability.  Therefore, the problem
is $\NPPP$-complete, by the argument in the previous paragraph.

% easy to argue this is nppp complete?  Not clear.  ought to be that
% evaluation is nppp, pp, conppp

In spite of many superficial differences between the problems analyzed
in this paper and those studied by the creators of the {\sc buridan}
planners, our results are quite relevant to understanding their work.

\subsection{Treeplan}

A family of planners have been designed that generate a
decision-tree-based representation of stationary policies (mappings
from state to action)~\cite{Boutilier95,boutilier96b,boutilier96} in
probabilistic propositional domains; we refer to these planners
collectively as the {\sc treeplan} planners.  Once again, these
planners solve problems that are not identical to the problems
addressed in this paper but are closely related.

The planner described by \namecite{Boutilier95} finds solutions that
maximize expected total discounted reward in compactly represented
Markov decision processes (the domain representation used is
expressively equivalent to ST).  As mentioned earlier, the difference
between maximizing goal satisfaction and maximizing expected total
discounted reward is a superficial one, so the problem addressed by
this planner is $\EXPTIME$-complete~\cite{littman97b}.  Although the
policies used by \namecite{Boutilier95} appears quite dissimilar from
the finite-state controllers described in our work, policies can be
converted to a type of similarly sized compact {\em looping\/} plan
(an extension of the type of plan described in
Corollary~\ref{c:succinct-prob-plans}).  The conversion from
stationary policies to looping plans is as described in the proof of
Theorem~\ref{th:loop}, except that the resulting plans are represented
compactly.

In later work, \namecite{boutilier96} show how it is possible to limit
the size of the representation of the policy in {\sc treeplan} and
still obtain approximately optimal performance.  This is necessary
because, in general, the size of decision trees needed to represent
the optimal policies can be exponentially large.  By keeping the
decision trees from getting too large, the resulting planner becomes
subject to an extension of Theorem~\ref{th:PSPACE-complete2} and,
therefore, attacks a $\PSPACE$-complete problem.

One emphasis of \namecite{boutilier96} is on finding approximately
optimal solutions, with the hope that doing so is easier than finding
optimal solutions.  We do not explore the worst-case complexity of
approximation in this paper, although \namecite{lusena98} have
produced some strong negative results in this area.  A related issue
is one of using simulation (random sampling) to find approximately
optimal solutions to probabilistic planning problems.  Some empirical
successes have been obtained with the related approach of
reinforcement learning~\cite{tesauro94,crites96}, but, once again, the
worst-case complexity of probabilistic planning is not known to be any
lower for approximation by simulation.

% \cite{dearden97}


% Other important plan structures to which our results can be applied
% include universal plans or policies~\cite{dearden97} and parallel
% plans~\cite{blum97}.

% UBC: not goal oriented problems.  not restricted to small plans.
%  need to check source papers for how the problems are described.
%  what cutoff was used in the approximation paper boutilier96?

% plinth and tree-structured plans?
% evaluation of tree-structured plans: in P, finding one is in NP^P =
% NP and is NP-hard because even deterministic domains are NP-hard.

\section{Conclusions}

In this paper, we explored the computational complexity of plan
evaluation and plan existence in probabilistic domains.  We found
that, in compactly represented propositional domains, restricting the
size and form of the policies under consideration reduced the
computational complexity of plan existence from $\EXPTIME$-complete
for unrestricted plans to $\PSPACE$-complete for polynomial-size
looping plans and $\NPPP$-complete for polynomial-size acyclic plans.
In contrast, in flat domains, restricting the form of the policies
under consideration {\em increased\/} the computational complexity of
plan existence from $\PTIME$-complete for unrestricted plans to
$\NP$-complete for totally ordered plans; this is because a plan that
is smaller than the domain in which it operates is often unable to
exploit important Markov properties of the domain.  We were able to
characterize precisely the complexity of all problems we examined with
regard to the current state of knowledge in complexity theory.

Several problems we studied turned out to be $\NPPP$-complete.  The
class $\NPPP$ promises to be very useful to researchers in uncertainty
in artificial intelligence because it captures the type of problems
resulting from choosing (``guessing'') a solution and then evaluating
its probabilistic behavior.  This is precisely the type of problem
faced by planning algorithms in probabilistic domains, and captures
important problems in other domains as well, such as constructing
explanations in belief networks and designing robust communication
networks.  We provide a new conceptually simple $\NPPP$-complete
problem, \EMAJSAT, that may be useful in further explorations in this
direction.

The basic structure of our results is that if plan evaluation is
complete for some class $\cC$, then plan existence is typically
$\NP\ora{\cC}$-complete.  This same basic structure holds in
deterministic domains: evaluating a totally ordered plan in a
propositional domain is $\PTIME$-complete (for sufficiently powerful
domain representations) and determining the existence of a
polynomial-size totally ordered plan is
$\NP\ora{\PTIME}=\NP$-complete.

{From} a pragmatic standpoint, the intuition that searching for small
plans is more efficient than searching for arbitrary size plans
suggests that exact dynamic-programming algorithms, which are so
successful in flat domains, may not be as effective in propositional
domains; they do not focus their efforts on the set of small plans.
Algorithm-development energy, therefore, might fruitfully be spent
devising heuristics for problems in the class $\NPPP$ as this class
captures the essence of searching for small plans in probabilistic
domains---some early results in this direction are
appearing~\cite{majercik97b,majercik98b}.  Complexity theorists have
only recently begun to explore classes such as $\NPPP$ that lie
between the polynomial hierarchy and $\PSPACE$ and algorithm designers
have come to these classes even more recently.  As this paper marks
the beginning of our exploration of this class of problems, much work
is still to be done in probing algorithmic implications, but it is our
hope that heuristics for $\NPPP$ could lead to powerful methods for
solving a range of important uncertainty-sensitive combinatorial
problems.

\acks{This work was supported in part by grants
NSF-IRI-97-02576-CAREER (Littman), and NSF CCR-9315354 (Goldsmith).
We gratefully acknowledge Andrew Klapper, Anne Condon, Matthew Levy,
Steve Majercik, Chris Lusena, Mark Peot, and our reviewers for helpful
feedback and conversations on this topic.}

\appendix

\section{Complexity of \EMAJSAT}

The \EMAJSAT\ problem is: given a pair $(\phi,k)$
consisting of a Boolean formula $\phi$ of $n$
variables $x_1,\ldots,x_n$ and a number $1\le k\le n$, is there an
assignment to the first $k$ variables $x_1,\ldots,x_k$  such that the
majority of assignments to the remaining $n-k$ variables
$x_{k+1},\ldots, x_n$ satisfies $\phi$?

For $k=n$, this is precisely Boolean satisfiability, a classic
$\NP$-complete problem.  This is because we are asking whether there 
exists an assignment to {\em all\/} the variables that makes $\phi$
true.  For $k=0$, \EMAJSAT\ is precisely \MAJSAT, a well-known
$\PP$-complete problem.  This is because we are asking whether the
majority of all {\em total\/} assignments makes $\phi$ true.

Deciding an instance of \EMAJSAT\ for intermediate values of $k$ has a
different character.  It involves both an $\NP$-type calculation to
pick a good setting for the first $k$ variables and a $\PP$-type
calculation to see if the majority of assignments to the remaining
variables makes $\phi$ true.  This is akin to searching for a good
answer (plan, schedule, coloring, belief network explanation, etc.) in
a combinatorial space when ``good'' is determined by a computation
over probabilistic quantities.  This is just the type of computation
described by the class $\NPPP$, and we show next that \EMAJSAT\ is
$\NPPP$-complete.

\begin{theorem}\label{th:EMajsat}
\EMAJSAT\ is $\NPPP$-complete.
\end{theorem}

\begin{proof}
Membership in $\NPPP$ follows directly from definitions.  To show
completeness of \EMAJSAT, we first observe~\cite{toran91} that $\NPPP$
is the $\leq_m^{\NP}$-closure of the $\PP$-complete set $\MAJSAT$.
Thus, any $\NPPP$ computation can be modeled by a nondeterministic
machine $N$ that, on each possible computation, first guesses a
sequence $s$ of bits that controls its nondeterministic moves,
deterministically performs some computation on input $x$ and $s$, and
then writes down a formula $q_{x,s}$ with variables in
$z_1,\ldots,z_l$ as a query to $\MAJSAT$.  Finally, $N(x)$ with oracle
$\MAJSAT$ accepts if and only if for some $s$, $q_{x,s}\in\MAJSAT$.

Given any input $x$, like in Cook's Theorem, we can construct a
formula $\phi_x$ with variables $y_1,\ldots,y_k$ and $z_1,\ldots,z_l$
such that for every assignment $a_1,\ldots,a_k,b_1,\ldots,b_l$ it
holds that 
$\phi_x(a_1,\ldots,a_k,b_1,\ldots,b_l)=q_{x,a_1\cdots
a_k}(b_1,\ldots,b_l)$.  Thus, $(\phi_{x},k)\in\EMAJSAT$ if and only if
for some assignment $s$ to $y_1,\ldots,y_k$, $q_{x,s}\in \MAJSAT$ if
and only if $N(x)$ accepts.
\end{proof}


\ifthenelse{\boolean{nofigures}}
{ }
{
\bibliography{mlittman}
}

\end{document}
