\documentclass{article}

\title {Partial-Ordering Using Needs Analysis}
\author {Elly Winner and Manuela Veloso}

\begin{document}

\maketitle

%%%%%%%%%%%%   ABSTRACT   %%%%%%%%%%%%
%\begin{abstract}
%\end{abstract}

%%%%%%%%%%%%   INTRODUCTION   %%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}

Partial-order planners are becoming more rare as total-order
planners win more and more planning competitions. The fastest
partial-order planners tend to be Graphplan-based, which allows for
only limited partial-ordering, as explained in
Section~\ref{sec:killgraph}. But partial orders remain useful for
scheduling, task decomposition, and task understanding. Algorithms
exist for partially-ordering total orders in domains with no
conditional effects. We present an algorithm for partially-ordering
total orders in domains with conditional effects.

The no-conditional-effect algorithm involves tracing backwards from
preconditions to the last adding operator, preventing deletion in
between. This is polynomial. The trouble with conditional effects is
that it is unclear which effects of a given operator will be used, and
so what exactly the preconditions of the operator will be.

One way to solve this problem is to assume that exactly the same
conditional effects should occur in the partial order as occur in the
total order. However, this is overly limiting--many irrelevant conditional
effects may occur, as described in Section~\ref{sec:activeces}.

Instead, we chose to compute a ``need'' structure over the total
order, which describes the conditions of each operator, but includes
the logical operators AND and OR to encompass the different
possibilities of conditions for each op.


%%%%%%%%%%%%   ALGORITHM   %%%%%%%%%%%%
\section{Algorithm}
\label{sec:alg}

We describe the initial state as an operator with no preconditions and
add effects of the items in the initial state. We also describe the
goal state as an operator with preconditions of the items in the goal
state and no effects.

The jist of the algorithm is that, given the conditions of the
previous step, calculate what set of things needs to be true for this
step to preserve/create those terms.

MUST simplify, clarify:

\begin{verbatim}
build_po:
  goal step needs = AND of all preconditions of goal step
  from last plan step back to initial step,
    for all preconditions of this step,
      add ADD precondition to this step's need set
    expand_needs(needs of last step, currentstep)
  propagate_accomplished();
  trim_unaccomplished();
  compress_ops();
  use_needs_to_build_po(); //not yet done

expand_needs (needs of prev step, current step)
  from first need to last need,
    creation = create (current need, current step)
    prevention = prevent (current need, current step)
    if (!impossible)
      need.needs = creation AND prevention;
    

create (need, current step)
  if (there exists a c eff of this step that adds need but has no conditions)
    need is accomplished
    inevitable = true;
    add NOTHING to current step's need set
  else
    return OR MAINTAIN need
           ADD preconditions of any c. effs of current step that add need
    add all these to current step's need set

prevent (need, current step)
  if (there exists a c eff of this step that dels need but has no conditions)
    impossible = true;
    add NOTHING to current step's need set
  else
    return ADD NOT preconditions of any c. effs of current step that del need
    add all these to current step's need set
\end{verbatim}

Should include complexity analysis.
%%%%%%%%%%%%   FEATURES   %%%%%%%%%%%%
\section{Features of the Algorithm}
\label{sec:features}
Things our algorithm does that yours may not:

%%%%%%%%%%%%   MULTIPLE POs   %%%%%%%%%%%%
\subsection{Multiple Partial Orders}
\label{sec:mpos}
\textbf{ALL} pos? maybe all pos consistent with TO? why wouldn't it be all
pos? wd have to prove all somehow.

Use Backstrom's example to show multiple.
\begin{itemize}
\item init: p
\item goal: q, r
\item plan:
  \begin{enumerate}
  \item a(needs 0, prod p, q)
  \item b(needs p, prod q, r)
  \item c(needs q, prod r)
  \end{enumerate}
\end{itemize}
seems that c isn't necessary in the 1st place. could we say we need q,
s and c produces s instead of r?

%%%%%%%%%%%%   CEs CHANGE BTW TOTAL ORDER & PARTIAL ORDER   %%%%%%%%%%%%
\subsection{Active Conditional Effects May Differ from Total Order}
\label{sec:activeces}
The partial order need not involve all the same conditional effects as
the total order. It needs to preserve the ``relevant'' conditional
effects (those that facilitate the transition between the initial 
conditions and the goal conditions), but not the ``irrelevant'' ones.

For example, simple sprinkler example with goal = wet front and wet
back and at shoe back--shoe may/may not be wet.

%%%%%%%%%%%%   KILL GRAPHPLAN   %%%%%%%%%%%%
\subsection{Partial Orders that Graphplan-based Systems Don't Get}
\label{sec:killgraph}
There are some simple partial orders that Graphplan-esque partial
orders fail to encompass. For example, the plan that consists of
walking and chewing gum.

What we really want for this example is one track for stepping and one
for chewing. Graphplan-esque partial-orderers would find the plan:

\{Step, Chew\}, \{Step, Chew\}, ...

And the inherent separation between these two activities would not be visible.

%%%%%%%%%%%%   COND EFFS   %%%%%%%%%%%%
\subsection{Conditional Effects}
\label{sec:ceffs}
Sprinkler example/Bomb example
\begin{itemize}
\item init: (at shoe front)
\item goal:
  \begin{itemize}
  \item (wet front)
  \item (wet back)
  \item (not (wet shoe)
  \end{itemize}
\item plan
  \begin{enumerate}
  \item (sprinkle back)
  \item (move shoe front back)
  \item (sprinkle front)
  \end{enumerate}
\end{itemize}

%%%%%%%%%%%%   WAYS TO ACCOMPLISH GOALS NOT IN PLAN   %%%%%%%%%%%%
\subsection{Unsupported Ways to Accomplish Goals}
\label{sec:otherways}
Sprinkler example--same as kitten to moon / exploding kitten bomb example.
\begin{itemize}
\item initial: (at shoe lawn)
\item goal: (wet shoe)
\item plan1: (sprinkle lawn)
\item plan2: (move shoe lawn ocean)
\end{itemize}

%%%%%%%%%%%%   IMPOSSIBLE WAYS TO ACCOMPLISH THAT SEEM OKAY   %%%%%%%%%%%%
\subsection{Impossible Plan Instantiations}
\label{sec:impossible}
it may be possible to think of a need graph that seems to allow a
given partial order Q where Q is not actually possible, since it
depends on mutually exclusive tracks of execution, but i'm feeling
brain dead and can't come up with an example of this.

also, i apparently can't even explain the problem clearly... ugh...!


%%%%%%%%%%%%   REORDERINGS   %%%%%%%%%%%%
\subsection{Instantiations that Require Reordering}
\label{sec:reorder}
The partial-orderer will not create partial orderers that violate the
``sense'' of the total order (i.e., that would come from the same
steps, but in a different order). For example, take the following operators:
\begin{itemize}
\item op1
  \begin{itemize}
  \item preconditions: -
  \item cond eff:
    \begin{itemize}
    \item condition: A
    \item effect: B
    \end{itemize}
  \item cond eff:
    \begin{itemize}
    \item condition: P
    \item effect: Q
    \end{itemize}
  \end{itemize}
\item op2
  \begin{itemize}
  \item preconditions: -
  \item cond eff:
    \begin{itemize}
    \item condition: B
    \item effect: C
    \end{itemize}
  \item cond eff:
    \begin{itemize}
    \item condition: A
    \item effect: P
    \end{itemize}
  \end{itemize}
\item op3
  \begin{itemize}
  \item preconditions: -
  \item cond eff:
    \begin{itemize}
    \item condition: C
    \item effect: Z
    \end{itemize}
  \item cond eff:
    \begin{itemize}
    \item condition: Q
    \item effect: Z
    \end{itemize}
  \end{itemize}
\end{itemize}

if we start with A and our goal is Z,
two total order plans are possible:

\begin{itemize}
\item plan 1:
  \begin{enumerate}
  \item op1
  \item op2
  \item op3
  \end{enumerate}
\item plan2:
  \begin{enumerate}
  \item op2
  \item op1
  \item op3
  \end{enumerate}
\end{itemize}

these two plans would not be considered reorderings of each other by
the partial orderer because switching between them requires changing
the relevant constraints of the total order.

%%%%%%%%%%%%   CONCLUSIONS   %%%%%%%%%%%%
\section{Conclusions}
\label{sec:concl}
ha!


%\bibligraphy{po}

\end{document}