\documentstyle[jair,twoside,11pt,theapa,latexsym,amsmath,amssymb,amsfonts,theorem,float,array,graphicx,eufrak,multirow,enumerate]{article}

\input epsf
\input xy
\xyoption{all}



%%%----------------------------
\def\defemb#1#2{\expandafter\def\csname #1\endcsname
                              {\relax\ifmmode #2\else\hbox{$#2$}\fi}}
\defemb{cA}{{\cal A}}
\defemb{cB}{{\cal B}}
\defemb{cC}{{\cal C}}
\defemb{cc}{{\cal c}}
\defemb{cD}{{\cal D}}
\defemb{cE}{{\cal E}}
\defemb{cF}{{\cal F}}
\defemb{cf}{{\cal f}}

\defemb{cG}{{\cal G}}
\defemb{GG}{{\cal G}}

\defemb{cI}{{\cal I}}
\defemb{cK}{{\cal K}}
\defemb{cP}{{\cal P}}
\defemb{cL}{{\cal L}}
\defemb{cN}{{\cal N}}
\defemb{cM}{{\cal M}}
\defemb{cR}{{\cal R}}

\defemb{cS}{{\cal S}}
\defemb{SS}{{\cal S}}

\defemb{cT}{{\cal T}}
\defemb{cV}{{\cal V}}
\defemb{cU}{{\cal U}}
\defemb{cO}{{\cal O}}
\defemb{cH}{{\cal H}}
\defemb{cX}{{\cal X}}
\defemb{cY}{{\cal Y}}
\defemb{cZ}{{\cal Z}}

\defemb{sP}{{\sf P}}
\defemb{sG}{{\sf G}}
\defemb{sU}{{\sf U}}
\defemb{sE}{{\sf E}}
\defemb{sI}{{\sf I}}
\defemb{su}{{\sf u}}
\defemb{se}{{\sf e}}
\defemb{ss}{{\sf s}}
\defemb{st}{{\sf t}}
\defemb{sp}{{\sf p}}
\defemb{si}{{\sf i}}
\defemb{sb}{{\sf b}}
\defemb{sw}{{\sf w}}
\defemb{sA}{{\sf A}}
\defemb{sB}{{\sf B}}
\defemb{sa}{{\sf a}}
\defemb{sb}{{\sf b}}
\defemb{scc}{{\sf c}}
\defemb{sd}{{\sf d}}



\defemb{tta}{{\tt a}}
\defemb{ttb}{{\tt b}}
\defemb{ttc}{{\tt c}}
\defemb{ttd}{{\tt d}}
\defemb{tte}{{\tt e}}
\defemb{ttf}{{\tt f}}

\defemb{bara}{{\bar{a}}}
\defemb{barb}{{\bar{b}}}
\defemb{barc}{{\bar{c}}}
\defemb{barf}{{\bar{f}}}
\defemb{barv}{{\bar{v}}}

\newcommand{\toadd}[1]{
  {\footnotesize
  \begin{center}
  \fbox{
    \begin{minipage}{3in}
      carmel:\\ #1
    \end{minipage}    
    }
  \end{center}
  }
}


\newcommand{\scite}{\citeyear}
\newcommand{\commentout}[1]{}
\newcommand{\journal}[1]{}
\newcommand{\conference}[1]{#1}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}

\newenvironment{proof}{\noindent {\bf Proof:}~~}{\ 
$\square$\vspace{0.5cm}}
\newenvironment{nproof}[1]{\setlength{\parindent}{0in}{\bf Proof (#1)}~~}{\\ 
$\blacksquare$}
\newenvironment{sproof}{\noindent {\bf Proof sketch:}~~}{\ 
$\blacksquare$\vspace{0.5cm}}
\newenvironment{snproof}[1]{\setlength{\parindent}{0in}{\bf Sketch of the 
proof (#1)}~~}{\\}
\newenvironment{ssproof}{\setlength{\parindent}{0in}{\bf Proof
    sketch.}~~}{}

\newenvironment{atheorem}[1]{{\vspace{0.4cm}\noindent\bf Theorem~\ref{#1}}~~}
                            {\\}
\newenvironment{alemma}[1]{{\vspace{0.4cm}\noindent\bf Lemma~\ref{#1}}~~}
                            {\\}


\newcommand{\sset}[1]{
  \left\{ \begin{array}{l}#1\end{array} \right.}


%% Planning
%% --------
\newcommand{\strips}{\textsc{strips}}

\newcommand{\pre}{{\mathsf{pre}}}
\newcommand{\post}{{\mathsf{post}}}
\newcommand{\prv}{{\mathsf{prv}}}

\newcommand{\parents}{{\mathsf{pred}}}
\newcommand{\sons}{{\mathsf{succ}}}
\newcommand{\lparents}{pred}
\newcommand{\lsons}{succ}
% \newcommand{\parents}{\mathsf{Parents}}
% \newcommand{\sons}{\mathsf{Sons}}
% \newcommand{\lparents}{Parents}
% \newcommand{\lsons}{Sons}
\newcommand{\plans}{{\mathbf\Pi}}

\newcommand{\Can}{{\mathsf{MaxPoss}}}
\newcommand{\newCan}{{\mathsf{newMaxPoss}}}
\newcommand{\FeasibleMust}{{\mathsf{FMaxReq}}}
\newcommand{\Must}{{\mathsf{MaxReq}}}
\newcommand{\LocalMust}{{\mathsf{Req}}}
\newcommand{\newMust}{{\mathsf{newMaxReq}}}
\newcommand{\minplan}{{\mathsf{MinPlanSize}}}
\newcommand{\maxplan}{{\mathsf{MaxPlanSize}}}


\newcommand{\val}{\vartheta}
\newcommand{\POP}{{\sc pop-pcg}}

\def\nat{{\mathbb N}}
\newcommand{\var}{\upsilon}


%\jairheading{1}{1993}{1-15}{6/91}{9/91}
\jairheading{18}{2003}{315-349}{10/02}{4/03}
\ShortHeadings{Structure and Complexity in Planning with Unary Operators}
{Brafman \& Domshlak}
\firstpageno{315}

\begin{document}

\title{Structure and Complexity in Planning with
       Unary Operators}
\author{\name  Ronen I. Brafman \email brafman@cs.bgu.ac.il \\
  \name Carmel Domshlak \email  dcarmel@cs.bgu.ac.il\\
       \addr Department of Computer Science\\
       Ben-Gurion University\\
       P.O. Box 653, 84105 Beer-Sheva, Israel}
     
\date{}

\maketitle

\begin{abstract}
  Unary operator domains -- i.e., domains in which operators have a single
  effect -- arise naturally in many control problems.  In its most general
  form, the problem of \strips\ planning in unary operator domains is known to
  be as hard as the general \strips\ planning problem -- both are {\sc
    pspace}-complete. However, unary operator domains induce a natural
  structure, called the domain's {\em causal graph\/}. This graph relates
  between the preconditions and effect of each domain operator. Causal graphs
  were exploited by Williams and Nayak in order to analyze plan generation for
  one of the controllers in NASA's Deep-Space One spacecraft. There, they
  utilized the fact that when this graph is acyclic, a serialization ordering
  over any subgoal can be obtained quickly. In this paper we conduct a
  comprehensive study of the relationship between the structure of a domain's
  causal graph and the complexity of planning in this domain.  On the positive
  side, we show that a non-trivial polynomial time plan generation algorithm
  exists for domains whose causal graph induces a polytree with a constant
  bound on its node indegree. On the negative side, we show that even plan
  existence is hard when the graph is a directed-path singly connected DAG.
  More generally, we show that the number of paths in the causal graph is
  closely related to the complexity of planning in the associated domain.
  Finally we relate our results to the question of complexity of planning with
  serializable subgoals.
\end{abstract}

\section{Introduction}
\label{S:intro}
One of the first well formulated problems addressed by AI researchers was
the planning problem. Simply stated, it involves the generation of a
sequence of system transformations, taken out of a given set of system
transformations (called {\em actions\/} or {\em plan operators\/}), whose
combined effect is to move the system from some given initial state into
one of a set of desired goal states.  The planning problem is known to be
intractable in general~\cite{Chapman:ai87}, and tractable algorithms exist
for very restrictive classes of problems only. This discouraging fact has
not deterred planning researchers. Indeed, many researchers believe that
real-world problems have some properties, or {\em structure\/}, that could
be exploited, either implicitly or explicitly.  In this paper we attempt to
understand the relationship between structure and complexity in planning
problems in which each action changes the value of a single variable.

To study the relation between the structure and the complexity in a class
of problems we must identify a set of parameters that characterize it.
In the case of planning, a number of such problem properties  %structural properties
have been
studied in the past (which we review in more detail in Section~\ref{S:related}).
These properties have been mostly syntactical, i.e., they involve
restriction on %the structure of
operators, e.g., the type and number of
preconditions or effects that operators have.
% Generating plans in the context of the \strips\ representation
% language is known to be a difficult (P-SPACE complete) problem
% \cite{Bylander.AI.94}. Thus, various authors have explored the
% existence of more constrained problem classes for which planning is
% easier.  
For example, Bylander~\scite{Bylander.AI.94} showed that \strips\ planning in
domains where each operator is restricted to have positive
preconditions and one postcondition only is tractable.
B{\"a}ckstr{\"o}m and Klein~\scite{Backstrom:Klein:ci91} considered
other, more global types of syntactical restrictions, but using a more refined model in
which two types of preconditions are considered: {\em prevail\/}
conditions, which are variable values that are required prior to the
execution of the operator and are not affected by the operator, and
{\em preconditions\/}, which {\em are\/} affected by the operator.
For example, they have shown that when
operators have a single effect, no two operators have the same effect,
and each variable can be affected only in one context (of prevail
conditions) then the planning problem can be solved in polynomial
time. However, these restrictions are very strict, and it is
difficult to find reasonable domains satisfying them.

In this paper we concentrate on more global properties of unary
operator domains; properties that capture some of the interactions
between different planning operators. The tool we use to study these
properties is the domains' {\em causal graph\/}.  A causal graph is a
directed graph whose nodes stand for the domain propositions. An edge
$(p,q)$ appears in the causal graph if and only if some operator that
changes the value of $q$ has a prevail condition involving $p$. Such a
problem structure was introduced by Knoblock~\scite{Knoblock:aij94} in
the context of automatically generating abstractions for planning.
Subsequently, Jonsson and
B{\"a}ckstr{\"o}m~\scite{Jonsson:Backstrom:amai98} introduced the 3S
class of planning problems with unary operators, which was
characterized by the acyclicity of the causal graph, and some
restrictions on the operator set. It was shown that determining plan
existence for this class of problems is polynomial, while plan
generation is provably intractable.

% More recently, Williams and Nayak~\scite{Williams:Nayak:IJCAI97}
% studied planning problems where all operators affect a single
% variable, in the context of their work on controlling NASA's
% Deep-Space One spacecraft. In this context, they 
% % defined 
% exploited the notion of a {\em causal graph\/} which relates the
% causal structure of the problem, i.e., how different variables play a
% role in our ability to affect other variables. A causal graph is a
% directed graph whose nodes are the domain propositions. An edge
% $(p,q)$ appears in the causal graph if some operator that changes the
% value of $q$ has a prevail condition involving $p$. This problem
% structure was introduced by Knoblock~\scite{Knoblock:aij94} in the
% context of automatic generating abstractions for planning.
% Subsequently, in~\cite{Jonsson:Backstrom:amai98}, Jonsson and
% B{\"a}ckstr{\"o}m introduced the 3S class of planning problems with
% unary operators, which was characterized by the acyclicity of the
% causal graph, and some restrictions on the operator set. It was shown 
% that determining plan existence for this class of problems is
% polynomial, while plan generation is provably intractable.


% When the causal
% graph is a tree, it is easy to determine a serializability ordering
% over any set of sub-goals, and consequently, obtain a plan in
% polynomial time.

Complexity results for unary operators would be of theoretical
interest alone if one could not supply interesting problems in which
unary operators are used. One interesting application in which this
problem arises is the determination of dominance relationship between
different outcomes in a CP-net~\cite{BBHP.UAI99}.  This problem is
reducible to \strips\ planning with unary operators.

Another example, of greater interest to the planning community, is a
planning-based reactive control system that commands the NASA Deep
Space One autonomous
spacecraft~\cite{DSO:97,Williams:Nayak:AAAI96,Williams:Nayak:IJCAI97}.
This system was hailed by Weld~\scite{Weld:aimag99} in his recent
survey of AI planning as one of the most exciting recent developments
in the area of planning. Naturally, the complete system~\cite{DSO:97}
is very complex, however, its configuration planning and execution
subsystem are of particular interest to us.  In the context of
controlling Deep-Space One, Williams and
Nayak~\scite{Williams:Nayak:AAAI96,Williams:Nayak:IJCAI97} present a
reactive planner, Burton, that generates a single control action for
the main engine subsystem of the spacecraft, and compensates for
anomalies at every step. Given a high-level goal (for example, thrust
in one of the engines), Burton continually tries to transition the
system toward a state that satisfies the desired goal. What is
particularly relevant for us is that Burton's task can be described as
a \strips\ planning problem in which each operator affects only a {\em
  single\/} variable (hardware component) -- Williams and
Nayak~\scite{Williams:Nayak:IJCAI97} argue that in physical hardware
it is usually the case that each state variable is commanded
separately.  However, Burton is based on two additional important
restrictions: First, the planner is explicitly supplied with a
serialization order for any satisfiable set of goal. Second, all
operators must be reversible.


% An important byproduct of Williams and Nayak's work is its demonstration
% that unary operator domains are of practical interest, since they arise naturally
% in many control problems. Interestingly, unary operator
% domains show up naturally in another application -- answering dominance
% queries in CP-networks \cite{BBHP.UAI99}.
One of the reasons cited for designing Burton as a reactive planner
that generates a single action at a time was the potential
intractability of generating whole plans. Indeed, Williams and Nayak
were pessimistic about the prospects of generating whole plans
quickly even for Burton, i.e., for problem instances with serializable
sub-goals and single-effect operators. As our results show, this
pessimism was not fully justified. 

Our work continues the study of planning with unary operators.
This apparently easier problem is in fact as hard as the
general \strips\ planning problem~\cite{Bylander.AI.94}. However, we
can obtain finer distinctions and some positive results if we pay
closer attention to the causal structure of the domain. 
For example, it is easy to show that
when the causal graph is a tree, it is
easy to determine a serializability ordering over any set of
sub-goals, and consequently, obtain a plan in polynomial time.
In this paper we analyze the relationship between the
domain's causal graph and the complexity of plan generation and plan
existence.  In particular we prove the following results:
\begin{itemize}
\item When the causal graph forms a polytree (the induced undirected graph is
  acyclic), and its node indegree is bounded by a constant, then plan existence
  and plan generation are polynomial.
  
\item When the causal graph is directed-path singly connected (there is at most
  one directed path between any pair of nodes), then plan existence is {\sc
    np}-complete.
  
%\item When the causal graph is a general DAG, plan generation is provably
%  intractable, i.e., the problem requires exponential time.
  
\item In general, plan generation for the problems with acyclic causal
  graphs is provably intractable, i.e., the problem requires
  exponential time. The corresponding claim is derived from a previous
  result by Jonsson and
  B{\"a}ckstr{\"o}m~\scite{Jonsson:Backstrom:amai98}. However, we show
  that the complexity of plan generation for these problems can be
  bounded by a function of the number of paths within the causal
  graph.
\end{itemize}
% NEW-JAIR
Note that the complexity of the problems with polytree causal graphs but with
unbounded node indegree remains an open problem -- it is still to be shown
whether they can be solved in polynomial time, or they are {\sc np}-complete.
% end NEW-JAIR

Finally, we relate our results to an old open question: how difficult
is it to generate plans for problems with \emph{serializable
  subgoals}~\cite{Korf.AI.87}?  This question was stated by
Bylander~\scite{Bylander.AAAI.92}, and different hypotheses were
raised by different researchers. Here, we present a clear, though
somewhat disappointing answer:
% NEW-JAIR
First, our results suggest that even when the underlying causal graph of the
problem is acyclic (and thus the problem is known to be serializable), finding a
serialization ordering on the problem subgoals may be hard. Second, we show
that even if the actual serialization ordering on the subgoals is known,
solving the problem is not necessarily easy.
% end NEW-JAIR

The rest of this paper is organized as follows: In Section~\ref{S:back} we
first introduce some basic formalism used in the paper, then discuss, motivate
and illustrate the notion of causal graph.  In Sections~\ref{S:upolytree}
and~\ref{S:polytree} we present our results on the relation between the form of
the causal graph and the complexity of the planning problem.  In
Section~\ref{S:serial} we discuss the sub-goal serializability issue and the
impact of our results on it.  In Section~\ref{S:related} we describe some
related work on complexity of planning, and connect our work with the previous
results.  We summarize in Section~\ref{S:summary}. Finally,
Appendix~\ref{app:pop} provides a short review of the POP
algorithm~\cite{Penberthy:Weld:KR92}, and Appendix~\ref{app:proofs} provides
some of the proofs.


\section{Basic Formalism and Causal Graphs}
\label{S:back}

%\subsection{Basic Formalism}
In this paper we consider only propositional planning problems, using
the {\em propositional \strips\ with negative goals}
formalism~\cite{Bylander.AI.94}, in which both positive and negative
preconditions are allowed.  Following B{\"a}ckstr{\"o}m and
Klein~\scite{Backstrom:Klein:ci91}, we distinguish between
preconditions and prevail conditions. In the former case the variable
involved changes its value after the operator is executed, while in
the latter case the value does not change.  The post-condition of an
operator expresses which state variables it changes and what values
these variables will have after executing the operator. The
pre-condition specifies which values these changed variables must have
before the operator is executed. The prevail condition specifies which
of the unchanged variables must have some specific value before
execution of the operator and what these values are. Hence, prevail
conditions, such as having a visa, are needed in order to apply an
operator, such as Enter-USA, but their values do not change after the
operator is applied.  Finally, we assume that an operator is
applicable if and only if both its pre- and prevail conditions are
satisfied.

Formally, we assume that a problem instance is given by a quadruple
$\Pi = \langle \cV,\Lambda,Init,Goal\rangle$, where:
\begin{itemize}
  \item $\cV = \{v_1,\ldots,v_n\}$ is a set of propositional {\em state variables},
    each one with an associated {\em binary domain} $\cD(v_i)$. The domain
    $\cD(v_i)$ of the variable $v_i$ induces an {\em extended domain}
    $\cD^+(v_i) = \cD(v_i)\cup\{\su\}$, where $\su$ denotes the {\em unspecified}
    value.

  \item $Init$ is an initial, fully specified state, i.e.
    $Init \in \cD(v_1)\times\ldots\times\cD(v_n)$.
    
  \item $Goal$ is a set of possible goal states. We assume that such a
    set is specified by a partial assignment on $\cV$, thus $Goal \in
    \cD^+(v_1)\times\ldots\times\cD^+(v_n)$.
    
  \item $\Lambda = \{A_1,\ldots,A_N\}$ is a finite set of {\em operators}
    of the form $\langle \pre,\post,\prv \rangle$, where
    $\pre,\post,\prv \subseteq \cD^+(v_1)\times\ldots\times\cD^+(v_n)$
    denote the pre-, post-, and prevail condition, respectively.
    In what follows, by $\pre(A)$, $\post(A)$, and $\prv(A)$ we denote 
    the corresponding conditions of an operator $A$, and by $\pre(A)[i]$,
    $\post(A)[i]$, and $\prv(A)[i]$ the corresponding values of the variable
    $v_i$.
    
%     If $\prv(A)[i] = \su$, then the value of $v_i$ does not condition
%     applicability of $A$. If $\pre(A)[i] = \su$ then the value of
%     $v_i$ does not affected by $A$. The same is true if $\post(A)[i] =
%     \su$, since $\pre[i] \neq \su$ iff $\pre[i] \neq \post[i] \neq
%     \su$. Finally, in order to close the definition of the operator
%     conditions, we require that for each $A\in\Lambda$ and for each
%     %% $v_i\in\cV$, either $\post[i] = \su$, or $\prv[i] = \su$.

    % NEW-JAIR            ^^^^^^^
    For every $v_i \in \cV$, we must have either $\pre(A)[i] = \su$ or
    $\prv(A)[i] = \su$. Further, $\post(A)[i] \neq \su$ if and only if
    $\pre(A)[i] \neq \su$, in which case $\post(A)[i] \neq \pre(A)[i]$.
    % end NEW-JAIR
\end{itemize}

In this paper we analyse only planning problems with {\em unary} operators.
Therefore, in what follows, we assume that, for each operator $A\in\Lambda$,
we have that:
\begin{enumerate}
\item there exists a variable $v_i\in\cV$, such that $\pre(A)[i] \neq \su$, and
\item for each other variable $v_j\in\cV-\{v_i\}$, $\pre(A)[j] = \su$.
\end{enumerate}

Note that specifying both pre- and postconditions in case of only propositional
variables is redundant, and we use it only to simplify the presentation.
Likewise, our assumption that $\post(A) \neq \su$ implies $\pre(A) \neq \su$ is
different from the usual \strips\ formalism, and requires an exponential time
translation in general.  However, in our case of only unary operators, this
translation takes only linear time.



\subsection{Causal Graphs}
\label{S:cg}
{\em Causal graphs\/} were used by Williams and
Nayak~\scite{Williams:Nayak:IJCAI97} as a tool for describing the
structure of planning domains with unary operators. They represent a
dependence relation between the state variables in the domain. A
causal graph $\cG$ is a directed graph whose nodes correspond to the
state variables. An edge from $p$ to $q$ appears in the causal graph
if and only if some operator that changes the value of $q$ has a
prevail condition involving some value of $p$.  Hence the immediate
predecessors of $q$ in $\cG$ are all those variables that affect our
ability to change the value of $q$.  Such a problem structure was
introduced by Knoblock~\scite{Knoblock:aij94} in the context of
automatic generation of abstractions for planning.  The causal graph
is an intuitive model which is easily constructed given any planning
problem.
% NEW-JAIR

Causal graphs are not the only graphical structure that can be derived
from a given planning problem, and effectively exploited in solving
it.  For instance, graphs in which operators and literals (and not
variables/propositions) are represented by the nodes, and the edges
represent both prevail and preconditions were introduced by
Etzioni~\scite{Etzioni:aij93} and Smith and
Peot~\scite{Smith:Peot:aaai93}.  In particular, problem space graphs
of Etzioni~\scite{Etzioni:aij93} and operator graphs of Smith and
Peot~\scite{Smith:Peot:aaai93} were proposed as mechanisms to reduce
the number of threats that arise during the total-order and
partial-order planning, respectively.  However, in this paper we focus
on the causal graphs, since they were shown to be especially
informative when all operators are
unary~\cite{Jonsson:Backstrom:amai98,Williams:Nayak:IJCAI97}.
% end NEW-JAIR

Causal graphs have an important potential role in the design of
autonomous industrial systems, as argued and demonstrated by Williams
and Nayak~\scite{Williams:Nayak:IJCAI97}: Unary operators are natural
when the manipulated objects are hardware components, since the basic
control actions in such systems change the state of a single hardware
component.  The applicability of these control actions in any state
depends on the state of the affected component as well as on the state
of the related hardware components.  This naturally gives rise to a
planning domain with unary operators.  Moreover, since the state
variables correspond to hardware components, in the induced causal
graph we typically see that the prevail dependencies between variables
are usually implicitly entailed by the inter-composition of the
hardware components.  Thus, the causal graph of such domains resembles
the structure of and the relationships between the system's hardware
components.  This resemblance has important practical ramifications
for system design given the relationship between causal graph
structure and the complexity of plan generation: It enables the system
designer to consider the effect of his hardware design on the system's
ability to autonomously generate control sequences.

A case in point is the planning problem studied by Williams and Nayak
\scite{Williams:Nayak:IJCAI97}, which had a number of important
features: all operators were unary and reversible, and the causal
graph was acyclic.  Williams and Nayak argued that acyclic
connectivity frequently occurs in designed systems. However, the
requirement that all operators should be reversible seems to us
restrictive, and it has important impact on the complexity of the
problem. In the case of the Burton
planner~\cite{Williams:Nayak:IJCAI97}, there were good reasons to make
this assumption.  Burton's reactive nature precludes extensive
deliberation on the consequences of its operators. Thus it leaves open
the possibility that operators may degrade the system's capabilities,
leading it to dead-ends.  In that case, the restriction to reversible
operators was required in order to achieve a more reliable system. As
we show later, in certain cases, complete plans can be generated
efficiently even when the operators are not reversible.

Williams and Nayak's work has another interesting aspect, as noted by
Weld~\scite{Weld:aimag99}. For a long time, researchers have known that
planning problems with serializable subgoals are likely to be easier
to solve. Williams and Nayak recognized that their spacecraft
configuration task was serializable (many real-world problems are not),
and, more importantly, they developed a fast algorithm for computing
the correct order based on the fact that the underlying causal graph
is acyclic.  However, their algorithm makes heavy use of the
fact that all operators are reversible.  Informally, reversibility
implies that we can solve our subgoals one by one as long as they are
consistent with some topological order of the causal graph without
taking into account any global considerations: any side-effect can
always be undone.
Without the assumption of operator reversibility, it is relatively
easy to show that Williams and Nayak's algorithm works only if the causal graph forms a
directed chain. Even when the causal graph is a tree, although the problem
is easy, one must take care in the choice of which subgoal to achieve next
when operators are not reversible.
As we show later, when the structure of the
causal graph is more complicated than a directed tree then either the
problem is hard or, if not, a more sophisticated algorithm is
required.

Finally, we note that the existence of reversible operators might
make the problem seem easier than it actually is. 
In this paper we present an example of a
propositional planning problem with unary operators, acyclic causal
graph, and totally reversible operators, the minimal solution of which is
exponentially long in the size of the problem's description.
% }

\subsection{Example}

In order to illustrate the notion of a causal graph, consider the
following example, inspired by the work of Williams and
Nayak~\scite{Williams:Nayak:IJCAI97} on controlling the main engine
subsystem of the Cassini spacecraft, in general, and its valve driver
circuitry, in particular.

Each valve $VL$ (on/off) is controlled by a
valve driver $VLD$ (open/close), and a safety control unit
$SCU$ (safe/unsafe). Each driver controls exactly one valve, while
a safety control unit can control several valves.
Commands to the driver are sent via a driver control unit,
that consist of two switches, $S^l$ and $S^r$, which can be either on
or off.  The activating states of $S^l$ and $S^r$ are described below.
A valve reacts (by a state change) to a command from its driver only
if (i) the instruction actually involve a state change (i.e., an open
valve should not be reopened), and (ii) the safety control unit
indicates that manipulating the valve is safe.  In addition, the valve can
be closed if the safety control unit indicates an unsafe situation.  For
simplicity of presentation, Table~\ref{table:example} presents the
operator set for controlling the valves and valve drivers only.
The dashed boxes stand for driver control units, two switches in each.

\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline
 Affected component & $\pre$ & $\post$ & $\prv$\\
\hline
\multirow{2}{1in}{
$VLD$
  } & $close$ & $open$ & $S^l=1\; \wedge\; S^r=0$\\
\cline{2-4}
 & $open$ & $close$ & $S^l=0\; \wedge\; S^r=1$\\
\hline
\multirow{2}{1in}{
$VL$
  } & $on$ & $off$ & $VLD=close\;\wedge\; SCU=safe$\\
\cline{2-4}
& $off$ & $on$ & $VLD=open\;\wedge\; SCU=safe$\\
\cline{2-4}
& $on$ & $off$ & $SCU=unsafe$\\
\hline
\end{tabular}
\end{center}
\caption{A subset of the operator set for the valve circuitry controller example.}
\label{table:example}
\end{table}

Now suppose that the valves $VL_1$ and $VL_2$, with the drivers $VLD_1$ and $VLD_2$,
respectively, are controlled by a shared safety control unit $SCU$.
Given the operator set in Table~\ref{table:example}, the causal graph for
controlling this subsystem is presented in Figure~\ref{fig:example}.

\begin{figure}[hbt]
%\centering
\begin{center}
\mbox{
  \def\g#1{\save
    [].[rr]!C="g#1"*+++[F--]\frm{}\restore}%
  \xymatrix @C=25pt{
    *++[F]{S^l_1} \ar[dr] \g1 & & *++[F]{S^r_1}\ar[dl] &
      & *++[F]{S^l_2}\ar[dr] \g2 & & *++[F]{S^r_2}\ar[dl]\\
    & *++[F]{VLD_1}\ar[dr] & & *++[F]{SCU}\ar[dl]\ar[dr] & & *++[F]{VLD_2}\ar[dl]\\
    & & *++[F]{VL_1} & & *++[F]{VL_2}
}
}
\end{center}
\caption{Causal graph for the example.}
\label{fig:example}
\end{figure}


\section{Polytree Causal Graphs}
\label{S:upolytree}
Starting at this section, we show how, by bounding the structural
complexity of the causal graph, we can bound the complexity of plan
generation. Recall that we use a propositional language (binary variables) to
describe the state of the world, and each operator is described by its
prevail conditions, single precondition, and single effect (or post-condition).
The precondition and the effect are two literals, one the
negation of the other.

%carmel
A causal graph forms a {\em polytree} if there is a single path between every
pair of nodes in the induced {\em undirected\/} graph\footnote{These graphs are
  also known as {\em singly connected DAGs}.}, i.e., the induced undirected
graph is a tree.
%carmel: end of change
For example, the causal
graph presented in Figure~\ref{fig:example} forms a polytree.
For this class of problems we present a planning algorithm which is
polynomial if the indegree of all nodes in the causal graph is bounded
by a constant.  We argue that this assumption is reasonable if the
prevail dependencies reflect the inter-composition of some controlled
hardware components~\cite{Williams:Nayak:IJCAI97}.
% Belongs to the ECP version
\commentout{
The algorithm is 
based on the POP algorithm of Penberthy and Weld
\scite{Penberthy:Weld:KR92}.
For those familiar with the algorithm, we note one
slight technical change, stemming from the use of unary operators.
POP uses two fictitious actions $A_0$ and $A_{\infty}$ to capture the initial 
and goal state, respectively. Here, we replace each of these actions by
a set of actions, each with a single effect. The (fictitious) action
setting the initial value of variable $v_i$ is denoted $A^0_i$ and the 
fictitious action whose precondition is the value of variable $v_i$ is
denoted $A^*_i$.
}  %end commentout


Given a propositional
planning instance with a polytree causal graph, we:
\begin{enumerate}
\item \label{gstep1} Provide a {\em general} upper bound for the number of
  times that a variable may be required to change its value on a valid, irreducible
  plan.
\item \label{gstep2} Using this general upper bound, provide a polynomial time
  procedure, called {\sc determine-max-sequence}, that, given a variable $v$,
  determines the {\em actual} maximal number of times that $v$ can change its
  value on a valid, irreducible plan.
  %{\em maximal achievable} number of {\em possibly required} value
  %changes for a given variable.
% NEW-JAIR
\item \label{gstep3} Provide a preprocessing algorithm that: (a) determines
  whether or not a plan for a given problem instance of our class exists, and
  (b) performs a substantial amount of preprocessing for the subsequent step of
  plan generating.  This algorithm is based on a top-down execution of {\sc
    determine-max-sequence} on the variables of the given problem instance.
% \item Provide a preprocessing algorithm that determines whether or not a plan for a
%   given problem instance of our class exist. This algorithm is based
%   on a top-down execution of the previously defined procedure on the
%   variables of the given problem instance.

  
\item If the answer of the plan existence check is positive we run a particular
  {\em deterministic} instance of the POP algorithm\footnote{ A short review of
    the POP algorithm, and the corresponding formalism is provided in Appendix
    A.  For those familiar with the algorithm, we note one slight technical
    change, stemming from the use of unary operators.  POP uses two fictitious
    actions $A_0$ and $A_{\infty}$ to capture the initial and goal state,
    respectively. Here, we replace each of these actions by a set of actions,
    each with a single effect. The (fictitious) action setting the initial
    value of variable $v_i$ is denoted $A^0_i$ and the fictitious action whose
    precondition is the goal value of variable $v_i$ is denoted
    $A^*_i$.}~\cite{Penberthy:Weld:KR92}, called\ \POP, that generates the
  required plan using the information provided by the preprocessing algorithm,
  without backtracking, in linear time.
\end{enumerate}

% NEW-JAIR
Informally, this process is based on the following properties of the planning
problems with polytree causal graph. First, the bound achieved in
step~\ref{gstep1} is necessary for the steps~\ref{gstep2}-\ref{gstep3}, which
are the main steps of our technique.  By itself, this bound will be valid not
only for a polytree, but for a wider class of directed-path singly connected
causal graphs.  However, steps~\ref{gstep2}-\ref{gstep3} will be valid for
polytree causal graphs only, because of the following properties of this form
of dependence relation between the variables:
\begin{enumerate}[(i)]
\item \label{ggstep1} Given a variable $v\in\cV$, changing the value of a
  parent (immediate predecessor) $w \in \parents(v)$ does not require any
  changes of neither other parents of $v$, nor their predecessors in the causal
  graph.
\item \label{ggstep2} The number of times that a variable $v$ will be able to
  change its value along a valid plan for a given problem instance depends
  directly both on these numbers for $\parents (v)$, and on the actual
  ordering of the value changes of $\parents (v)$.
\item From (\ref{ggstep1}) it follows that {\em all} the possible orderings of
  the value changes of $\parents (v)$ are legal. In addition, it will be shown
  that chosing an ordering for the value changes of $\parents (v)$ will not
  affect our ability to change the value of any variable except of $v$.
\item The crucial part of the process (steps~\ref{gstep2}-\ref{gstep3}) is
  basically about finding the {\em right} ordering of the {\em right} number of
  value changes of $\parents (v)$ for each variable $v\in\cV$. By synchronizing
  these changes to $v$'s parents appropriately, we can increase the number
  of possible changes to $v$.
\end{enumerate}
% end NEW-JAIR

We start with some notation. First, a valid plan $P$ for a given planning
instance $\Pi$ will be called {\em irreducible} if any subplan $P'$ of $P$ is
not a plan for $\Pi$, in the following sense: Removal of any subset of
(not necessarily subsequent) actions from $P$ makes the resulting plan either
illegal, or its initial state is not $Init$, or its goal state is not one of
the states specified by $Goal$.
The notion of irreducible plans was introduced
by Kambhampati~\scite{rao95}, where it was exploited for admissible
pruning of partial plans during
search\footnote{Irreducible plans were called in~\cite{rao95}
  {\em minimal plans}. However, we decided to change the name of
  this concept in order to prevent an ambiguity between ``minimal as
  irreducible'' and ``minimal as optimal''.}.

Now, given a planning instance $\Pi$, let $\cP$ be the set of {\em all}
irreducible plans for $\Pi$. We denote by $\Must (v)$ the maximal number of
times that a variable $v\in\cV$ changes its value in the course of execution of
an irreducible plan for $\Pi$. Formally, let $\LocalMust (P,v)$ be the number
of times that $v$ changes its value in the course of execution of a plan $P$.
Then,
\[
  \Must (v) = \max_{P\in\cP}\{\LocalMust(P,v)\}
\]
% end NEW-JAIR

% First we make the following observation upon which we base our algorithm.
% Given
% a planning instance $\Pi$, denote by $\Must (v)$ the maximal number of times
% that a variable $v\in\cV$
% changes its value in the course of execution of a valid, irreducible plan for $\Pi$.
% Informally it means that if a plan for $\Pi$ contains more than $\Must
% (v)$ changes of $v$ then it contains some redundant steps that can be
% removed from the plan.
Observe that, for any
planning problem with unary operators, a variable must change its value
at most once for each required change of its immediate successors in
the causal graph (in order to
satisfy the necessary prevail conditions), and then at most once in order
to obtain the value requested by the goal. % state.
Thus, for all variables in $\cV$, $\Must (v)$ satisfies:
\begin{equation}
\label{eq:must}
   \Must (v) \leq 1\ +\ \sum_{\lsons (v)} \Must (u)
\end{equation}
where $\sons (v)$ denotes the immediate successors of $v$ in the
corresponding causal graph.
%carmel
Adopting the terminology
from~\cite{Domshlak:Shimony:flairs03,Shimony:Domshlak:singly}, a directed
acyclic graph $G$ is {\em directed-path singly connected} if, for every pair of
nodes $s,t\in G$, there is at most one directed path from $s$ to $t$.  The
following lemma shows that if the causal graph forms a directed-path singly
connected DAG then we can bound $\Must (v)$ by $n$.  Clearly, all polytrees are
directed-path singly connected DAGs, but not vice versa.
%carmel- end of change

\begin{lemma}
\label{l1}
  For any solvable problem instance $\Pi$
  with a directed-path singly connected causal graph over $n$ variables, for any
  variable $v$, we have that $\Must (v) \leq n$.%:
%   \begin{eqnarray*}
%    \Must (v) \leq n
%   \end{eqnarray*}
\end{lemma}


% The proof is obtained by a relatively straightforward induction.  The
% main point of establishing such bounds is that using bounds on
% $\Must$, we can bound the number of value changes, and thus, the size of any
% plan without redundant steps.

\begin{proof}
The proof is by induction on $n$. For $n=1$ it is obvious that $\Must
(v) \leq 1$. Now suppose that when $|\cV| = n-1$ then
for any $v\in\cV$, 
\[
\Must (v) \leq n-1
\]
Let $\Pi'$ be some problem instance for which $|\cV'|=n$. Suppose that
the variables in $\cV'=\{v_1,\ldots v_{n}\}$ are topologically ordered
based on the domain's causal graph. Clearly, $v_n$ is a leaf node
(i.e., $\sons$ ($v_n$) = $\emptyset$). We will denote by $\Pi$ the
problem instance obtained by removing $v_n$ from the domain,
and the corresponding variable set by $\cV$.
According to Eq.~\ref{eq:must},
for each immediate predecessor $v$ of $v_n$ in the causal graph,
\[
     \newMust (v) \leq \Must (v) + \newMust (v_n) \leq \Must (v) + 1
\]
where $\newMust (v)$ denotes $\Must (v)$ with respect to $\Pi '$.  Generally,
since the causal graph is directed-path singly connected, for each variable
$v\in \cV'$,
\begin{equation}
\label{eq:newmust}
   \newMust (v) \leq \sset{\Must (v) + 1,
     \ \ \ \mathrm{if}\ \mathrm{there}\ \mathrm{is}\ \mathrm{a}\ \mathrm{path}\ \mathrm{from}\
     \mathnormal{v}\ \mathrm{to}\ \mathnormal{v_n}\\
                       \Must (v),\ \ \ \ \ \ \ \ \mathrm{otherwise} }
\end{equation}
and thus, for each $v\in\cV'$, holds
%\begin{eqnarray*}
\[
  \newMust (v) \leq n
\]
%\end{eqnarray*}
\end{proof}


Recall that $\Must (v)$ stands for an upper bound on the number of
value changes of $v$ that may be required by a valid, irreducible
plan.  However, the maximal achievable number of value changes of $v$,
denoted by $\Can (v)$ can be greater or less than $\Must (v)$.  For
example, if $v$ has no predecessors in the causal graph, and there are
two operators affecting $v$ differently, then $\Can (v) = \infty$.

We denote the upper bound on the {\em feasible} number of
value changes of $v$ that may be required 
in a valid, irreducible plan for $\Pi$ by $\FeasibleMust (v)$. Informally, no more
than $\Can (v)$ value changes of $v$ {\em can} be required and no more
than $\Must (v)$ value changes of $v$ {\em should} be required, thus
\begin{equation}
\label{eq:feasible}
  \FeasibleMust (v) = \min (\Can (v), \Must (v))
\end{equation}

Determining $\FeasibleMust (v)$ for all variables requires explicit
examination of a given problem instance. Recall that here we restrict
the causal graph of $\Pi$ to form a polytree.  To simplify the
presentation, we assume that the goal values are specified for all
state variables, i.e. $Goal \in \cD(v_1)\times\ldots\times\cD(v_n)$.
Later we show that this assumption does not affect the generality of
the algorithm. Denote by $v^0$ and $v^*$ the initial and the goal
values of $v$ in $\Pi$, and by $\Lambda_v \subseteq \Lambda$ the set
of all operators affecting $v$.  First we examine the root variables
of the causal graph, then we analyze the rest of the variables.

Denote by $\parents (v)$ the immediate predecessors of $v$ in the causal
graph. If $\parents (v) = \emptyset$, then there are at most two operators
$A_v^-,A_v^+$ in $\Lambda_v$: $A_v^+$ has $v^*$ as its postcondition,
while $A_v^-$ has the reverse effect.  Since these operators 
have no prevail condition, if both $A_v^-$ and $A_v^+$ are presented in $\Lambda$,
then they can be applied one after another an infinite number of times.
Therefore, from Eq.~\ref{eq:feasible}, $\FeasibleMust (v) = n$.
 If $\Lambda_v \neq
\{A_v^-,A_v^+\}$ then we have two cases: If the initial and the goal
values of $v$ are the same, then we cannot change the value of $v$
and reconstruct it later, and thus $\FeasibleMust (v) = 0$. Alternatively, if the
initial and the goal values of $v$ are different then if $\Lambda_v =
\{A_v^+\}$ then we can achieve the goal value of $v$ but only once and
thus $\FeasibleMust (v) = 1$. Otherwise, the goal value of $v$ is unachievable,
thus the given problem instance is unsolvable.
Table~\ref{table:can}
summarize this analysis.

\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|c|c|}
\hline
          & $\Lambda_v$ & $\FeasibleMust (v)$\\
\hline
\hline
$v^0=v^*$ & $\{A_v^-,A_v^+\}$ & n\\
\hline
          & otherwise & 0\\
\hline
\hline
$v^0\neq v^*$ & $\{A_v^-,A_v^+\}$ & n\\
\hline
              & $\{A_v^+\}$ & 1\\
\hline
              & otherwise  & no solution\\
\hline  
\end{tabular}
\end{center}
\caption{$\FeasibleMust (v)$ values for the root variables in the causal graph.}
\label{table:can}
\end{table}


Now consider a variable $v$ which is presented by an internal node in
the causal graph: $\parents (v) = \{w_1,\ldots,w_k\} \neq \emptyset$.
Observe that the number of possible value changes of $v$ depends on
and only on: 
\begin{enumerate}
\item The initial and the goal values of $v$, i.e., $v^0$ and $v^*$.
\item The set of operators affecting $v$, i.e., $\Lambda_v$.
\item The maximally possible (but still reasonable) number of times that
  predecessors of $v$ can change their values, i.e., $\FeasibleMust (w_1),
  \ldots, \FeasibleMust (w_k)$.
\item The actual scheduling of the value changes of the
  predecessors of $v$.
\end{enumerate}
The last point is crucial -- it means that in order to determine
$\FeasibleMust (v)$ we should find a particular scheduling of the value changes
of $\parents (v)$ that allows such a maximal number of value changes
for $v$. The corresponding interleaving sequence of $v$'s values, starting and
finishing by $v^0$ and $v^*$ respectively, with $\FeasibleMust (v)$ value changes
will be called {\em maximal} and will be denoted by $\sigma (v)$
($|\sigma (v)| = \FeasibleMust (v) + 1$).

From Lemma~\ref{l1}, for $1 \leq i \leq k$, we have $\FeasibleMust (w_i) \leq
n$, thus the number of different orderings of value changes of $\parents (v)$
can be exponential in $n$. For instance, when, for $1 \leq i \leq k$, we have
$\FeasibleMust (w_i) = n$, this number of different orderings
% NEW JAIR
%can be greater than $n^{nk}$.
can be expressed as:
\[
\prod_{i=1}^{k-1}{\sum_{j=1}^{n}{\binom{n-1}{j-1}\binom{n i + 1}{j}}} \gg 2^{nk}
\]
where the correctness of the expression on the left side of the inequality is
shown by Lemma~\ref{l:aux} (see Appendix~\ref{app:proofs},
p.~\pageref{l:aux}).
%
Clearly, we cannot check all these orderings in a naive manner. Following, we
provide an algorithm that determines $\sigma (v)$ in time which is polynomial
in $n$.
% end NEW JAIR

For clarity of presentation we want to distinguish between the different
elements of a maximal sequence $\sigma (v)$.
Since all variables are binary, % for clarity of presentation,
we denote the initial value of $v$, $v^0$, by $\sb_v$ and the opposite
value by $\sw_v$ (black/white). Similarly, $\sb_i$ and $\sw_i$ will
stand for the corresponding values of the variable $v_i$.  If so, we
can think about all the operators in $\Lambda$ as described in this
language.  Likewise, we sequentially number the appearances of each
value of $v$ on $\sigma (v)$. For example, $\sb_v^i$ stands for the $i$th
appearance of the value $\sb_v$ along $\sigma (v)$.
To illustrate this notation, suppose that $\cD(v) = \{true, false\}$, the
initial value of $v$ is $v^0 = true$, and $\FeasibleMust (v) = 4$. Then, we
have:
\begin{eqnarray*}
  \sb_v & \equiv & true\\
  \sw_v & \equiv & false\\
  \sigma (v) &  = & \sb_v^1 \cdot \sw_v^1 \cdot \sb_v^2 \cdot \sw_v^2 \cdot \sb_v^3
\end{eqnarray*}
%%%% (remember that $i\leq \frac{n}{2} + 1$).

%% NEW-JAIR
First, for every variable $v$, every operator $A \in \Lambda_v$ is extended to
a set of operators % $\{A^1,\ldots,A^m\}$
that explicitly specify prevail values for {\em all} parents of $v$ in the
causal graph: If $|\parents (v)| = k$, and the prevail condition of $A$ is
specified only in terms of some $0 \leq k' \leq k$ parents\footnote{For every
  other parent $w_j$ of $v$, we have $\prv(A)[j]=\su$.} of $v$, then $A$ is
extended to a set of $2^{k-k'}$ operators, where each operator extends $A$ by
an instantiation of the previously unspecified parents of $v$. For example,
consider a variable $v$ with $\parents (v) = \{u,w\}$, and an operator
\[
  A = \{\pre:\{\sb_{v}\},\ \post:\{\sw_{v}\},\ \prv:\{\sb_u\}\},
\]
the prevail condition of which does not involve $w$. This operator is extended
to a pair of operators:
\begin{eqnarray*}
  A' & = & \{\pre:\{\sb_{v}\},\ \post:\{\sw_{v}\},\ \prv:\{\sb_u,\sb_w\}\}\\
  A'' & = & \{\pre:\{\sb_{v}\},\ \post:\{\sw_{v}\},\ \prv:\{\sb_u,\sw_w\}\}\\
\end{eqnarray*}
corresponding to the possible values of $w$.  In what follows, we refer to the
operator set resulting from such a compilation of $\Lambda$ as
$\Lambda^{\bowtie}$. Note that, under the assumption of constantly bounded
maximal indegree $\kappa$ of the causal graph, compiling $\Lambda$ into
$\Lambda^{\bowtie}$ takes only polynomial time, since, for every variable $v$,
$|\Lambda_v^{\bowtie}| \leq 2^{\kappa+1}$, and thus $|\Lambda^{\bowtie}| =
O(n2^{\kappa+1})$.
%% end NEW-JAIR

Given the maximal sequences $\sigma (w_1), \ldots, \sigma (w_k)$ and
the operator set $\Lambda_v^{\bowtie}$ we construct a directed graph (denoted
as $G_e'(v)$) that captures {\em all (and only)
  feasible} sequences of, up to $n$, value changes of $v$, where
each value change is annotated with the corresponding assignment on
$\parents (v)$. Although the number of the captured sequences can be
exponential in $n$, the size of $G'_e(v)$ is polynomial in $n$.
With respect to this graph, the problem of finding the maximal
sequence $\sigma(v)$ is reduced to the problem of finding a
longest path from a given node to an arbitrary other node in a
directed acyclic graph.

The graph $G'_e(v)$ is created in three incremental steps.  At the first step,
given the maximal sequences $\sigma (w_1), \ldots, \sigma (w_k)$ and the
operator set $\Lambda_v^{\bowtie}$ we construct a directed labeled graph $G(v)$
capturing information about all sequences of assignments on $\parents(v)$
that can enable $n$ or less value flips of $v$.  The graph $G(v)$ is defined as
follows:

\begin{enumerate}
  \item $G(v)$ consist of $\eta$ nodes, where
  \[
   \eta = \sset{
                         n, \hskip 0.5cm ((n=2j) \;{\mathrm{and}}\; (v^0=v^*))
                              \;{\mathrm{or}}\\
                          \hskip 1cm    ((n=2j+1) \;{\mathrm{and}}\; (v^0 \neq
                          v^*)),\; j\in{\mathbb N}\\
                          n-1, \hskip 0.2cm{\mathrm{otherwise}}
                        }
 \]
 
\item $G(v)$ forms a {\em 2-colored multichain}, i.e., (i) the nodes
  of the graph are colored by black and white, starting by black; (ii)
  there are no two subsequent nodes with the same color; (iii) for $1
  \leq i \leq \eta-1$, edges from the node $i$ are only to the node
  $i+1$.

  Observe that such a construction of $G(v)$ promises that the color of
  the last node will be consistent with $v^*$.

\item The nodes of $G(v)$ are denoted precisely by the elements of the maximal
  sequence $\sigma (v)$, i.e., $\sb_v^i$ stands for the $i$th black node in $G(v)$.

\item Suppose that there are $m$ operators in $\Lambda_v^{\bowtie}$ that change
   the value of $v$ from $\sb_v$ to $\sw_v$. In this case, for each $i$,
   there are $m$ edges from $\sb_v^i$ to
   $\sw_v^i$, and $|\Lambda_v^{\bowtie}|-m$ edges from $\sw_v^i$ to $\sb_v^{i+1}$.
   All edges are labeled by the prevail conditions of the corresponding
   operators, i.e., a $k$-tuple of the values
   of $w_1,\ldots,w_k$. This tuple is denoted by $l(e)$ (label of the
   edge $e$) and its component, corresponding to a predecessor $w_i$, is
   denoted by $l(e)_{w_i}$.
\end{enumerate}

This formal definition of $G(v)$ is relatively complicated, thus we provide a 
demonstrating example:  Suppose that we are given a problem instance
over 5 variables, and we consider a variable $v$ with $\parents (v) =
\{u,w\}$, $v^0=\sb_v$, and $v^*=\sw_v$. Recall that every operator in
$\Lambda^{\bowtie}$ is presented as a three-tuple $\langle\pre ,\post
,\prv \rangle$ of pre-, post-, and prevail conditions of the
operator respectively.  Suppose that:

\[ \sigma (u)  = \sb_u^1 \cdot \sw_u^1 \;\;\;\;\;\;\;
  \sigma (w)  = \sb_w^1 \cdot \sw_w^1 \cdot \sb_w^2 \cdot \sw_w^2
  \]
\[
\Lambda_v^{\bowtie}    = \sset { 
                       A_v^1 = \{\pre:\{\sb_{v}\},\ \post:\{\sw_{v}\},\ \prv:\{\sb_u,\sw_w\}\}\\
                       A_v^2 = \{\pre:\{\sw_{v}\},\ \post:\{\sb_{v}\},\ \prv:\{\sb_u,\sb_w\}\}\\
                       A_v^3 = \{\pre:\{\sw_{v}\},\ \post:\{\sb_{v}\},\ \prv:\{\sw_u,\sw_w\}\}
                       }
                     \]
For this case, the graph $G(v)$ is presented by Figure~\ref{fig:graph1}.
\begin{figure}[hbt]
%\centering
\begin{center}
\mbox{
\xymatrix @C=25pt{
 \sb_v^1 \ar[r]^{\sb_u\sw_w} & 
 \sw_v^1 \ar@/^1pc/[r]^{\sb_u\sb_w} \ar@/_1pc/[r]_{\sw_u\sw_w} &
 \sb_v^2 \ar[r]^{\sb_u\sw_w} &
 \sw_v^2 \ar@/^1pc/[r]^{\sb_u\sb_w} \ar@/_1pc/[r]_{\sw_u\sw_w} &
 \sb_v^3 \ar[r]^{\sb_u\sw_w} &
 \sw_v^3
}
}
\end{center}
\caption{Example of the graph $G(v)$.}
\label{fig:graph1}
\end{figure}

The constructed graph $G(v)$ captures information about all {\em
  potentially possible} executions of the operators in $\Lambda_v^{\bowtie}$
that can provide us $\Must(v)$ or less value changes of $v$. Each path,
started at the source node of $G(v)$, uniquely corresponds to such an
execution. Although the number of these alternative executions may be
exponential in $n$, this graphical representation is compact: the number
of edges in $G(v)$ is $O(n \cdot |\Lambda_v^{\bowtie}|)$.
Note that the information about the number of times that each
operator in $\Lambda_v^{\bowtie}$ can be executed is not captured by $G(v)$.
The following two steps add this information indirectly and exploit it to
find a maximal sequence $\sigma (v)$.

At the second step of construction, we expand $G(v)$ with respect to the
maximal sequences $\sigma (w_1), \ldots, \sigma (w_k)$ as follows: Each edge $e
\in G(v)$ (which by definition corresponds to some operator $A \in
\Lambda_v^{\bowtie}$), is replaced by a set of edges such that their labels
correspond to all possible assignments of the elements of $\sigma (w_1),
\ldots, \sigma (w_k)$ to $l(e)$ (i.e., $\prv(A)$).  Likewise, we add a dummy
source node $s_v$, with an edge from $s_v$ to the original source node of
$G(v)$ labeled by a tuple of the first elements of $\sigma (w_1), \ldots,
\sigma (w_k)$ (= initial values of $w_1,\ldots,w_k$).  Similarly, we add a
dummy target node $t_v$, with an edge from the original target node of $G(v)$
to $t_v$ labeled by a tuple of the last elements of $\sigma (w_1), \ldots,
\sigma (w_k)$ (= goal values of $w_1,\ldots,w_k$). We denote this extended
graph by $G'(v)$, and Figure~\ref{fig:graph2} illustrates $G'(v)$ for the
example above.

\begin{figure}[hbt]
\centering
\mbox{
\xymatrix @C=35pt{
 s_v \ar[r]^{\sb_u^1 \sb_w^1} &
 \sb_v^1 \ar@/^1pc/[r]^{\sb_u^1 \sw_w^1} \ar@/_1pc/[r]_{\sb_u^1 \sw_w^2} & 
 \sw_v^1 \ar@/^3pc/[r]^{\sb_u^1 \sb_w^1} \ar@/^1pc/[r]^{\sb_u^1 \sb_w^2}
 \ar@/_1pc/[r]_{\sw_u^1 \sw_w^1} \ar@/_3pc/[r]_{\sw_u^1 \sw_w^2}  &
 \sb_v^2 \ar@/^1pc/[r]^{\sb_u^1 \sw_w^1} \ar@/_1pc/[r]_{\sb_u^1 \sw_w^2} & 
 \sw_v^2 \ar@/^3pc/[r]^{\sb_u^1 \sb_w^1} \ar@/^1pc/[r]^{\sb_u^1 \sb_w^2}
 \ar@/_1pc/[r]_{\sw_u^1 \sw_w^1} \ar@/_3pc/[r]_{\sw_u^1 \sw_w^2} &
 \sb_v^3 \ar@/^1pc/[r]^{\sb_u^1 \sw_w^1} \ar@/_1pc/[r]_{\sb_u^1 \sw_w^2} &
 \sw_v^3 \ar[r]^{\sw_u^1 \sw_w^2} &
 t_v
}
}
\caption{Example of the graph $G'(v)$.}
\label{fig:graph2}
\end{figure}


The extended graph $G'(v)$ can be viewed as a projection of the
maximal sequences $\sigma (w_i)$, {\footnotesize $1 \leq i \leq k$}, on the graph
$G(v)$. Each edge in $G(v)$ may be replaced by $O(n^k)$ edges in
$G'(v)$, and thus the number of edges in $G'(v)$ is $O(n^{k+1} \cdot
|\Lambda_v^{\bowtie}|)$.

It is easy to see that not all paths in $G'(v)$ starting at $s_v$ are relevant.
For example, in $G'(v)$ above, an operator instance prevailed by $\sb_u^1
\sb_w^2$ can not be performed after an operator instance prevailed by $\sb_u^1
\sw_w^2$. Thus, now we are faced with the problem of finding a longest {\em
  feasible path} from $s_v$ to a node in $G'(v)$, the label of which is
consistent with $v^*$.  The following (last) step provides a reduction of
the problem of finding a longest feasible path from $s_v$ to a $v^*$-colored
node in $G'(v)$ to a known problem of finding a longest path in a directed
acyclic graph.  Let the graph $G'_e(v)$ have the {\em edges} of $G'(v)$ as
nodes, and let its edges be defined by all {\em allowed} pairs of immediately
subsequent edges in $G'(v)$: $(e,e')$ is allowed if, for $1 \leq i \leq k$,
either $l(e)_{w_i} = l(e')_{w_i}$ or $l(e')_{w_i}$ appears after $l(e)_{w_i}$
on $\sigma (w_i)$.  Such a construction is a variant of a so called ``edge
graph'' known in graph theory; the addition in our case is the exclusion of
non-allowed edges from it.  Clearly, $G'_e(v)$ can be constructed in time
polynomial in size of $G'(v)$, and the number of edges in $G'_e(v)$ is
$O(n^{2k+2}\cdot |\Lambda_v^{\bowtie}|^2)$.

\begin{figure}[htb]
\centering
\mbox{
%\def\objectstyle{\scriptstyle}
\xymatrix @C=30pt{
 & & \sb_u^1 \sb_w^1 \ar[dr] \ar[dddr] & & 
     \sb_u^1 \sb_w^1 \ar[dr] \ar[dddr] \\
 & \sb_u^1 \sw_w^1 \ar@{-->}[r] \ar[ddr] \ar[dddr] &
     \sb_u^1 \sb_w^2 \ar@{-->}[ddr] &
     \sb_u^1 \sw_w^1 \ar[r] \ar[ddr] \ar[dddr] &
     \sb_u^1 \sb_w^2 \ar[ddr] &
     \sb_u^1 \sw_w^1 \ar[dr]\\
 \sb_u^1 \sb_w^1 \ar@{-->}[ur] \ar[dr] & & & & & & 
     \sw_u^1 \sw_w^2\\
 & \sb_u^1 \sw_w^2 \ar[dr] &
     \sw_u^1 \sw_w^1 &
     \sb_u^1 \sw_w^2 \ar[dr] &
     \sw_u^1 \sw_w^1 &
     \sb_u^1 \sw_w^2 \ar[ur]\\
 & & \sw_u^1 \sw_w^2 & & \sw_u^1 \sw_w^2
}
}
\caption{Example of the graph $G'_e(v)$.}
\label{fig:edgegraph}
\end{figure}


Figure~\ref{fig:edgegraph} presents $G'_e(v)$ for our example.  The
dashed edges present the longest path from the dummy source node to a
node that corresponds to a value change from $\neg v^*$ to $v^*$ (from
$\sb_v$ to $\sw_v$). Such a longest path in $G'_e(v)$ describes a
maximal sequence of value changes $\sigma (v)$, and its length is
actually $\FeasibleMust (v) + 1$.  In our example, $\sigma (v) =
\sb_v^1 \cdot \sw_v^1 \cdot \sb_v^2 \cdot \sw_v^2$, and $\FeasibleMust
(v)=3$.  Note that if $v^0=v^*$ then the empty path will be also
acceptable since, in general, $v$ does not have to change its value.
In this case $\FeasibleMust (v)=0$ and $\sigma (v)$ will consist of
only one element which corresponds to the initial (= goal) value of
$v$.


Observe that a longest path in $G'_e(v)$ describes not only $\sigma
(v)$ but also the actual sequence of invocations of the operators from
$\Lambda_v^{\bowtie}$ that provides $\sigma (v)$. We denote by $\{A(\sb^j_v)\}$
and $\{A(\sw^j_v)\}$ the sequences of operator instances that have as
effects the corresponding elements from the sequences $\{\sb^j_v\}$
and $\{\sw^j_v\}$ ($\{\sb^j_v\}\cup\{\sw^j_v\}=\sigma(v)$)
%%% ($j \leq \frac{n}{2} + 1$)
of $v$'s values,
respectively.  In what follows, we address these sequences of
operator instances as one sequence of operator instances
$\Gamma_v = \{A(\nu^i_v)\}_{i=2}^{\FeasibleMust (v)}$, where
$A(\nu^i_v)$ has $\nu^i_v$ as its effect, and
% conference: $\post(A(\nu^i_v)) = \nu^i_v$, and
\[
\nu^i_v = \sset {
                  \sb^{\frac{i+1}{2}}_v, \hskip 1cm i=2k+1\\
                  \sw^{\frac{i}{2}}_v, \hskip 1.2cm i=2k} \;\;\;\;k\in{\Bbb N}
\]


% Note that we
% can view these operator invocations as new operators that are
% described in terms of value acquisitions rather that in terms of
% values of the variables.


\begin{figure*}[tb]
\centering
  \fbox{
\begin{minipage}{\textwidth}
%{\footnotesize
\textbf{Procedure} {\sc forward-check} ($\Pi$)
\begin{enumerate}
  \item Topologically sort all variables $\cV$ based on the
        the causal graph.% $\cG$
  \item For each variable $v\in\cV$, call {\sc determine-max-sequence}($\Pi, v$),
    respecting the above ordering.
  \item If one of the calls to {\sc determine-max-sequence} return failure, then return
    failure.  Otherwise return success.
\end{enumerate}

\textbf{Procedure} {\sc determine-max-sequence} ($\Pi, v$)
\begin{enumerate}
  \item If $\parents (v) = \emptyset$ then
    \begin{enumerate}
    \item If $v^0 \neq v^*$ and $A_v^+\not\in\Lambda_v$, return
      failure.
    \item Otherwise, determine $\sigma (v)$ according to the rules in
      Table~\ref{table:can}, and return success.
    \end{enumerate}
  \item Otherwise, if $\parents (v) = \{w_1,\ldots,w_k\}$ then
    \begin{enumerate}
    \item Construct $G(v)$ (based on $v^0,v^*$, and $\Lambda_v^{\bowtie}$).
    \item Construct $G'(v)$ (from $G(v)$, based on $\sigma (w_1),\ldots
      \sigma (w_k)$).
    \item Construct $G'_e(v)$ (from $G'(v)$, based on $\sigma (w_1),\ldots
      \sigma (w_k)$).
    \item \label{step:mod1} Determine the longest path in $G'_e(v)$ to a node
      corresponding to a $v^*$-ended value change, and derive $\sigma
      (v)$ and the corresponding sequence of operators from it.
    \item \label{step:mod2} If $v^0\neq v^*$ and $\FeasibleMust (v) = 0$, return failure.
      Otherwise, return success.
    \end{enumerate}
\end{enumerate}
%}
\end{minipage}
}
  \caption{{\sc forward-check} algorithm}
  \label{fig:polytree}
\end{figure*}


Procedure {\sc forward-check} in Figure~\ref{fig:polytree}
summarizes the presented approach.
Note that finding a set of longest
paths from a node to all other nodes in a directed acyclic graph can be done
in time linear in the size of the graph~\cite{pert69}.
Therefore, the time complexity of
a call to the {\sc determine-max-sequence} procedure with a variable
$v$ is bounded by the size of the constructed graph $G'_e (v)$ and
thus is $O(n^{2k+2}\cdot |\Lambda_v^{\bowtie}|^2)$.  {\sc forward-check} calls
{\sc determine-max-sequence} $n$ times. Therefore, if the maximal node
indegree is bounded by a constant $\kappa$, then the overall complexity of
the algorithm is $O(|\cV|^{2\kappa+3}\cdot 2^{2\kappa+2})$, i.e.,
polynomial in the size of the problem description.


\begin{figure*}[tb]
\centering
  \fbox{
\begin{minipage}{\textwidth}
\textbf{Algorithm:} \POP\ ($\langle \cA,\cO,\cL \rangle,
\mathtt{agenda}, \Lambda$)
\begin{enumerate}
  \item \textbf{Termination:}
        If $\mathtt{agenda}$ is empty, return $\langle \cA,\cO,\cL \rangle$
  \item \textbf{Goal selection:}
        Let $\langle \val_i, A_{need} \rangle$
        be a \emph{rightmost} pair on the $\mathtt{agenda}$ (by
        definition, $A_{need} \in \cA$ and $\val_i$ is one of the
        pre/prevail conditions of $A_{need}$).
  \item \textbf{Operator selection:}
        \begin{enumerate}
          \item \label{step:simple} If $A_{need} \neq A^*_i$ ($\val_i
            =\nu_i^j$) then $A_{add} = A(\nu^{j}_i) \in \Gamma_i \cup \{A_i^0\}$.
          \item \label{step:nonsimple} Otherwise:
            \begin{enumerate}
            \item Let $m = \max{\{\ j\ |\ A(\nu^j_i)\in\cA \}}$.
            \item \label{step:carmel} If $v^*_i$ is consistent with
              % $\nu_i^j$ 
              $\nu^{m}_i$
              (both associated with the same color from
              $\{\sb,\sw\}$)\\ then $A_{add} = A(\nu^{m}_i)$, else
              $A_{add} = A(\nu^{m+1}_i)$.
            \end{enumerate}
        \end{enumerate}
  \item \label{step:update} \textbf{Plan updating:}
        Let $\cL = \cL \cup \{A_{add} \stackrel{\val_i}{\rightarrow}
        A_{need}\}$, and let $\cO = \cO \cup \{A_{add} <
        A_{need}\}$. If $A_{add}$ is newly instantiated, then
        $\cA = \cA \cup \{A_{add}\}$ and $\cO = \cO \cup \{A_i^0
        < A_{add} < A_i^*\}$ (otherwise $\cA$ and $\cO$ remain unchanged).
  \item \textbf{Update goal set:} Let $\mathtt{agenda}$ =
        $\mathtt{agenda}$ - $\{ \langle \val_i , A_{need} \rangle \}$.
        If $A_{add}$ is newly instantiated, then for each of its
        pre/prevail conditions $Q$, add $\langle Q, A_{add} \rangle$ to
        $\mathtt{agenda}$.
  \item \label{step:prevent} \textbf{Threat prevention:} If $A_{add} = A(\nu^{j}_i)$,
        $j>1$, then, for each $A \in \cA$, s.t. $\nu^{j-1}_i$ belongs
        to the prevail conditions of $A$, add $\{A < A(\nu^{j}_i)\}$ to
        $\cO$. 
   \item \textbf{Recursive invocation:}
        \POP($\langle \cA,\cO,\cL \rangle, \mathtt{agenda}, \Lambda$),
        where $\mathtt{agenda}$ is topologically ordered (based on the causal graph
        with respect to the precondition part of each pair).
\end{enumerate}
\end{minipage}
}
  \caption{\POP\ algorithm}
  \label{fig:pop}
\end{figure*}



\begin{theorem}
  \label{t:polytree}
  A given problem instance with a polytree causal graph is solvable if
  and only if, for each $v\in\cV$, {\sc forward-check} succeeds in constructing the
  maximal sequence $\sigma(v)$.
  % the maximal sequence
  % $\sigma(v)$ created by {\sc forward-check} starts with $v^0$ and ends with $v^*$.
\end{theorem}

{\sc forward-check} fails if and only if at least one of the calls to
the {\sc determine-max-sequence} procedure fails. In turn, a call to
{\sc determine-max-sequence} on a variable $v$ fails if and only if
the initial and the goal values of $v$ are different but there is no
way to change the value of $v$ even once. Thus, if {\sc forward-check}
fails, then no plan exists.
  
To prove the opposite direction we proceed as follows: We define the \POP\ 
algorithm (POP for polytree causal graphs) and show that it will succeed
without backtracking if {\sc forward-check} succeeds.\footnote{For a short
  review of the POP algorithm, the corresponding formalism, and the description
  of the initial call to the algorithm, we refer the reader to Appendix A.}
\POP\ is described in detail in Figure~\ref{fig:pop}, and it works as follows:
First, let us expand each sequence of operator instances $\Gamma_i$ by
$A(\nu^1_i)$ ($A(\sb^1_i)$) which will stand for the dummy operator $A^0_i$.
(Recall that up until now, only operators of the form $A(\nu^j_i)$ for $j>1$
were defined.) The algorithm maintains a goal agenda sorted based on the causal
graph structure: parent variables appear after their descendents. At each
point, the next agenda item is selected; if it requires achieving some value
for $v_i$ we add the corresponding operator to the plan with the desired effect
(step~\ref{step:simple}). Actually, if we would be ready to accept plans with
possible redundant steps, we can omit the next step~\ref{step:nonsimple} from
the algorithm by assuming that the goal value of each variable $v$ is the last
element of the maximal sequence $\sigma (v)$.  However, if we would like our
plan to be irreducible, then a careful decision about the really required
number of value changes of each variable is required.  This decision is
captured in step~\ref{step:nonsimple} by analysis of the value changes of a
variable $v_i$ that were found necessary in the previous iterations of the
algorithm in order to satisfy the predecessors of $v_i$ in the causal graph.
Note that the agenda is sorted with respect to some reverse topological
ordering of the causal graph, thus if an operator affecting $v_i$ was selected
from the agenda then no operator affecting some predecessor of $v_i$ in the
causal graph will appear on the agenda until the end of the algorithm. No
threats arise in \POP, and the ordering constraints are consistent.



\begin{lemma}
\label{L1}
If {\sc forward-check} was successful then \POP\ will return a valid plan.
\end{lemma}

\begin{proof} 
%\textbf{(Lemma \ref{L1})}
The lemma will follow from the following claims:
\begin{enumerate}
\item For every agenda item, there exists an operator that has it as an effect.
\item There are no threats in the output of \POP.
\item The ordering constraints in $\cO$ are consistent.
\item The agenda will be empty after a polynomial number of steps.
\end{enumerate}
For the proof see Appendix~\ref{app:proofs}, p.~\pageref{aL1}.
\end{proof}

Recall that, for simplicity of presentation, we assumed that the goal
values are specified for all state variables (single goal state), i.e.
$Goal \in \cD(v_1)\times\ldots\times\cD(v_n)$.  Now we show that the
presented approach, with minor modifications, works for a set of
possible goal states as well, if such a set is specified by a partial
assignment on $\cV$, i.e. $Goal \in
\cD^+(v_1)\times\ldots\times\cD^+(v_n)$. Note that the latter assumption is
widely accepted in the planning literature.

First, no modifications should be done in processing variables that
are specified by $Goal$. Now, for each variable $v$, such that $v^*$ is not
specified by $Goal$, the modifications are as follows:
\begin{enumerate}
\item The graph $G(v)$ will consist of exactly $n$ nodes.  This
  is correct since (i) according to Lemma~\ref{l1}, $n$ changes of $v$
  have to be sufficient, and (ii) any value change of $v$ can be its
  last value change.

\item No changes in construction of $G'(v)$ and $G'_e(v)$.

\item In the procedure {\sc determine-max-sequence}:
  \begin{enumerate}
  \item In step~\ref{step:mod1}, determine the longest path
    from the dummy source node to {\em any} other node in the graph.
  \item In step~\ref{step:mod2}, {\em always} return success.
  \end{enumerate}
  Again, this is correct since any value change of $v$ can be its last
  value change, and, in particular, $v$ may remain unchanged in a plan
  for a given problem.
\end{enumerate}

Finally, the \POP\ algorithm starts with a null plan that contains
the end operator $A_i^*$ only if $v_i^*$ is specified by $Goal$.



\section{Directed-Path Singly Connected and General DAGs}
\label{S:polytree}
In this section we analyze planning complexity in face of more
complicated causal graphs. First, we show that when the causal graph
is directed-path singly connected even plan existence is {\sc np}-complete.  Second,
we show that for general causal graphs the situation is even worse.
Finally, we characterize an important parameter of the causal graph
affecting planning complexity, which allows us to extend the class of
problems which are in {\sc np}.
%We also show that this problem
%remains hard even if the indegree of causal graph's nodes is bounded
%by a low constant.

\begin{theorem}
\label{t:bh-nphard}
  Plan existence for \strips\ planning problems with unary operators and
  directed-path singly connected causal graph is {\sc np}-complete.
\end{theorem}

\begin{proof}
  For the proof see Appendix~\ref{app:proofs}, p.~\pageref{at:bh-nphard}.
\end{proof}

Note that node indegree in the causal graph of the problem created in
the proof of Theorem~\ref{t:bh-nphard} is bounded by 6. The hardness
for directed-path singly connected causal graphs with maximal indegree lower than 6 is
thus open.





%\section{General DAGs}
%\label{S:dag}
The directed-path singly connected structure of the causal graph turns out to
be crucial for guaranteeing reasonable solution times. As we now show, there
are solvable propositional planning problems with an arbitrary acyclic (DAG)
causal graph that have minimal solutions of exponential size.  Analysis of this
class of problems points to the reason for such provable intractability. This
allows us to characterize an important parameter of the causal graph affecting
planning complexity and to extend the class of problems which are in {\sc np}.
However, all these restricted problems are still {\sc np}-complete.

\begin{theorem}
\label{t:hnp}
Plan generation for general \strips\ planning problems with unary operators
and acyclic causal graph is provably intractable, i.e.~it is harder than {\sc np}.
\end{theorem}

This theorem follows from
Theorem~5.4~in~\cite{Jonsson:Backstrom:amai98}, 
that shows that plan
generation for the 3S problem class is provably intractable.
The point is that the upper bound for $\minplan$,
presented in Eq.~\ref{eq:ubound}, can be exponential in the size
of the input in this case. First, we show by example that
this upper bound can be achieved, then we 
present some analysis of the reasons for this intractability.

The following example shows that an exponential upper bound can be
achieved. It was used in the proof of
Theorem~5.4~in~\cite{Jonsson:Backstrom:amai98}, and was originally
presented in a different context by B{\"a}ckstr{\"o}m and
Nebel~\scite{Backstrom:Nebel:ci95}.  Consider a propositional planning
problem with $|\cV| = n$, where, for $1\leq i\leq n$, $\cD(v_i) =
\{0,1\}$ and $\parents (v_i) = \{v_1,\ldots v_{i-1}\}$.  The operator
set $\Lambda$ consist of $2n$ operators $\{A_1, A_1',\ldots
A_n,A_n'\}$ where
%{\footnotesize
\begin{eqnarray*}
  && \pre (A_i)[j] = \post (A_i')[j] = \sset{0\ \ \ {\mathrm{if}}\ j=i\\
                                             \su\ \ \ {\mathrm{otherwise}}}\\
  && \pre (A_i')[j] = \post (A_i)[j] = \sset{1\ \ \ {\mathrm{if}}\ j=i\\
                                             \su\ \ \ {\mathrm{otherwise}}}\\
%  &&\pre (A_i) = \post (A_i') = 0 \;\;\;\; \pre (A_i') = \post (A_i) = 1\\
  &&\prv (A_i)[j] = \prv (A_i')[j] = \sset{0\ \ \ {\mathrm{if}}\ j<i-1\\
                                 1\ \ \ {\mathrm{if}}\ j=i-1\\
                                 \su\ \ \ {\mathrm{otherwise}}}
\end{eqnarray*}
%}
It is easy to see that the causal graph of this problem forms a DAG
(see Figure~\ref{fig:hamilton}), and an instance of this planning
problem with the initial state $\langle 0,\dots,0 \rangle$ and the
goal state $\langle 0,\dots, 0, 1 \rangle$ has a unique minimal
solution of length $2^n-1$ corresponding to a Hamilton path in the
state space.

\begin{figure}[htb]
  \begin{center}
    \vspace{0.5cm}
    \mbox{
    \xymatrix{
    *+++[o][F]{V_1} \ar[r] \ar@/^2pc/[rrr] \ar@/^3pc/[rrrr] & 
    *+++[o][F]{V_2} \ar@/_1pc/[rr] \ar@/_2pc/[rrr] & \ldots & 
    *++[o][F]{V_{n-1}}  \ar[r] & *+++[o][F]{V_{n}}
    }
  %    \includegraphics[width=3in]{../images/upolytree/example.eps}
  }
  \end{center}
    \vspace{0.5cm}
  \caption{Causal graph for the proof of Theorem~\ref{t:hnp}}
  \label{fig:hamilton}
\end{figure}


Now we show that this escalation in complexity can be ``parametrized''
by the form of the causal graph.

\begin{lemma}
  \label{l:paths}
  For any solvable problem instance $\Pi$ with an acyclic causal graph
  over $n$ variables, for any variable $v$, we have that:
  \[
  \Must (v_i) \leq 1\; +\; \sum_{j=i+1}^n \rho(v_i, v_j)
  \]
  where $\rho(v_i, v_j)$ denotes the total number of
  different, not necessary disjoint, paths from $v_i$ to $v_j$,
  where variables are ordered via a topological
  sort of the causal graph.
\end{lemma}

\begin{proof}
  The proof is by induction on $i$. For $i = n$ it is obvious that
  $\Must (v_n) \leq 1$. Now we assume that the lemma holds for any
  $i>k$, and prove it for $i=k$. Without loss of generality, assume
  that $\sons (v_k) \neq \emptyset$. Otherwise, we simply have
  that $\Must (v_k) \leq 1$.

  The proof is straightforward:
  \begin{eqnarray*}
    \Must (v_k) & \stackrel{Eq.~\ref{eq:must}}{\leq} &
                  1\ +\ \sum_{v_{i_k}\in\lsons (v_k)} \Must (v_{i_k}) \leq \\
                &\stackrel{I.H.}{\leq} &
                  1 + |\sons (v_k)| + \sum_{v_{i_k}\in\lsons (v_k)}{\sum_{\hspace{0.3cm}j=i_k+1}^{n}{\rho(v_{i_k},v_j)}} =\\
                & = & 1 + \sum_{j=k+1}^n \rho(v_k, v_j)
  \end{eqnarray*}
\end{proof}

\commentout{
%% UPDATED
Now we show that this escalation in complexity can be ``parametrized''
by the form of the causal graph. Our analysis is based on achieving an
upper bound on $\newMust (v)$, similar to Eq.~\ref{eq:newmust} in the
proof of Lemma~\ref{l1} for directed-path singly connected DAGs. For the general
problems considered in Theorem~\ref{t:hnp}, we have:
  \[
  \newMust (v) \leq \Must (v) + \rho_{v\rightsquigarrow v_n}
  \]
  where $\rho_{v_i\rightsquigarrow v_j}$ denotes the total number of
different, not necessary disjoint, paths from $v_i$ to $v_j$.
This means that for a given propositional planning
problem with acyclic causal graph, and 
with the variables numbered according to a topological
sort induced by the causal graph,
\begin{equation}
\label{eq:paths}
   \Must (v_i) \leq \sum_{j=i+1}^n \rho_{v_i\rightsquigarrow v_j}
\end{equation}
Therefore, given such a problem $\Pi$, the upper bound for
$\minplan(\Pi)$
depends on the number of different paths between the nodes in the
causal graph.
%% END UPDATED
}

Lemma~\ref{l:paths} entails that the upper bound for $\minplan(\Pi)$
for a general planning problem with unary operators and acyclic causal
graph depends on the number of different paths between the nodes in
the causal graph.
An immediate conclusion
% of Theorem~\ref{t:hnp}
is that there is a significant class of problems
with an acyclic causal graph for which planning is in {\sc np}. Let
a DAG be called \emph{max-$\delta$-connected} if the
number of different directed paths between every two nodes in this graph is
bounded by $\delta$.

\begin{theorem}
\label{c:restr}
  Plan generation for \strips\ planning problems with unary operators and
  max-$\delta$-connected causal graph is {\sc np}-complete if
  $\delta$ is polynomially bounded.
\end{theorem}

\begin{proof}
  Membership in ${\sc np}$ is straightforward:
  If the variables of a given problem $\Pi$ are considered in a topological
  ordering induced by the causal graph, then from Lemma~\ref{l:paths}
  follows that, for any variable $v_i$, $\Must (v_i) \leq \delta n$.
  In turn, from this follows that $\minplan (\Pi ) \leq \delta n^2$,
  and thus, if $\delta$ is polynomially bounded, then we can guess
  a minimal plan for $\Pi$ that could be verified in polynomial time.
  
  The hardness follows from Theorem~\ref{t:bh-nphard} that shows that even if
  the causal graph is max-1-connected (directed-path singly connected), then
  plan existence (and thus plan generation) is hard.
\end{proof}

\section{Serializable Subgoals}
\label{S:serial}
A set of subgoals is defined to be \emph{serializable}
\cite{Korf.AI.87} if there exists an ordering among the subgoals such
that the subgoals can always be solved sequentially without ever
violating a previously solved subgoal in the order. 
Naturally, not all collections of subgoals are serializable -- sometimes
it may be necessary to interleave plans for achieving different goals.
However, when a problem instance is {\em serially decomposable}, it is
possible to design a set of macro-operators with respect to
which the subgoals {\em are\/} serializable~\cite{Korf.AI.85}.

A problem instance is serially decomposable if there exists some
ordering of the state variables for which the effect of each operator
on each state variable depends only on that state variable and
previous state variables in the ordering.  Unfortunately,
Bylander~\scite{Bylander.AAAI.92} shows that determining serial
decomposability of a problem is {\sc pspace}-complete.

One major open problem put forth by Bylander in this context is: {\it
  If a problem is known to be serially decomposable, how difficult is
  it to determine whether a given instance is solvable?}  As far as we
know, the only work in this direction was done by Chalasani {\em et
  al.}~\scite{Chalasani:et.KR.91}, where the serial decomposability of
the ``general permutation problem'' was considered.  In particular,
they showed that this problem is in {\sc np}, but it is unknown
whether it is {\sc np}-hard.  Recently, some complementary results for
Bylander's question were presented K\"oehler and
Hoffmann~\scite{Koehler:Hoffmann:jair00}.  Our results shed more light
on this question: Any problem instance based on a unary operator
domain whose causal graph is acyclic is serially decomposable.
Therefore, it can be concluded that finding a solution for serially
decomposable problems may require exponential time (i.e., the problem
is in {\sc exptime}).
%is {\sc pspace}-hard.
However, Bylander's question is about plan existence.  In that case,
Theorem~\ref{t:hnp} does not apply, and we can only apply our {\sc
  np}-hardness result (for directed-path singly-connected graphs), since it
addresses plan existence as well.

Weld~\scite{Weld:aimag99} hypothesized that: (1) If the underlying
causal graph of the planning problem is acyclic, then a serialization
ordering on the subgoals of the problem is obvious; (2)
\emph{Serialized} subgoals could be solved extremely quickly because
no backtracking is required between them.  \commentout{
\begin{enumerate}
  \item If the underlying causal graph of the planning problem is acyclic,
    then a serialization ordering on the subgoals of the problem is obvious.
  \item \emph{Already serialized} subgoals could be solved
    extremely quickly because no backtracking is required between them.
\end{enumerate}
}
Although the first observation sounds intuitive, our results suggest
that it is rarely true. The acyclicity of the causal graph implies
serializability, but in most of the cases its structure does not
provide us sufficient information about the actual serialization
ordering. Even when the causal graph is a directed tree one must think
first before choosing an ordering. Likewise, our results imply that
when the causal graph does not form an undirected tree determining a
subgoal ordering is {\sc np}-complete, and if the causal graph is not
directed-path singly connected, the problem is even more complex.  

The second observation is not always true either. The problem is that
it is important to determine not only the serialization ordering over
the subgoals, but also the exact strategies for achieving them. As we
showed, in certain cases, a problem with $n$ serializable subgoals
requires an exponentially long solution. When the domain
variables are not binary, the situation is even worse -- some of the
corresponding complexity results can be derived from the computational
analysis of Domshlak and Dinitz~\scite{Domshlak:Dinitz:ecp01}.



\section{Connection with Related Work on Planning Complexity}
\label{S:related}
The idea of analyzing and exploiting structural properties is not new
to classical planning, and in the last few years a number of important
results have emerged.  Generating plans in the context of the \strips\ 
representation language was shown by Bylander~\scite{Bylander.AI.94} to
be {\sc pspace}-complete.  Despite this fact, the
existence of many successful planning systems, especially in recent
years, demonstrates that planning is possible and practical for a wide
list of domains.  Bylander argues that the large gap between the
theoretical hardness of planning and its practical success stems from
the use of domain-dependent problem analysis and algorithms.
Consequently, various authors have explored the existence of some
constrained problem classes for which planning is easier.
%CD removed:
% We believe that many ``natural'' planning problems are likely to have
% special structure and special properties that can be utilized,
% implicitly or explicitly, to generate plans quickly. This work is part
% of our effort to characterize structural properties of planning
% problems that impact the complexity of plan generation.

In this section we shortly overview some of the major, previous
results on complexity of planning, and discuss their relationship to
the results presented in this paper.
% We believe that connecting
% previous and new results is essential in order to better understand
% the novelty of latter, and its exact placement in the global map of
% research on planning complexity.  Note that we do not strive to
% provide a comprehensive survey on planning complexity.  Therefore, the
% previous results are discussed here only at the level of details that
% required to understand their relationship to our results.
For a more detailed presentation of the previous results discussed
below we refer the reader to the original papers.


\subsection{Local Syntactical Restrictions}
In his seminal paper, Bylander~\scite{Bylander.AI.94} presents a
number of complexity results for propositional planning, analyzing
different planning problems based on the type of formulas used, the
number and type (positive/negative) of operator pre- and
postconditions, etc. The work of Bylander is extended by some
interesting, complementary results by Erol {\em at
  al.}~\scite{Erol:Nau:Subramanian:ai95}.  For example, Bylander shows
that propositional planning in domains where each operator is
restricted to have positive preconditions and one postcondition only
is tractable.  Generally, extremely severe restrictions on operators
are required to guarantee tractability, or even membership in {\sc
  np}.  Note that Bylander~\scite{Bylander.AI.94} and Erol {\em et
  al.}~\scite{Erol:Nau:Subramanian:ai95} focuses on {\em local
  syntactical\/} properties of operators, i.e., properties of single
operators.

The only syntactic restriction that we pose on the planning problems
in this paper is the unarity of the operators. Determining plan
existence for this, apparently easier class of problems was shown by
Bylander to be as hard as general propositional planning, i.e. {\sc
  pspace}-complete. Note that this result by itself does not entail
our Theorem~\ref{t:hnp}, since planning problems with unary operators
may induce causal graphs with cycles.  Therefore, none of our results
is entailed by the results presented by
Bylander~\scite{Bylander.AI.94} and Erol {\em et
  al.}~\scite{Erol:Nau:Subramanian:ai95}.


\subsection{Global Syntactical Restrictions}

B{\"a}ckstr{\"o}m and Klein~\scite{Backstrom:Klein:ijcai91,Backstrom:Klein:ci91},
and, subsequently, B{\"a}ckstr{\"o}m and Nebel~\scite{Backstrom:Nebel:ci95}, consider
other types of restrictions, but using a more refined model (the
{\em SAS\/} formalism) in which:
\begin{enumerate}
\item The state variables are multi-valued, and 
\item Two types of preconditions are considered: {\em prevail\/}
  conditions, which are variable values that are required prior to the
  execution of the operator and are not affected by the operator, and
  {\em preconditions\/}, which are affected by the operator.
\end{enumerate}
%CD moved to Section 2.1
%Hence, prevail conditions, such as having a
%visa, are needed in order to apply an operator, such as Enter-USA, but
%their values do not change after the operator is applied.
In general, four different restrictions were considered in these works:
\begin{itemize}
  \item[(P)] {\em Post-uniqueness}: For each effect there is at most one
    operator that achieves this effect. In other words, desired effects
    determine operators to be used in a plan. Formally,
    a problem instance is post-unique if and only if, for each $v_i\in\cV$
    and $x\in\cD(v_i)$, there is at most one operator $A\in\Lambda$ such that
    $\post(A)[i]=x$.
    
  \item[(S)] {\em Single-valuedness}: At most one value of each state
    variable appears in the prevail conditions of the operators. For
    instance, if a certain operator requires the light to be on (as a
    prevail condition), no other operator can use the prevail
    condition that the light is off. Formally, a problem instance is
    single-valued iff there exist no two operators $A,A'\in\Lambda$
    and $v_i\in\cV$ such that $\prv(A)[i] \neq \su$, $\prv(A')[i] \neq
    \su$, and $\prv(A)[i] \neq \prv(A')[i]$.

  \item[(U)] {\em Unariness}: Each operator affects only one state variable.

  \item[(B)] {\em Binariness}: All state variables have exactly two possible values, i.e.
    all state variables are propositional.
\end{itemize}

All these four properties are syntactical. However, the properties P
and S differ from the properties U and B by the fact that they have a
{\em global} nature: Post-uniqueness and single-valuedness restrict
not the form of the operators, but a global property of the whole set
of operators. B{\"a}ckstr{\"o}m and Nebel~\scite{Backstrom:Nebel:ci95}
showed that US (unariness and single-valuedness) is the extreme
problem class for which plan generation is polynomial.~\footnote{For a
  thorough analysis of the complexity of SAS planning, we refer to
  B{\"a}ckstr{\"o}m and Nebel~\scite{Backstrom:Nebel:ci95}.}


\commentout{ For example, B{\"a}ckstr{\"o}m and
  Klein~\scite{Backstrom:Klein:ijcai91} have shown that when operators
  have a single effect ({\em unary}), no two operators have the same
  effect ({\em post-uniqueness}), and each variable can be affected
  only in a unique context of prevail conditions ({\em
    single-valuedness}) then the planning problem can be solved in
  polynomial time.  However, as argued
  in~\cite{Erol:Nau:Subramanian:ai95}, the properties of SAS required
  for tractability or {\sc np} membership are so strict that it is
  hard to find domains satisfying them. The most severe restriction
  for practical applications is {\em single-valuedness\/}. For
  example, we could not model a problem in which one operator,
  affecting a particular engine, can be applied only when a certain
  valve is open, and another operator, affecting the same engine, can
  be applied only when the same valve is closed. For a thorough
  analysis of the complexity of SAS planning, see
  \cite{Backstrom:Nebel:ci95}.  }


% The plan existence complexity map
% with respect to these restrictions is presented in Figure~\ref{fig:backstrom}.

% \begin{figure}[H]
%     \begin{center}
%     \mbox{
%       \includegraphics[width=3in]{../images/backstrom.eps}}
%   \end{center}
%   \caption{Complexity of plan existence for SAS
%     and restrictions~\cite{Backstrom:Nebel:ci95}.}
%   \label{fig:backstrom}
% \end{figure}

The problems that we analyzed in this paper belong to the problem
class UB, by definition. As we already mentioned, even determining
plan existence for this class of problems is {\sc pspace}-complete.
Now consider the problem class PUB.  B{\"a}ckstr{\"o}m and
Nebel~\scite{Backstrom:Nebel:ci95} showed that: (i) PUB has
instances with exponentially long minimal solutions, thus plan
generation for PUB is requires exponential time; (ii) existence of
bounded length plans for PUB is strongly {\sc np}-hard; and (iii) the
complexity of general plan existence for PUB is still an open
question. Informally it means that strengthening restrictions from UB
to PUB does not reduce the complexity significantly, at least from the
practical point of view.

\begin{proposition}
\label{p:treeub}
Every UB problem instance with a tree causal graph is either
post-unique, or can be transformed into an equivalent post-unique
problem instance in (low) polynomial time. Thus, TreeUB $\subset$ PUB.
\end{proposition}

% NEW-JAIR
\begin{proof}
  Consider a UB problem with a tree causal graph, and suppose that it
  is not post-unique. It means that there exist a variable $v\in\cV$,
  with $\cD(v) = \{v',v''\}$, such that there exist two operators
  $A_1,A_2\in\Lambda_{v}$ that change the value of $v$ from $v'$ to
  $v''$, and $\prv(A_1) \neq \prv(A_2)$.
  
  From the assumption that the causal graph forms a tree it follows that
  $|\parents (v)| \leq 1$. If $\parents (v) = \emptyset$, then it is easy to
  see that the existence of such a pair of operators is simply impossible.  Therefore,
  let $\parents(v) = \{w\}$, where $\cD(w) = \{w',w''\}$. Without loss of
  generality assume that $\prv(A_1)[w] = \{w'\}$, $\prv(A_2)[w] = \{w''\}$.
  Otherwise, if, for instance, $\prv(A_1)[w]=\su$, then it is easy to see
  that $A_2$ is a redundant operator.  
  
  Observe that in this case, prevail dependence of $v$ on $w$ is
  redundant: We can replace the pair of operators $A_1,A_2$ in
  $\Lambda$ by a single operator $A$ that changes the value of $v$
  from $v'$ to $v''$ without any prevail condition. The replacement of $A_1,A_2$
  by $A$ brings us to an {\em equivalent} problem instance in which the operator
  set $\Lambda_v$ is post-unique. This way we continue to process iteratively all such
  "problematic" variables $v$ until we arrive at a post-unique problem instance.
\end{proof}
% end NEW-JAIR

\commentout{
\begin{proof}
  Consider a UB problem with a tree causal graph, and suppose that it
  is not post-unique. It means that there exist a variable $v\in\cV$,
  with $\cD(v_i) = \{v',v''\}$, such that there exist two operators
  $A_1,A_2\in\Lambda_{v}$ that change the value of $v$ from $v'$ to
  $v''$, and $\prv(A_1) \neq \prv(A_2)$.  Without loss of generality
  assume that both $\prv(A_1) \neq \su$ and $\prv(A_2) \neq \su$.
  Otherwise, if, for instance, $\prv(A_1)=\su$, then it is easy to see
  that $A_2$ is simply redundant.  If so, then
  $\parents (v) \neq \emptyset$, i.e. $\parents(v) = \{w\}$, where
  $\cD(w) = \{w',w''\}$, and $\prv(A_1) = \{w'\}$, $\prv(A_2) =
  \{w''\}$.  Note that $|\parents (v)| \leq 1$ follows from the
  assumption that the causal graph forms a tree.
  
  Observe that in this case, prevail dependence of $v$ on $w$ is
  redundant: We can replace the pair of operators $A_1,A_2$ in
  $\Lambda$ by a single operator $A$ that changes the value of $v$
  from $v'$ to $v''$ without any prevail condition. The replacement of $A_1,A_2$
  by $A$ bring us to an {\em equivalent} problem instance in which the operator
  set $\Lambda_v$ is post-unique. This way we continue to process iteratively all such
  "problematic" variables $v$ until we arrive to a post-unique problem instance.
\end{proof}
}

\begin{proposition}
\label{p:treeub2}
  There are UB problem instances with a tree causal graph
  that are not single-valued, thus TreeUB $\not\subset$ UBS.
\end{proposition}

\begin{proof}
The proof of Proposition~\ref{p:treeub2} is straightforward: Consider
a variable $v\in\cV$, $\cD(v)=\{v',v''\}$, such that $\sons(v) =
\{u,w\}$. It can be the case that any value change of $u$
will be prevailed by $v'$, while any value change of $w$ will be
prevailed by $v''$. Therefore, restricting causal graphs
even to trees does not entail single-valuedness.\footnote{Using the
  simple construction technique from the proof of Proposition~\ref{p:treeub}
  it can be shown that restricting causal graphs to directed chains only does entails
  single-valuedness. However, this case is too restrictive.}
\end{proof}

Propositions~\ref{p:treeub} and~\ref{p:treeub2} show that TreeUB is a
polynomial subclass of PUB that is not entailed by any tractability
results of B{\"a}ckstr{\"o}m and Nebel~\scite{Backstrom:Nebel:ci95}.

\begin{proposition}
\label{p:polytreeub}
  There are UB problem instances with a polytree causal graph
  that are neither single-valued, nor post-unique.
\end{proposition}

\begin{proof}
  The proof is straightforward:
  Consider a planning problem with a polytree causal graph,
  such that there exist a variable $v\in\cV$ with $\parents(v) = \{u,w\}$,
  and the following operator set $\Lambda_v$:

  \begin{center}
  \begin{tabular}{ccc}
    $\pre$ & $\post$ & $\prv$\\
    \hline
    $v'$ & $v''$ & $\{u',w''\}$\\
    $v'$ & $v''$ & $\{u'',w'\}$\\
    $v''$ & $v'$ & $\{u',w'\}$\\
    $v''$ & $v'$ & $\{u'',w''\}$
  \end{tabular}
  \end{center} 

  Clearly, any problem instance with such $\Lambda_v \subseteq \Lambda$
  is neither single-valued, nor post-unique, since (i) there is more than
  one operator achieving any value of $v$, and (ii) both values of $u$ (and
  both values of $w$) appear in prevail conditions of the operators in $\Lambda_v$.
  Note that the maximal indegree of such a polytree can be minimal, i.e. equal to 2.
  Thus, the proposition is valid for any polytree that is not a tree.
\end{proof}

From Proposition~\ref{p:polytreeub} it follows that Theorems~\ref{t:polytree}
and~\ref{c:restr} introduce new polynomial and {\sc np}-easy subclasses of
the UB problem class, respectively.



\subsection{Structural Restrictions in Propositional Planning}
Jonsson and B{\"a}ckstr{\"o}m~\scite{Jonsson:Backstrom:amai98} present
the 3S class of planning problems. This class is most closely related
to the problems examined in this paper, since it defines a special
subclass of problems with binary variables, unary operators and
acyclic causal graphs. The 3S problem class is defined by posing some
additional, relatively severe, restrictions on the problem's operator
set: Each variable $v$ in a 3S problem instance is required to be
either (i) {\em static}, i.e., unchangeable; (ii) {\em symmetrically
  reversible}, i.e., for each operator $A$ affecting $v$, there exist
an operator $A'$ affecting $v$ with the same prevail conditions and
the opposite effect; or (iii) {\em splitting}. For the formal
definition of the splitting property we refer to Jonsson and
B{\"a}ckstr{\"o}m~\scite{Jonsson:Backstrom:amai98}.  Informally, if a
binary variable $v$ is splitting then the problem instance can be
split into three, well-defined subproblems that can be solved
independently.  For this class of planning problems it was shown that
plan existence can be determined in polynomial time, while plan
generation is provably intractable, since there are instances of 3S
with exponentially long minimal solutions. In particular, the problem
instance that we used in the proof of Theorem~\ref{t:hnp} is in 3S.


The complexity analysis by Jnonsson and
B{\"a}ckstr{\"o}m~\scite{Jonsson:Backstrom:amai98} is somewhat unique
in the research on complexity of propositional planning, since, to the
best of our knowledge, this was the only attempt to exploit not only
syntactical restrictions on the operator set, but also some structural
restrictions on interaction between the variables. Our analysis can be
seen as continuing this direction by looking on the structural
restrictions {\em only}. We believe that eliminating the marginal
effect of the problem structure on the problem's (potential) hardness
will allow us to understand better the connection between the
component interactions topology, and the potential complexity of the
problem.


\subsection{Structural Restrictions in Multi-valued Formalisms}
When the variables are no longer propositional, some additional
properties of the problems can be identified, and, possibly,
exploited. In particular, additional internal structures of the problem
can be analysed.

Jonsson and B{\"a}ckstr{\"o}m~\scite{Jonsson:Backstrom:ai98a}
analyze different properties of a multi-valued problem structure,
which is called the {\em domain transition graph\/}.
Such a structure is defined for each state variable
of the problem, and it describes 
% another class of structural properties by examining {\em domain
% transition graphs\/} which describe
possible transitions between different values of this variable.
%the same multi-valued (non-propositional) variable.
The domain transition graph of a state variable $v$ is a directed
labeled graph $G_v=(V,E)$, where $V$ is associated with the $v$'s set
of possible values, $\cD(v)$, and $(x,A,y)\in E$ if and only if the operator $A$
can be applied at some state in which $v=x$, and its application
results in a state in which $v=y$ holds. 

Jonsson and B{\"a}ckstr{\"o}m identify sets of structural restrictions
on domain transition graphs which make planning instances tractable.
Roughly, the properties are the following: (1) The problem domain is
{\em interference-safe}, i.e., each operator is either unary or
irreplaceable with respect to every variable it affects.  An
operator $A$ is {\em irreplaceable\/} with respect to a variable $v$ if the
removal of all edges from $G_v$ that stem from $A$ disconnects some
weakly connected component of $G_v$. (2) For every variable $v$, the graph
$G_v$, restricted to the set of values that appear in the prevail
conditions of some operators, is acyclic.  (3) Any sequence of
operators annotating a path from $x$ to $y$ in the domain transition
graph of $v$, is stronger than all shortest such sequences connecting
$x$ and $y$. Here, a sequence $A_1,\ldots,A_k$ is {\em stronger} than
$A'_1,\ldots,A'_l$ if there is a subsequence $A_{i_1},\ldots, A_{i_l}$
of $A_1,\ldots,A_k$ such that for every $1\leq j\leq l$, the prevail
conditions of $A'_j$ are a subset of the prevail conditions of
$A_{i_j}$. Jonsson and B{\"a}ckstr{\"o}m present a map of the
computational complexity of problems with different restrictions,
displaying the frontier between the tractable and intractable cases.

Each domain transition graph combines and structures the influence of
many operators on a particular variable. Therefore, they provide us a
more global picture than the operator set alone.  Hence, in spite of
the fact that domain transition graphs do not capture the relationship
between different variables, they do allow us to express some
structural properties that address interactions between the variables (e.g., see
property (2) above). 

% NEW-JAIR
Observe that domain transition graphs are not very informative in the case of
propositional planning, since they are only distinguish between the variables
that can be changed only in one direction and the variables that can be changed
in both directions. Although this property of domain transition graphs
allows to distinguish between the polynomial
planning with only positive postconditions, and the {\sc pspace}-complete
planning with both positive and negative postconditions~\cite{Bylander.AI.94},
it seems to be not very helpful in further hierarchical refinement of the
propositional planning complexity.
% end NEW-JAIR
On the other hand, there is no a priori reason why the causal graphs
will not be informative in the multi-valued case.  Exploiting the
properties of causal graphs, together with the properties of domain
transition graphs, seems to be a natural direction to extend the work
presented in this paper.  The recent work of Domshlak and
Dinitz~\scite{Domshlak:Dinitz:ecp01} on multi-entity off-line
coordination can be seen as investigating connections between the
structure of the causal graph, together with the properties of the
domain transition graphs, and the complexity of the corresponding
problems in case of multi-valued domains. To the best of our
knowledge, this is the only work that was done with respect to such a
``mixed'' structural analysis, and a lot of work remains to be done.
For instance, combining various properties of the domain transition
graphs studied by Jonsson and
B{\"a}ckstr{\"o}m~\scite{Jonsson:Backstrom:ai98a}, with the properties
of the problem's causal graph is a direction for the further research.




\section{Summary and Future Work}
\label{S:summary}
We have shown that the form of the causal graph for \strips\ planning
problems with unary operators is an important factor in determining
the computational complexity of plan generation. In particular, we
have shown that a polynomial time algorithm exists for any problem
with a polytree causal graph and the node indegree bounded by a
constant.  More generally, this result shows that planning with
polytree causal graphs is at most (what is often referred to in the
Bayes nets literature as) locally exponential, i.e., it is exponential
in the maximal number of parents of a node.  Note that in 
hardware-control planning problems the maximal node indegree is
expected to be small, since prevail dependencies between the
variables reflect the direct interconnections between the
corresponding
hardware components.  Likewise we have shown that for a problem with
directed-path singly connected causal graph the maximal plan length is a low order
polynomial, but the problem is {\sc np}-complete.  More generally, we
have shown a relation between the number of paths between variables in
the causal graph and the computational complexity of the corresponding
planning problem.
Finally we have presented the impact of our results
on the question of complexity of planning problems with serializable
subgoals, and connected our work with previous results on planning
complexity.

% NEW-JAIR
Our work leaves a number of open questions with respect to purely syntactical,
and a mixture of both structural and syntactical restrictions on the planning
problems with unary operators. In the former case, one of the most important
directions is a further analysis of causal graphs with constantly bounded node
indegree. It turns out that complexity analysis for this class of problems will
be very helpful in understanding various computational properties of
CP-nets~\cite{BBHP.UAI99}. Although here we provided a partial answer for this
question, the general picture of the worst-case complexity for this class of
problems is not clear. For example, if the indegree of the causal graph is
known to be bounded by 2, and this is the only structural property of the
causal graph, it is even not clear whether this problem subclass is in {\sc
  np}.

In the latter case, various syntactical restrictions can be analysed together
with the form of the causal graph. For example, one may be interested in the
computational properties of the problems with acyclic causal graphs, and the
restriction that every operator has at most $\alpha$ prevail conditions, where
$\alpha$ is bounded by a constant. This, as well as many other related
questions with respect to various special cases of planning with unary
operators are of interest for the future work.
% end NEW-JAIR

\section*{Acknowledgments}
A preliminary version of this paper appeared in the Sixth
International Conference on Artificial Intelligence Planning and
Scheduling, April, 2002.  We would like to thank the three anonymous
reviewers for their extremely helpful comments. Ronen Brafman is
supported in part by the Paul Ivanier Center for Robotics Research and
Production Management.

\newpage
\appendix

\section{A Short Review of POP, Causal Links and Threats}
\label{app:pop}

We represent a plan as a tuple: $\langle \cA,\cO, \cL \rangle$, where
$\cA$ is a set of unary {\em operators}, $\cO$ is a set of {\em
  ordering constraints} over $\cA$, and $\cL$ is a set of {\em causal
  links}. For example, if $\cA = \{ A_1, A_2, A_3 \}$ then $\cO$ might
be the set $\{ A_1 < A_3, A_2 < A_3 \}$. These constraints specify a
plan in which $A_3$ is necessarily the last operator, but do not
commit to a particular order on $A_1$ and $A_2$. Naturally, the set of
ordering constraints must be consistent, i.e., there must exist some
total order satisfying them. A causal link has the form $A_p
\stackrel{\val_i}{\rightarrow} A_c$, where $A_p$ and $A_c$ are
operators and $\val_i$ is a possible value for some propositional
variable $v_i$. It denotes the fact that $A_p$ produces (i.e., has the
postcondition) $v_i=\val_i$ which is consumed by $A_c$ (i.e., used to
satisfy a pre- or prevail-condition of $A_c$). Causal links help us
detect whether one operator $A_t$ interferes with the work done to
enable the execution of some other operator $A_c$. In that case, $A_t$
is said to constitute a \emph{threat} to one of $A_c's$ causal links.
Formally, suppose that $\langle \cA,\cO, \cL \rangle$ is a plan, and
$A_p \stackrel{\val_i}{\rightarrow} A_c$ is a causal link in $\cL$.
Let $A_t$ be a different operator in $\cA$. We say that $A_t$
\emph{threatens} $A_p \stackrel{\val_i}{\rightarrow} A_c$ when the
following two criteria are satisfied:
%(i) $\cO \cup \{ A_p < A_t < A_c
%\}$ is consistent, and (ii) $A_t$ has $\neg \val_i$ as an effect.
\begin{itemize}
  \item $\cO \cup \{ A_p < A_t < A_c \}$ is consistent, and
  \item $A_t$ has $\neg \val_i$ as an effect.
 \end{itemize}
When a partial order plan $P$ contains threats, it is possible that
the goal will not be achieved by some (or all) of
the total order plans 
consistent with $P$'s ordering constraints.
To prevent this, the plan generator must check for threats
and remove them by adding one of two possible ordering constraints:
$A_t < A_p$ (demotion) or $A_c < A_t$ (promotion).

A tutorial introduction to POP  algorithms can
be found in~\cite{Weld:aimag94}.  POP is a regressive framework for
partial order planning that starts with the null plan and continuously
updates it by inserting new actions and removing threats.  This
process continues until the precondition and the prevail conditions of
every operator in the plan are supported by some causal link and no
threats exist. The first argument to POP is a plan and the second
argument is an agenda of goals that need to be supported by causal
links. Each item on the agenda is represented by a pair $\langle
\val_i , A\rangle$ where $\val_i$ is either pre- or prevail condition
of a plan action $A$.  The last argument to POP is the whole
collection of the operators defined by the planning instance.  The
initial call to POP contains the null plan, a specially initialized
agenda, and the operator set $\Lambda$ of the given problem.

In this paper we introduce a specialized, {\em deterministic} POP
algorithm that starts the planning process using a variant of the null
plan which encodes the planning problem. In particular, if the
planning instance has $v_1^*,\ldots,v_n^*$ as the goal then the
corresponding null plan has exactly $2n$ dummy unary operators,
$\cA=\{A_1^0,\ldots,A_n^0,A_1^*,\ldots,A_n^*\}$, $n$ ordering
constraints, $\cO=\{\{A_1^0 < A_1^*\},\ldots,\{A_n^0 < A_n^*\}\}$, and
no causal links, $\cL = \{\}$. For every $v_i \in \cV$, $A_i^0$ is the
corresponding "start" operator - it has neither pre- nor prevail
conditions, and its effect specifies the value of the variable $v_i$
in the initial state, which is denoted by $v_i^0$.  Similarly, $A_i^*$
is the "end" operator - it has no effect, no prevail conditions, but
its precondition is set to the value of $v_i$ in the goal state, which
in turn is denoted by $v_i^*$.\footnote{Actually, the goal state may
  not specify the values of all the variables, thus the number of the
  end operators can be less than $n$. However, for clarity of
  presentation, we leave this definition of the null plan.}  Our
description of the null plan is modified from that of
Weld~\scite{Weld:aimag94} to better suit the restriction to unary
operators. Likewise, the initial call to our POP algorithm contains
the agenda $\{\langle v_1^*,A_1^*\rangle,\ldots,\langle
v_n^*,A_n^*\rangle\}$.




\newpage
\section{Proofs and Auxiliary Results}
\label{app:proofs}

\begin{alemma}{L1}
  \label{aL1}
{\em If {\sc forward-check} was successful then \POP\ will return a valid plan.}
\end{alemma}

\begin{proof} 
%\textbf{(Lemma \ref{L1})}
The lemma will follow from the following claims:
\begin{enumerate}
\item For every agenda item, there exists an operator that has it as an effect.
\item There are no threats in the output of \POP.
\item The ordering constraints in $\cO$ are consistent.
\item The agenda will be empty after a polynomial number of steps.
\end{enumerate}

(1+4) 
The first claim follows from the success of the {\sc forward-check}
procedure. {\sc forward-check} implies
that for any $\nu_i^j \in \sigma (v_i)$ there is an operator instance
$A(\nu_i^j) \in \Gamma_i \cup \{A^0_i\}$. Therefore, if $\nu^j_i \in \sigma (v_i)$
then the existence of an appropriate $A_{add}$ is promised.

Assume to the contrary that $\nu^j_i \not\in \sigma (v_i)$ and, without
loss of generality, assume that this is the first iteration that it
happens. If so, then for each variable $u \in \sons (v_i)$, there is
no edge labeled by $\nu^j_i$ in the graph $G'(u)$, which is created by
the {\sc forward-check}. From this follows that $A_{need}$ cannot have
$\nu^j_i$ as a prevail condition, and thus $A_{need}$ has to affect the
variable $v_i$ itself. 
In this case either $A_{need} = A(\nu^{j+1}_i)$ or
$A_{need} = A^*_i$. 

Consider the former case: If $A_{need} = A(\nu^{j+1}_i)$
then $\nu^{j+1}_i$ was previously selected from the agenda. By our
assumption it means that $\nu^{j+1}_i \in \sigma (v_i)$, and it contradicts
our assumption that $\nu^j_i \not\in \sigma (v_i)$ since $\nu^j_i$ is a
predecessor of $\nu^{j+1}_i$ on $\sigma (v_i)$.

Now consider the last option that $A_{need} = A^*_i$. If $A_{add} =
A(\nu^j_i)$ then the goal value of the variable $v_i$ is consistent
with $\nu^j_i$, and $A(\nu^{j-1}_i) \in \cA$ (see
Step~\ref{step:carmel}). If $A(\nu^{j-1}_i) \in \cA$ then
$\nu^{j-1}_i$ was previously selected from the agenda. By our
assumption it means that $\nu^{j-1}_i \in \sigma (v_i)$. However, it
contradicts our assumption that $\nu^j_i \not\in \sigma (v_i)$ since
$\sigma (v_i)$, by definition, terminates with a node consistent with the
goal value of $v_i$.

In addition, since we have shown that the only operators added into $\cA$
are those from $\Gamma_i \cup \{A_i^0,A_i^*\}$, for $1 \leq i \leq n$,
the agenda will be empty after $O(n^2)$ steps.
% Since the agenda
% contains only value acquisitions of the variables that belong to the
% maximal sequences $\sigma(v_1),\ldots,\sigma(v_n)$, the
% first claim is true.

(2) Suppose that some operator
$A_t$ {threatens} $A_p\stackrel{\val_i}{\rightarrow} A_c$, i.e.,
\begin{itemize}
  \item $\cO \cup \{ A_p < A_t < A_c \}$ is consistent, and
  \item $A_t$ has $\neg \val_i$ as an effect.
\end{itemize}
For a given variable $v_i$, \POP\ forces the operators affecting $v_i$
as follows (Step~\ref{step:update}): 
\begin{equation}
\label{e:order1}  
  A^0_i \equiv A(\nu^1_i) < A(\nu^2_i) < \ldots  < A(\nu^x_i),\;\;\; x
  \leq \FeasibleMust (v_i)
\end{equation}
Thus $A_c$ can only be an operator with $\val_i$ as a prevail
condition. Note that $A_p$ and $A_t$ affect the same variable $v_i$.
In (1) we already showed that $\val_i = \nu^j_i \in \sigma (v_i)$. In
that case $A_t = A(\nu^l_i)$, $l > j$. However, if $\nu^j_i$ is a
prevail condition of $A_c$ then the ordering constraint $\{A_c <
A(\nu^{j+1}_i)\}$ was added to $\cO$ at Step~\ref{step:prevent}.  If
so then from Eq.~\ref{e:order1}, it follows that $\{A(\nu^l_i) <
A(\nu^{j+1}_i), A(\nu^{j+1}_i) < A(\nu^l_i)\}$, $l > j$, will be
implied by $\cO \cup \{ A_p < A_t < A_c \}$, and it contradicts with
the assumption that $\cO \cup \{ A_p < A_t < A_c \}$ is consistent.

(3) The ordering constraints are consistent if no two operators $A_i$
  and $A_j$ are such that $\cO$ implies $\{\{A_i < A_j\}, \{A_j <
  A_i\} \}$.  In what follows, $A_i$ will be used to denote an
  arbitrary operator affecting variable $v_i$.
  
  First note that each ordering constraint added in
  Step~\ref{step:update} or Step~\ref{step:prevent} is either between
  operators affecting the same variable or between operators affecting
  a variable and its child (with respect to the causal graph). In
  particular, if $A_i<A_j$ was added in Step~\ref{step:update} then
  either $v_i=v_j$ or $v_i \in \parents (v_j)$, whereas if $A_i<A_j$
  was added in Step~\ref{step:prevent} then $v_j \in \parents (v_i)$.
  
  Assume, to the contrary that $\cO$ implies $A_i<A_j$ and $A_j<A_i$.
  From the argument above, we know that there is a, possibly empty,
  path between $v_i$ and $v_j$ in the undirected graph induced by the
  causal graph. By our structural assumption, we know that such an
  undirected path between $v_i$ and $v_j$ is unique, and thus the situation
  is as follows: We have two chains of operators
  \begin{eqnarray*}
    \alpha\;:\; A_i = A_{i_0}^1 < \ldots < A_{i_0}^{x_0} < A_{i_1}^1 < & \ldots & <
          A_{i_1}^{x_1} < \ldots \ldots < A_{i_m}^1 < \ldots < A_{i_m}^{x_m} = A_j\\
    \beta\;:\; A_i=\bar{A}_{i_0}^1 > \ldots > \bar{A}_{i_0}^{y_0} > \bar{A}_{i_1}^1 > & \ldots & >
          \bar{A}_{i_1}^{y_1} > \ldots \ldots > \bar{A}_{i_m}^1 > \ldots >
          \bar{A}_{i_m}^{y_m} = A_j\\
  \end{eqnarray*}
  such that, for $0 \leq k \leq m$, both $x_k \geq 1$ and $y_k \geq
  1$. The corresponding unique undirected path between $v_i$ and $v_j$ is:
  \[
  v_i = v_{i_0} \cdot v_{i_1} \cdot \ldots \cdot v_{i_{m-1}} \cdot
  v_{i_m} = v_j
  \]
  Without loss of generality, the internal elements of $\alpha$ and
  $\beta$ are disjoint. Otherwise, if there is an operator $B$ that
  belongs to the internal parts of both $\alpha$ and $\beta$ then we
  can reduce these chains and deduce $A_i < B$ and $A_i > B$.
  
  The proof of consistency is as follows:
  {\renewcommand{\theenumi}{(\alph{enumi})}
   \renewcommand{\labelenumi}{\theenumi}
  \begin{enumerate}
  \item \label{l:proof1} We prove that if such $\alpha$ and $\beta$ exist then at least
    one of them should have at least one internal element.
  \item \label{l:proof2} We show some useful property of $\alpha$ and
    $\beta$, that is exploited in~\ref{l:proof3}.
  \item \label{l:proof3} We show that for $0 \leq k \leq m$,
  $A_{i_k}^{x_k}$ and $\bar{A}_{i_{k}}^{y_k}$ are different except when $x_0 = y_0 = 1$.

  Note that~\ref{l:proof1} together with~\ref{l:proof3}
  contradicts our assumption that $A_{i_m}^{x_m} =
  \bar{A}_{i_{m}}^{y_m}$.
  \end{enumerate}
  }

  
  (a) Assume, to the contrary, that both $\alpha$ and $\beta$ do not
  contain any internal elements. If so, then the algorithm actually
  adds to $\cO$ ordering constraints $A_i < A_j$ and $A_j < A_i$. If
  $v_i$ and $v_j$ are the same variable then $A_i < A_j$ can only stem
  from Step~\ref{step:update} and only because $A_i$ has
  the precondition of $A_j$ as its effect. However, by definition of {\sc forward-check},
  $A_j$ can not have the same role w.r.t.\ $A_i$ and thus it is
  impossible that $A_j < A_i$ was added to $\cO$.  Alternatively, if
  $v_i$ is a parent of $v_j$ then $A_i < A_j$ can stem only from
  Step~\ref{step:update} because $A_i$ has the prevail
  condition of $A_j$ as its effect. Suppose that $A_i = A(\sb^j_i)$ and thus
  $\sb^j_i \in \prv (A_j)$. In turn, $A_j < A_i$ can be added only in
  Step~\ref{step:prevent} because $A_j$ has the precondition of $A_i$
  as the prevail condition. But if $\sb^j_i \in \prv (A_j)$ then $A_i
  = A(\sw^j_i)$, and this contradicts our assumption that
  $A_i = A(\sb^j_i)$. Alternatively, we can assume that $A_i =
  A(\sw^j_i)$ but this situation is completely symmetric, and thus the
  result will be the same.  Hence we proved that either $\alpha$ or
  $\beta$ have to contain at least one internal element.  In
  particular it means that the next to last elements of $\alpha$ and
  $\beta$ are different and this fact is exploited later in the
  proof.
  
  (b) Consider subchains of $\alpha$ that consist of operators
  affecting only one particular variable. For each such a subchain,
  i.e.\ for $0 \leq k \leq m$, for $1 \leq j \leq x_k - 1$, the
  ordering constraint $A_{i_k}^j < A_{i_k}^{j+1}$ can only stem from
  Step~\ref{step:update} because $A_{i_k}^j$ has the
  precondition of $A_{i_k}^{j+1}$  as its effect.  Thus, $\post (A_{i_k}^j) = \pre
  (A_{i_k}^{j+1})$. Similarly, for the subchains of $\beta$, for $0
  \leq k \leq m$ and for $2 \leq j \leq y_k$, $\post (\bar{A}_{i_k}^j)
  = \pre (\bar{A}_{i_k}^{j-1})$.  In what follows we denote this
  property of $\alpha$ and $\beta$ by {\em local monotonicity}.

  
  (c) 
  % If $x_0=y_0=1$ then $A_{i_0}^{x_0} = \bar{A}_{i_0}^{y_0} =  A_i$.  
  First suppose that either $x_0>1$ or $y_0>1$, or both. Consider the
  following sequence:
  \[
  \gamma\;:\; \bar{A}_{i_0}^{y_0} < \bar{A}_{i_0}^{y_0-1} < \ldots <
  \bar{A}_{i_0}^{1} = A_{i_0}^{1} < ... < A_{i_0}^{x_0}
  \]
  From the local monotonicity, the construction of {\sc
    forward-check}, and the fact that $|\gamma| \geq 2$ it follows
  that $\post (\bar{A}_{i_0}^{y^0})$ appears before $\post
  (A_{i_0}^{x_0})$ on the maximal sequence $\sigma_{v_{i_0}}$.
  Continuing with the next variable $v_{i_1}$ we claim that $\post
  (\bar{A}_{i_1}^{y^1})$ has to appear before $\post (A_{i_1}^{x_1})$
  on $\sigma_{v_{i_1}}$.

  
%   First, consider that case in which $\post (\bar{A}_{i_0}^{y^0})$
%   appears before $\post (A_{i_0}^{x_0})$ on $\sigma_{v_{i_0}}$:
  
  {\it (i)} If $v_{i_0}$ is a parent of $v_{i_1}$ then $A_{i_0}^{x_0} <
  A_{i_1}^1$ can only stem from Step~\ref{step:update} because
  $A_{i_0}^{x_0}$ has the prevail condition of
  $A_{i_1}^1$  as its effect. In turn, $\bar{A}_{i_0}^{y_0} > \bar{A}_{i_1}^{1}$ can
  only stem from Step~\ref{step:prevent} because the prevail
  condition of $\bar{A}_{i_{1}}^1$ is the precondition of
  $\bar{A}_{i_0}^{y_0}$. From the relation between $A_{i_0}^{x_0}$ and
  $\bar{A}_{i_0}^{y_0}$, and the construction of $G'_e(v_{i_1})$ in
  {\sc forward-check}, it follows that $\post (\bar{A}_{i_{1}}^1)$ appears
  before $\post (A_{i_1}^1)$ on $\sigma (v_{i_1})$. Subsequently, from the local
  monotonicity it follows that $\post (\bar{A}_{i_{1}}^{y_1})$ appears
  before $\post (A_{i_1}^{x_1})$ on $\sigma (v_{i_1})$.
  
  {\it (ii)} Similarly, if $v_{i_1}$ is a parent of $v_{i_0}$ then
  $\bar{A}_{i_0}^{y_0} > \bar{A}_{i_1}^{1}$ can only stem from
  Step~\ref{step:update} because $\bar{A}_{i_1}^{1}$ has the prevail
  condition of $\bar{A}_{i_0}^{y_0}$ as its effect, and
  $A_{i_0}^{x_0} < A_{i_1}^1$ can only stem from
  Step~\ref{step:prevent} because the prevail condition of
  $A_{i_0}^{x_0}$ is the precondition of $A_{i_1}^1$.  From the
  relation between $A_{i_0}^{x_0}$ and $\bar{A}_{i_0}^{y_0}$, and the
  construction of $G'_e(v_{i_1})$ in {\sc forward-check}, it follows that $\post
  (\bar{A}_{i_{1}}^1)$ appears before $\post (A_{i_1}^1)$ on $\sigma
  (v_{i_1})$, and again, from the local monotonicity it follows that
  $\post (\bar{A}_{i_{1}}^{y_1})$ appears before $\post
  (A_{i_1}^{x_1})$ on $\sigma (v_{i_1})$.
  
  Alternatively, if $x_0=y_0=1$ then $A_{i_0}^{x_0} =
  \bar{A}_{i_0}^{y_0} = A_i$. From~\ref{l:proof1} immediately follows
  that $A_{i_1}^1 \neq \bar{A}_{i_{1}}^1$, and an analysis similar to
  the above shows that $\post (\bar{A}_{i_{1}}^{y_1})$ appears before
  $\post (A_{i_1}^{x_1})$ on $\sigma (v_{i_1})$.
  
  Having established that $\post (\bar{A}_{i_{1}}^{y_1})$ appears
  before $\post (A_{i_1}^{x_1})$ on $\sigma (v_{i_1})$, it is apparent
  that an inductive argument will allow us to show that for all $k>0$
  we have that $\post (\bar{A}_{i_{k}}^{y_k})$ appears before $\post
  (A_{i_k}^{x_k})$ on $\sigma (v_{i_k})$.  Note that in particular it
  means that the operators $A_{i_k}^{x_k}$ and $\bar{A}_{i_{k}}^{y_k}$
  are different, and this contradicts our assumption that
  $A_{i_m}^{x_m} = \bar{A}_{i_{m}}^{y_m}$.
\end{proof}

\newpage
\begin{atheorem}{t:bh-nphard}
\label{at:bh-nphard}
  {\em Plan existence for \strips\ planning problems with unary operators and
  directed-path singly connected causal graph is {\sc np}-complete.}
\end{atheorem}

\begin{proof}
  First we show the membership in ${\sc np}$. Let $\minplan (\Pi )$ denote
  the size of the minimal plan for a problem instance $\Pi$.  Using
  the $\Must$ property of the state variables, the following upper
  bound for $\minplan (\Pi )$ is straightforward from the Lemma~\ref{l1}:
\begin{equation}
\label{eq:ubound}
  \minplan (\Pi )  \leq \sum_{v\in\cV} \Must (v) \leq n^2
\end{equation}
Thus, if we guess a minimal solution for a given solvable problem, we
can verify it in low polynomial time.

The proof of the hardness is by polynomial reduction from {\sc 3-sat}
to the corresponding propositional plan generation problem with a
directed-path singly connected causal graph.  {\sc 3-sat} is the problem of finding
a satisfying assignment for a propositional formula in conjunctive
normal form in which each conjunct (clause) has at most three
literals.

Let $\cF = C_1\wedge\ldots\wedge C_n$ be a propositional formula
belonging to 3-SAT, and let ${X_1,\ldots ,X_m}$ be the variables used
in $\cF$.  An equivalent propositional planning problem with a directed-path singly
connected causal graph can be constructed as follows: The variable set is
$\cV = \{X_1,\bar{X}_1,\ldots ,X_m,\bar{X}_m\}\cup\{C_1,\ldots
,C_n\}$. The variables $X_i$ and $\bar{X}_i$ have no predecessors in
the causal graph, thus $\parents (X_i) = \parents (\bar{X}_i)
=\{\emptyset\}$. In turn, for $1\leq i\leq n$, $\parents (C_i) =
\{X_{i_1},\bar{X}_{i_1},X_{i_2},\bar{X}_{i_2},X_{i_3},\bar{X}_{i_3}\}$,
where $X_{i_1},X_{i_2}$, and $X_{i_3}$ are the variables that
participate in the $i$th clause of $\cF$. Finally, $Init$ and $Goal$
consist of false and true assignments to all variables in $\cV$,
respectively.
%   {\footnotesize
%   \begin{enumerate}
%     \item $\cV = \{X_1,\bar{X}_1,\ldots ,X_m,\bar{X}_m\}\cup\{C_1,\ldots ,C_n\}$
%     \item $\parents (X_i) = \parents (\bar{X}_i) =\{\emptyset\}$
%     \item $\parents (C_i) =
%       \{X_{i_1},\bar{X}_{i_1},X_{i_2},\bar{X}_{i_2},X_{i_3},\bar{X}_{i_3}\}$,
%       where $X_{i_1},X_{i_2}$, and $X_{i_3}$ are the variables that participate
%       in the $i$th clause of $\cF$.
%     \item $Init$ - consist of false assignments to all variables in $\cV$.
%     \item $Goal$ - consist of true assignments to all variables in $\cV$.
%   \end{enumerate}}

Let every operator $A\in\Lambda$ be presented as a three-tuple
$\langle\{\pre\},\{\post\} ,\{\prv\} \rangle$ of pre, post, and
prevail conditions respectively. Then, the corresponding operator set
$\Lambda$ is specified as follows: 
%{\footnotesize
  \begin{eqnarray*}
    \Lambda_{X_i}\;   & = \left\{\right. & \left. \langle\{f\} ,\{t\} ,\{\} \rangle\;\;\;\right\} \\
    \Lambda_{\bar{X_i}}\;   & = \left\{\right. & \left. \langle\{f\} ,\{t\} ,\{\} \rangle\;\;\;\right\} \\
    \Lambda_{C_i}\;    & = \left\{\right. &
                  \left. \langle\{f\} ,\{t\} ,\{\alpha_1^i\} \rangle ,\right.
                  \left. \langle\{f\} ,\{t\} ,\{\alpha_2^i\} \rangle ,\right.
                  \left.  \langle\{f\} ,\{t\} ,\{\alpha_3^i\} \rangle\;\;\;\right\}
%     \Lambda_{C_i} & = \left\{\right. &
%                   \left. \langle\{f\} ,\{t\} ,\{\alpha_1^i\} \rangle ,\right.\\
%             &   & \left. \langle\{f\} ,\{t\} ,\{\alpha_2^i\} \rangle ,\right. \\
%             &   & \left.  \langle\{f\} ,\{t\} ,\{\alpha_3^i\} \rangle\;\;\;\right\}
  \end{eqnarray*}
%  } 
where $\alpha_j^i$ ($1\leq j\leq 3$) corresponds to the truth
assignment on the variable $X_{i_j}$ that satisfies the $i$th clause of
$\cF$.  Let $C_i = (X_1 \vee \bar{X}_2 \vee X_8)$.  Then $\alpha_1^i 
= \{X_1 = t, \bar{X}_1=f\}$, $\alpha_2^i = \{X_2 = f,
\bar{X}_2=t\}$, and $\alpha_3^i = \{X_8 = t, \bar{X}_8=f\}$.


% To illustrate the proposed reduction consider the following example:
%   formula $\cF$ consist of 3 clauses:
%   \begin{center}
%   \mbox{
%   \xymatrix @R=1pt@C=1pt{
%     C_1 & & C_2 & & C_3\\
%     (x_1\vee \bar{x_2} \vee x_3) & \wedge & (x_1\vee \bar{x_2} \vee x_4) & \wedge & (x_2\vee \bar{x_3} \vee \bar{x_4}) 
%     }}
%    \end{center}
To illustrate the proposed reduction consider the following example.
Formula $\cF$ consist of 3 clauses: $(x_1\vee \bar{x_2} \vee x_3)
\wedge (x_1\vee \bar{x_2} \vee x_4) \wedge (x_2\vee \bar{x_3}
\vee \bar{x_4})$. The causal graph of the corresponding planning
problem is as follows:
  \begin{center}
  \mbox{
  \entrymodifiers={++[o][F-]}
  \xymatrix @R=70pt@C=15pt{
    x_1  \ar[dr]\ar[drrr] & \bar{x_1} \ar[d]\ar[drr] 
    & x_2  \ar@{-->}[dl]\ar@{-->}[dr]\ar@{-->}[drrr] & \bar{x_2} \ar@{-->}[dll]\ar@{-->}[d]\ar@{-->}[drr] 
    & x_3 \ar@{.>}[dlll]\ar@{.>}[dr] & \bar{x_3} \ar@{.>}[dllll]\ar@{.>}[d]
    & x_4 \ar@{~>}[dlll]\ar@{~>}[dl] & \bar{x_4}\ar@{~>}[dllll]\ar@{~>}[dll] \\
    *+{} & C_1 & *+{} & C_2 & *+{} & C_3
    }}
   \end{center}
  
   This is a propositional planning problem with single-effect operators and an
   underlying directed-path singly connected causal graph. Clearly, $Goal$ is
   reachable ($\Pi$ is solvable) if and only if a satisfying assignment for
   $\cF$ can be found. Thus, plan existence for the propositional planning
   problems with directed-path singly connected causal graphs is ${\sc
     np}$-complete.
\end{proof}

\begin{lemma}
  \label{l:aux}
  Given $k$ ordered sequences $\sigma_1,\cdots,\sigma_k$ of $n$ elements each,
  the number $T[k]$ of different merges of $\sigma_1,\cdots,\sigma_k$,
  preserving the orderings induced by $\sigma_1,\cdots,\sigma_k$ on their
  elements, is given by:
  \begin{equation}
    \label{e:aux1}
    T[k] \;= \; \prod_{i=1}^{k-1}
    {\sum_{j=1}^{n}{\binom{n-1}{j-1}\binom{n i + 1}{j}}}
  \end{equation}
\end{lemma}

\begin{proof}
  Considering the merge operation of such $k$ sequences as iterative
  merge of $\sigma_i$, $2 \leq i \leq k$, with the already merged sequences
  $\sigma_1,\ldots,\sigma_{i-1}$, it is easy to see that $T(k)$ can be
  expressed as:
    \begin{equation}
    \label{e:aux2}
    T[k] \;= \; \begin{cases}
      T[k-1] \cdot S\left[ n(k-1),n \right], & k > 1\\
      1, & k=1
      \end{cases}
  \end{equation}
  where $S[x,y]$ stands for the number of different, order preserving merges of
  {\em two} ordered sequences of sizes $x$ and $y$ (without loss of generality,
  we assume that $x \geq y$).
  
  We consider the process of merging two ordered sequences $\sigma$ and
  $\sigma'$, $|\sigma| \geq |\sigma'|$, as:
  \begin{enumerate}[(i)]
    \item \label{i:aux1} partition of $\sigma'$ into $j$ sub-sequences,
    \item \label{i:aux2} partition of $\sigma$ into $l$ sub-sequences,
      where $j-1 \leq l \leq j+1$, and
    \item \label{i:aux3} {\em interleaving} and order preserving concatenation
      of the sub-sequences of $\sigma$ and $\sigma'$.
  \end{enumerate}
  
  First, observe that $\sigma'$ can be partitioned into $1 \leq j \leq
  |\sigma'|$ sub-sequences. Second, for any $j$, the numbers of different
  partitions corresponding to steps (\ref{i:aux1}) and (\ref{i:aux2}) are
  $\binom{|\sigma'|-1}{j-1}$ and $\binom{|\sigma| + 1}{j}$, respectively.
  Finally, given a pair of such partitions of $\sigma$ and $\sigma'$, there
  exist exactly one possible interleaving and order preserving concatenation as
  in step (\ref{i:aux3}). Therefore, we have:
  \begin{equation}
    \label{e:aux3}
    S(x,y) \;=\; \sum_{j=1}^{y}{\binom{y-1}{j-1}\binom{x + 1}{j}}
  \end{equation}
  and combining Eq.~\ref{e:aux2} with Eq.~\ref{e:aux3}, we arrive to
  Eq.~\ref{e:aux1}.
\end{proof}

\newpage

%\vskip 0.2in

\bibliographystyle{theapa}
\bibliography{phd}


\end{document}
















