% JAIR Article
% Computational Aspects of Reordering Plans
% Final version

% Last edited: Tue Sep 22 16:19:29 1998 by chrba@obel16.ida.liu.se (Christer Backstrom)


%\documentclass[11pt]{article} 
\documentstyle[jair,twoside,11pt,theapa,isolatin1,amssymbols]{article}
%\documentstyle[twoside,11pt,theapa,isolatin1,amssymbols]{article}

\jairheading{9}{1998}{99--137}{10/97}{9/98}
%\jairheading{*}{*--*}{*}{*}
\ShortHeadings{Computational Aspects of Reordering Plans}{Bäckström}
\firstpageno{99}

%%\usepackage{a4}
%\usepackage[latin1]{inputenc}   % Enter your text in ISO-Latin 1
%\usepackage[T1]{fontenc}        % To get Swedish characters in the output
%\usepackage{latexsym}
%\usepackage{amssymb}


\input{/sw/tex/inputs/psfig.tex}
\newcommand{\epsfig}[1]{\psfig{#1}} % Used by included pstex files!!!

\newcommand{\paper}{article}

\newcounter{prgline} % Used by algmacros.tex
\newcounter{A} % Used by \pushlist and \poplist


\newcommand{\eg}{\textit{eg}}
\newcommand{\ie}{\textit{ie}}
\newcommand{\etc}{\textit{etc}}


% File: mathmacros.tex

% Last edited: Tue Jan 13 13:39:30 1998 by chrba@obel16.ida.liu.se (Christer Backstrom)

% Some useful LaTeX macros, mainly math, to be input in head of LaTeX files


%%%%%%%%%%%%%%%%%%%%%%%
%% Fix greek letters %%
%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Commands to write text in math mode %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\text}[1]{\mbox{\rm \,#1\,}}        % To write text in mathmode

% Abbrev's for frequently used words
\newcommand{\tand}{\text{\ and\ }}
\newcommand{\tor}{\text{\ or\ }}
\newcommand{\tif}{\text{\ if\ }}
\newcommand{\tiff}{\text{\ iff\ }}
\newcommand{\tfor}{\text{\ for\ }}
\newcommand{\tforall}{\text{\ for all\ }}
\newcommand{\totherwise}{\text{\ otherwise}}


%%%%%%%%%%%%%%%%%%%
%% Miscellaneous %%
%%%%%%%%%%%%%%%%%%%

\newcommand{\fnl}{\void \\}             % Force newline

\newcommand{\pushlist}[1]{\setcounter{#1}{\value{enumi}} \end{enumerate}}
\newcommand{\poplist}[1]{\begin{enumerate} \setcounter{enumi}{\value{#1}}}
 % These commands makes it possible to break a first level enumerate list
 % and resume it later on. There must be a \newcounter{foo} command at
 % the beginning of the top level file, though.


%%%%%%%%%%
%% Math %%
%%%%%%%%%%

%% Numbers
%\newcommand{\naturals}{{\mathbb N}}
\newcommand{\integers}{{\mathbb Z}}
\newcommand{\rationals}{{\mathbb Q}}
\newcommand{\reals}{{\mathbb R}}
\newcommand{\complex}{{\mathbb}}

%% Sets
%\renewcommand{\emptyset}{\varnothing}  % The usual empty set,  not LaTeX std.
                                   % Requires the ``amssymbols'' option
\newcommand{\union}{\cup}               % Union
\newcommand{\intersect}{\cap}           % intersection
\newcommand{\diff}{-}                   % Set difference
\newcommand{\setdiff}{-}                % Old, do not use
\newcommand{\compl}[1]{\overline{#1}}   % Set complement
\newcommand{\card}[1]{{|#1|}}           % Cardinality     
\newcommand{\set}[1]{\{{#1}\}} % Set 
\newcommand{\st}{\ |\ }                 % `such that' symbol in sets
\newcommand{\suchthat}{\st}             % Old, do not use
\newcommand{\cprod}{\times}             % Cartesian product
\newcommand{\powerset}[1]{{\bf 2}^{#1}} % Powerset

%% Other math
\newcommand{\tuple}[1]{\langle{#1}\rangle}  % Tuple
\newcommand{\seq}[1]{\langle #1 \rangle}
\newcommand{\emptyseq}{\seq{}}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceiling}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\abs}[1]{{|#1|}} 
 
%% Functions
\newcommand{\map}{\rightarrow}
\newcommand{\fncomp}{\!\circ\!}         % Function composition


%% Relations
\newcommand{\transclos}[1]{#1^+}
\newcommand{\reduction}[1]{#1^-}        % Warning! non-standard notation

%% Lattices
\newcommand{\latlt}{\sqsubset}          % Lattice `less than'
\newcommand{\latleq}{\sqsubseteq}       % Lattice `less or equal'
\newcommand{\join}{\sqcup}              % Join
\newcommand{\meet}{\sqcap}              % Meet
\newcommand{\latbot}{\bot}              % Bottom eltTop elt
\newcommand{\lattop}{\top}              % Top elt

%% Logic
\newcommand{\limp}{\rightarrow} 
\newcommand{\leqv}{\leftrightarrow}
\newcommand{\falsum}{\bot}
 
\newcommand{\turnst}{\vdash}            % Turnstile
\newcommand{\nturnst}{\nvdash}          % Negated turnstile
\newcommand{\modls}{\vDash}             % Double turnstile
\newcommand{\nmodls}{\nvDash}           % negated double turnstile

\newcommand{\proves}{\vdash}            % Turnstile
\newcommand{\nproves}{\nvdash}          % Negated turnstile
\newcommand{\entails}{\vDash}             % Double turnstile
\newcommand{\nentails}{\nvDash}           % negated double turnstile


%% Environments %%
%%%%%%%%%%%%%%%%%%


\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{fact}[definition]{Fact}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{corollary}[definition]{Corollary}
\newtheorem{algorithm}{Algorithm}[section]
\newtheorem{example}{Example}[section]
\newtheorem{restr}{Restriction}[section]
\newtheorem{observation}[definition]{Observation}

\newcommand{\QED}{{\mbox{}~\hfill~$\Box$}}
\newenvironment{proof}{\noindent {\bf \noindent Proof: }}%
                      {\QED\par\addvspace{\baselineskip}}
\newenvironment{proofsk}{\noindent {\bf \noindent Proof sketch: }}{\QED}
\newenvironment{proofout}{\noindent {\bf \noindent Proof outline: }}{\QED}

\newcommand{\naturals}{{\Bbb N}}

% LaTeX macros for typesetting algorithms

% Last edited: Wed Apr 10 14:34:12 1996 by chrba@obel16.ida.liu.se (Christer Backstrom)


% This file is used for typesetting algorithms

%%% Variables %%%
%%%%%%%%%%%%%%%%%

% Counter used to keep current indentation length
\newlength{\prgindent}

% Lines will be numbered if linenumbering is true (the default)
\newif\iflinenumbering
\linenumberingtrue  % Default is line numbering

% Matching end's will be printed for all control structures (if, for, 
% while etc.) if prgendtext is true, otherwise not. Deafult is true.
\newif\ifprgendtext
\prgendtexttrue


%%% The main environment %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% The "program" environment is used for typesetting algorithms
\newenvironment{program}{
  \begin{list}%
   {\iflinenumbering\arabic{prgline}\else{}\fi}%
   {%\normalsize % To get the em measure right
   \usecounter{prgline}
   \setlength{\prgindent}{0em}
   \setlength{\parsep}{0em}
   \setlength{\itemsep}{0em}
   \setlength{\labelwidth}{1em}
   \setlength{\labelsep}{1em}
%   \setlength{\leftmargin}{\labelwidth}
   \setlength{\leftmargin}{4em}
   \setlength{\rightmargin}{4em}
   \addtolength{\leftmargin}{\labelsep}
   \setlength{\topsep}{0em}
   \setlength{\parskip}{0em} }
   \small}%
 {\end{list}}

%%% Primitives for typesetting blocks %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% These are primitives for typesetting algorithms. Usually you need
% not use these, but they can be useful at certain occasions.

% Environment for blocks. Everything between \begin{prgblock} and \end{block}
% will be indented
\newenvironment{prgblock}{\addtolength{\prgindent}{\labelsep}}%
{\addtolength{\prgindent}{-\labelsep}}

% A block can also be started and ended explicitly using the following
% three commands

% Begin a block, ie. increase the indentation
\newcommand{\prgbeginblock}{\addtolength{\prgindent}{\labelsep}}
% End a block, ie. decrease the indentation
\newcommand{\prgendblock}{\addtolength{\prgindent}{-\labelsep}}
% End a block. Also print the argument as a reserved word, bu only in
% the case \prgendtext is true. Used for ending blocks with end texts
% like endif, endwhile etc.
\newcommand{\prgcndendblock}[1]{\addtolength{\prgindent}{-\labelsep}
 \ifprgendtext \prglin\prgres{#1}\fi}


%%% Commands for typesetting algorithms %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% These are the commands you will typically use

% Start a new line using current indentation
\newcommand{\prglin}{\rm \item\hspace{\prgindent}}
% Start a new line, but with extra indentation
\newcommand{\prgindlin}{\rm \item\hspace{\prgindent}\hspace{\labelsep}}
% Start a new line for continuing text from previous line, ie. essentially
% a breakline command for algorithms
\newcommand{\prgcontlin}{\item[] \mbox{}\hspace{\prgindent}\hspace{\labelsep}}

% Typeset argument as reserved word (boldface)
\newcommand{\prgres}[1]{{\bf #1}}
% Assignment arrow
\newcommand{\prgassn}{\leftarrow}
\newcommand{\prgswap}{\leftrightarrow}
% Typeset argument as a name of a program, procedure etc. (italics)
\newcommand{\prgname}[1]{{\it #1}}

% Print "begin" and start a block
\newcommand{\prgbegin}{\prglin\prgres{begin}\prgbeginblock}
% End a block and print "end"
\newcommand{\prgend}{\prgendblock\prglin\prgres{end\ }}
% End a block, but do not print "end"
\newcommand{\prgnoend}{\prgendblock}

% Print "if"
\newcommand{\prgif}{\prglin\prgres{if\ }}
% Print "then" and start a new block
\newcommand{\prgthen}{\prgres{\ then\ }\prgbeginblock}
% Terminate current block, print "else" and start a new block
\newcommand{\prgelse}{\prgendblock\prglin\prgres{else}\prgbeginblock}
% D:o for "elsif"
\newcommand{\prgelsif}{\prgendblock\prglin\prgres{elsif\ }}
% End an if statement, ie. terminate curernt block and print "end if" 
% conditonally
\newcommand{\prgendif}{\prgcndendblock{end if}}
% Commands for printing reserved words for loop constructions
\newcommand{\prgwhile}{\prglin\prgres{while\ }}
\newcommand{\prgfor}{\prglin\prgres{for\ }}
\newcommand{\prgfrom}{\prgres{\ from\ }}
\newcommand{\prgto}{\prgres{\ to\ }}
\newcommand{\prgdownto}{\prgres{\ downto\ }}
% Print "do" and start a new block
\newcommand{\prgdo}{\prgres{\ do}\prgbeginblock}
% Print "repeat" and start a new block
\newcommand{\prgrepeat}{\prglin\prgres{\ repeat}\prgbeginblock}
% Print "loop" and start a new block
\newcommand{\prgloop}{\prglin\prgres{loop}\prgbeginblock}
% Commands for ending various types of loops. Terminates current block
% and print appropriate end text conditionally.
\newcommand{\prgendloop}{\prgendblock\prglin\prgres{end loop}}
\newcommand{\prgendwhile}{\prgcndendblock{end while}}
\newcommand{\prgendfor}{\prgcndendblock{end for}}
\newcommand{\prguntil}{\prgendblock\prglin\prgres{until\ }}

% Start a comment (ie. use italics)
\newcommand{\prgcomment}{\prglin\prgres{comment\ }\it }

% Commands for printing various common reserved words
\newcommand{\prgprocedure}{\prglin\prgres{procedure\ }}
\newcommand{\prgfunction}{\prglin\prgres{function\ }}
\newcommand{\prgnil}{\prgres{\ nil}}
\newcommand{\prgtrue}{\prgres{\ true}}
\newcommand{\prgfalse}{\prgres{\ false}}
\newcommand{\prgnot}{\prgres{\ not\ }}
\newcommand{\prgand}{\prgres{\ and\ }}
\newcommand{\prgor}{\prgres{\ or \ }}
\newcommand{\prgmod}{\prgres{\ mod \ }}
\newcommand{\prgfail}{\prgres{fail}}
\newcommand{\prgreturn}{\prgres{return\ }}
\newcommand{\prgaccept}{\prgres{accept}}
\newcommand{\prgreject}{\prgres{reject}}
\newcommand{\prgvar}{\prgres{\ var\ }}





%%% An example algorithm %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% This is an example of how to typeset Bubblesort using the macros in
% this file.
% NB, no indentation is required in the source file, but is recommended
% in order to make also the LaTeX source readable.

%\prgprocedure \prgname{Bubblesort}(\prgvar A: array [1..max] of integer);
%\prglin
%\prgvar i,j: integer;
%\prglin
%\prgbegin
%  \prgfor i \prgassn 1 \prgto n-1 \prgdo
%    \prgfor j \prgassn n \prgdownto i+1 \prgdo
%      \prgif A[i-1] > A[i] \prgthen
%        Swap(A[i-1], A[i]);
%      \prgendif
%    \prgendfor
%  \prgendfor
%\prgend




\prgendtextfalse


\newcommand{\false}{\textit{false}}
\newcommand{\true}{\textit{true}}
\newcommand{\atom}{p}
\newcommand{\atomb}{q}
\newcommand{\atomset}{{\cal P}}
\newcommand{\atomsetb}{{\cal Q}}
\newcommand{\lit}{l}       % \l no longer allowed!!!
\newcommand{\litset}{{\cal L}}
\newcommand{\litsetp}{{\litset_\atomset}}
\newcommand{\clauseset}{C}
\newcommand{\intrp}{I}

\newcommand{\state}{S}
\newcommand{\stateb}{T}

\newcommand{\op}{o}
\newcommand{\opset}{{\cal O}}
\newcommand{\opseq}{\omega}
\newcommand{\seqset}[1]{{\textit{Seqs\/}(#1)}}  % Set of sequences
\newcommand{\opseqset}{\seqset{\opset}}    % Set of operator sequences

\newcommand{\precond}{\textit{pre}}
\newcommand{\postcond}{\textit{post}}
\newcommand{\addlist}{\textit{add}}
\newcommand{\dellist}{\textit{del}}

\newcommand{\act}{a}
\newcommand{\actb}{b}
\newcommand{\actc}{c}
\newcommand{\actd}{d}
\newcommand{\actset}{A}
\newcommand{\precb}{\prec'}
\newcommand{\precc}{\prec''}

\newcommand{\edge}{e}

\newcommand{\pre}{\textit{pre}}
\newcommand{\post}{\textit{post}}

\newcommand{\slice}{S}
%\newcommand{\unord}{?}
\newcommand{\lc}{\latleq}
\newcommand{\lci}{\lc^\ppi}
\newcommand{\lcia}{\lc^{\ppi,\actset}}
\newcommand{\nonpar}{{\#}}
\newcommand{\duration}{d}
\newcommand{\release}{r}
\newcommand{\length}{\textit{length}}

\newcommand{\seqa}{\alpha}

\newcommand{\concat}{;\!}
\newcommand{\plan}{P}
\newcommand{\planb}{Q}
\newcommand{\planc}{R}
\newcommand{\init}{I}
\newcommand{\goal}{G}
\newcommand{\ppi}{\Pi}

\newcommand{\GT}{{GT}}
\newcommand{\valgt}{\textit{valid}}
\newcommand{\Neg}{\textit{Neg}}

\newcommand{\clink}[1]{\tuple{#1}}
\newcommand{\valstruct}{{\cal V}}

%% Specials for drawing plans %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\fgact}[2]{\put(#1){\framebox(10,10){$#2$}}}
\newcommand{\fgcnd}[2]{\put(#1){\makebox(0,0){$#2$}}}

\newcommand{\cond}{\pi}



\title{Computational Aspects of Reordering Plans}


\author{\name Christer B{\"a}ckstr{\"o}m \email cba@ida.liu.se\\
 \addr Department of Computer and Information Science \\
 Link{\"o}pings universitet,  S-581 83 Link{\"o}ping,  Sweden}


\begin{document}

\bibliographystyle{theapa}

\maketitle

\begin{abstract}
This \paper\ studies the problem of modifying the action ordering of a plan in 
order to optimise the plan according to various criteria.
One of these criteria is to make a plan less constrained and the other is
to minimize its parallel execution time.
Three candidate definitions are proposed for the first of these criteria,
constituting a sequence of increasing optimality guarantees.
Two of these are based on deordering plans, which means that ordering relations
may only be removed, not added, while the third one uses reordering, where
arbitrary modifications to the ordering are allowed.
It is shown that only the weakest one of the three criteria is tractable
to achieve, the other two being NP-hard and even difficult to approximate.
Similarly, optimising the parallel execution time of a plan is studied both
for deordering and reordering of plans.
In the general case, both of these computations are NP-hard.
However, it is shown that optimal deorderings can be computed in polynomial
time for a class of planning languages based on the notions of producers,
consumers and threats, which includes most of the commonly used planning
languages.
Computing optimal reorderings can potentially lead to even faster parallel
executions, but this problem remains NP-hard and difficult to approximate
even under quite severe restrictions.
\end{abstract}


\section{Introduction}
In many applications where plans, made by man or by computer, are executed,
it is important to find plans that are optimal with respect to some cost 
measure, typically execution time.
Examples of such applications are manufacturing and error-recovery for
industrial processes, production planning, logistics and robotics.
Many different kinds of computations  can be made to improve
the cost of a plan---only a few of which have been extensively studied in
the literature.
The most well-known and frequently used of these is \emph{scheduling}.
A plan tells which actions (or tasks) to do and in which order to do them, while a
schedule assigns exact release times to these actions.
The schedule must obey the action order prescribed by the plan and must often
also satisfy further metric constraints such as deadlines and earliest release
times for certain actions.
A schedule is \emph{feasible\/} if it satisfies all such metric constraints.
It is usually interesting to find a schedule that is optimal in some respect,
\eg\ the feasible schedule having the shortest total execution time, or the
schedule missing the deadlines for as few actions as possible.

In principle, planning and scheduling follow in sequence such that scheduling
can be viewed as a post-processing step to planning---where planning is concerned
with causal relations and qualitative temporal relations between actions,
while scheduling is concerned with metric constraints on actions.
In some planning systems, \eg\ \textsc{O-Plan}~\cite{Currie:Tate:ai91} and
\textsc{Sipe}~\cite{Wilkins:PP}, both planning and scheduling are integrated 
into one single system.
Similarly, temporal planners, \eg\ \textsc{Deviser}~\cite{Vere:pami83}
and \textsc{IxTeT}~\cite{Ghallab:Laruelle:aips94}, can often reason also
about metric constraints.
This does not make it irrelevant to study planning and scheduling as separate
problems, though, as can be seen from the vast literature on both topics.
The two problems are of quite different character and studying them separately
gives important insight also into such integrated systems as was just
discussed.
For instance, Drabble\footnote{Brian Drabble, personal communication, Aug. 1997.}
says that it is often very difficult to see when \textsc{O-Plan} plans
and when it schedules; it is easy to see that \textsc{O-Plan} works, but it is 
difficult to see why.

A further complication in understanding the difference between planning and
scheduling, both for integrated systems and for systems with separated
planning and scheduling, is that certain types of computations  fall
into a grey zone between planning and scheduling.
Planners are good at reasoning about effects of actions and causal relationships
between actions, but are usually very poor at reasoning about time and temporal
relationships between actions.
Schedulers, on the other hand, are primarily designed to reason about time and
resource conflicts, but have no capabilities for reasoning about causal 
dependencies between actions.
The problems in the grey zone require reasoning of both kinds, so neither
planners nor schedulers can handle these problems properly.
If these problems are not solved, then the scheduler does not get sufficient
information from the planner to do the best of the situation---the planner and
the scheduler may fail in their cooperation to find a plan with a feasible 
schedule, even when such a plan exists.

This \paper\ focusses on one of these grey-zone  problems, namely the problem 
of optimising the action order of a plan to allow for better schedules.
Whenever two actions conflict with each other and cannot be allowed to execute
in parallel, a planner must order these actions.
However, it usually does not have enough information and reasoning capabilities
to decide which of the two possible orders is the best one, so it makes an
arbitrary choice.
One of the choices typically allows for a better schedule than the other one, 
so if the planner makes the wrong choice it may prevent the scheduler from
finding a good, or even  feasible, schedule.
This situation arises also when plans are made by a human expert,
since it is difficult to see which choice of ordering is the best one in a
large and complex plan.
Planning systems of today usually cannot do anything better than
asking the planner for a new plan if the scheduler fails to find a feasible
schedule.
This is an expensive and unsatisfactory solution, especially if there is no
feedback from the scheduler to help the planner making a more intelligent
choice next time.
Another solution which appears in the literature is to use a filter between
the planner and scheduler which attempts to modify the plan order to put
the scheduler in a better position. 
Such filters could remove certain over-commitments in the ordering, which will
be referred to as \emph{deordering\/} the plan, or even change the order between
certain actions, which will be referred to as \emph{reordering\/} the plan.

This \paper\ is intended to provide a first formal foundation for studying
this type of problems.
It defines a number of different optimality criteria for plan order 
modifications, both with respect to the degree of over-committment in the
ordering and with respect to the parallel execution time, and it also
provides  computational results for computing such modifications.
The \paper\ also analyses some filtering algorithms suggested in the
literature for doing such order modifications.


The remainder of this \paper\ is structured as follows.
Section~\ref{sec:example} introduces the concepts and computations studied
in this \paper\ by means of an example.
Then Section~\ref{sec:formalisms} starts the theoretical content of the \paper,
defining the two planning formalisms used in the following sections.
The problems of making a plan least-constrained are studied in
Section~\ref{sec:least-constrainment} where some candidate definitions
for this concept are introduced and their computational properties investigated.
Section~\ref{sec:parallel-plans} defines the concepts of parallel plans 
and parallel executions of plans.
This is followed by Section~\ref{sec:parallel-reordering} where optimal 
deorderings and reorderings of parallel plans are introduced and 
the complexity of achieving such optimality is analysed.
Section~\ref{sec:restr-cases} then studies how the complexity of these problems 
is affected by restricting the language. This includes the positive result
that an algorithm from the literature finds optimal deorderings for a class 
of plans for most common planning languages.
Some other filtering algorithms from the literature as well as some planners
incorporating some ordering optimisation are discussed in 
Section~\ref{sec:related-work}.
Finally, Section~\ref{sec:discussion} discusses some aspects of this \paper\ and 
some related work, while Section~\ref{sec:conclusions} concludes by a brief 
recapitulation of the results.


\section{Example}\label{sec:example}

In order to illustrate the concepts and operations studied in this article
a simple example of assembling a toy car will be used.
The example is a  variation of the example used by 
Bäckström and Klein~\citeyear{Backstrom:Klein:ijcai91}, which is a much simplified
version of an existing assembly line for toy cars used for undergraduate
laborations in digital control at Linköping University
\cite<for a description of this assembly line, see \emph{eg.}>{Klein:etal:ewsp95,Klein:etal:aieng98,Stromberg:SLB}.
The problem is to assemble a LEGO\footnote{LEGO is a trade mark of the LEGO
company} car from pre-assembled parts as shown in Figure~\ref{fig:car-assembly}.
There is a chassis, a top and a set of wheels, the two latter to be mounted
onto the chassis.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \input{car-assembly.pstex_t}
    \caption{Schematic assembly process for a toy car}
    \label{fig:car-assembly}
  \end{center}
\end{figure}

The workpiece flow of the factory is shown in Figure~\ref{fig:factory}.
There are three storages, one for each type of preassembled part, two
workstations, number 1 for mounting the top and number 2 for mounting the wheels,
and there is a car storage for assembled cars.
Tops can be moved from the top storage to workstation 1 and sets of wheels can
be moved from the wheels storage to workstation 2.
Chassis can be moved from the chassis storage to either workstation and also,
possibly with other parts mounted, between the two workstations and from either
workstation to the car storage. 
Furthermore, before mounting the wheels on a chassis, the tyres must be inflated,
so workstation 2 incorporates a compressed-air container which must be 
pressurized before
inflating the tyres (this is not shown in the figure).

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \input{factory.pstex_t}
    \caption{Schematic lay-out of the toy-car factory}
    \label{fig:factory}
  \end{center}
\end{figure}

This article is concerned with modifying the order between the actions in a
given plan, and does not consider modifying also the set of actions.
Hence, the example will assume that a plan for assembling a toy car is 
given---whether this plan was produced by hand or by a planning algorithm is
not important.
It will also be assumed that this assembly plan contains exactly those actions
listed in Table~\ref{tab:assembly-actions}, in some order.
Since most results in this article are independent of the particular planning
language used, no assumptions about the planning language will be made in
this example either. 
To make things simple, the obvious common-sense constraints on which plans
are valid will be used.
For instance, a part must be moved to a workstation before it is mounted there,
the wheels must be inflated before being mounted and the air container must
be pressurized before inflating the tyres.
Furthermore, since a chassis can only be at one single place at a time, the
top cannot be mounted in parallel with mounting the wheels, and neither of
the mounting operations can be done in parallel with moving either the chassis 
or the part to be mounted.


\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \begin{tabular}[t]{|l|l|l|}
\hline
Action & Description & Duration\\
\hline
MvT1 & Move top to workstation 1    & 1\\
MvW2 & Move wheels to workstation 2 & 1\\
MvC1 & Move chassis to workstation 1 & 2\\
MvC2 & Move chassis to workstation 2 & 2\\
MvS & Move chassis to car storage  & 3\\
MtT  & Mount top on chassis & 7\\
MtW  & Mount wheels on chassis & 4\\
PAC   & Pressurize air container & 5\\
IT   & Inflate tyres & 4\\
\hline
    \end{tabular}
    \caption{Actions of the assembly plan}
    \label{tab:assembly-actions}
  \end{center}
\end{table}

The purpose of modifying the action order in a given plan is usually to
optimize the plan in some aspect, for instance, to make the
 plan \emph{least constrained}.
Consider the totally ordered plan in Figure~\ref{fig:lc-plans}a, for producing 
a chassis with wheels, which is a subplan of the plan for assembling a car.
Note that since the plan is totally ordered, all pairs of actions are ordered,
but the implicit transitive arcs are not shown in the figure.
This plan is clearly over-constrained.
For instance, it is not necessary to move the set of wheels to workstation 2
before pressurizing the air container, and removing this ordering constraint
results in the plan in Figure~\ref{fig:lc-plans}b.
Note that orderings have only been removed---the arc from MvW2 to IT existed
already in the original plan, but was implicit by transitivity.
A plan where some orderings have been removed will be referred to as a
\emph{deordering\/} of the original plan.
This new plan is less constrained than the original plan, since it is now possible
to move the wheels and pressurize the air container in either order or, perhaps, even
in parallel.
However, further orderings can be removed; it is not necessary to inflate
the wheels before moving the chassis to the workstation.
Removing also this ordering results in the plan in Figure~\ref{fig:lc-plans}c,
which is a least constrained deordering of the original plan
in the sense that it is not possible to
remove any further ordering constraints  and still have a valid plan.
That is, if removing any further ordering constraint, it will be possible to
sequence the actions in such a way that the plan will no longer have its intended
result. 
In addition to deorderings, one may also consider arbitrary modifications of
the ordering relation, that is, both removing and adding relations.
Such modifications will be referred to as \emph{reorderings}.
Three differents least-constrainment criteria for plans based on deorderings
and reorderings will be studied in
Section~\ref{sec:least-constrainment}, and the plan in Figure~\ref{fig:lc-plans}c
happens to be optimal according to all three of these criteria.


\begin{figure}[th]
  \begin{center}
    \leavevmode
    \input{lc-plans.latex}
    \caption{Three plans for mounting the wheels}
    \label{fig:lc-plans}
  \end{center}
\end{figure}

Making a plan least constrained is clearly useful if certain actions can be
executed in parallel.
However, even in the case where no parallel execution is possible, it may still
be  worth making a plan least constrained.
Although the partial order of this least constrained plan must again be 
strengthened into a total order for execution purposes, this need not be 
the same total order as in the original plan.
Suppose the actions have temporal constaints like deadlines and earliest release
times and that a scheduler will post-process the plan to try finding a feasible
schedule.
It may then be the case that the original plan has no feasible schedule, but a
less constrained version of it can be sequenced into a feasible schedule.
The idea of a least constrained plan is that the scheduler will have as many
alternative execution sequences as possible to choose from.


The most important reason for modifying the action ordering of a plan, however,
is to execute the plan faster by executing actions in parallel whenever possible.
For this purpose it is better to use the length of the optimal schedule for
a plan as a measure, rather than some measure on the ordering itself.
Suppose the following  car-assembly plan is given
    \[ \seq{MvW2, PAC, IT, MvC2, MtW, MvT1, MvC1, MtT, MvS}. \]
If the actions are executed sequentially in the given order, the minimum
execution time is the sum of the durations of the actions, that is 29 time
units.
However, just as in the previous example this plan is over-constrained, since
several of the actions could be executed in either order, or in parallel.

It is possible to remove orderings as far as shown in 
Figure~\ref{fig:deordered-ass-plan}a,
but no further, and still have a valid plan (the implicit transitive orderings
are not shown in the figure).
This deordered version of the original assembly plan can be scheduled to
execute in 25 time units by exploiting parallelism whenever possible.
An example of such a schedule is shown in Figure~\ref{fig:lc-plans}b.
However, no faster execution is possible, since the plan contains a subsequence
of actions which cannot be parallelized and which has a total execution time
of 25 time units. 


\begin{figure}[t]
  \begin{center}
    \leavevmode
    \input{deordered-ass-plan.pstex_t}
    \caption{An optimal deordering of the assembly plan}
    \label{fig:deordered-ass-plan}
  \end{center}
\end{figure}

It is obvious from the schedule in Figure~\ref{fig:deordered-ass-plan}b that not many
actions can be executed in parallel, and that the gain of deordering the plan
is quite small.
A much better performance is possible if  arbitrary modifications to the action
ordering are allowed, that is, if also reorderings are considered.
For instance, in the assembly plan
there is no particular reason why the wheels should be mounted
before the top is mounted, and it will be seen shortly that much time can
be saved by reversing the order of these two operations.
A deordering cannot do this, however, since removing the ordering between
the wheel-mounting action (MtW) and the top-mounting action (MtT) would make
these unordered.
This would be interpreted as if the two actions could be executed in parallel,
which is not possible.
This is also the reason why these actions must be ordered in the original plan.
However, when allowing arbitrary modifications, the order between these two
 actions can be reversed, and Figure~\ref{fig:reordered-ass-plan}a shows
such a reordering of the original plan.
This plan can be scheduled to execute in only 16 time units, which is a 
considerable improvement over both the original plan and the optimal deordered
version of it.
An example of an optimal schedule is shown in 
Figure~\ref{fig:reordered-ass-plan}b.
In fact, this plan is an optimal reordering in the sense that no other ordering
of the actions results in a valid plan that can be scheduled to execute faster.
The problems of finding optimal deorderings and reorderings of plan with
respect to parallel execution is the main topic of this article, and are
studied in Sections~\ref{sec:parallel-plans} to \ref{sec:restr-cases}.

\begin{figure}[t]
  \begin{center}
    \leavevmode
    \input{reordered-ass-plan.pstex_t}
    \caption{An optimal reordering of the assembly plan}
    \label{fig:reordered-ass-plan}
  \end{center}
\end{figure}

It is obvious that reordering is a more powerful operation than deordering,
since the reordered plan in Figure~\ref{fig:reordered-ass-plan}a allows for 
a shorter schedule than the optimal deordering in
Figure~\ref{fig:deordered-ass-plan}a.
On the other hand, if the original plan had been 
\[ \tuple{MvT1, MvC1, MtT, MvS, MvW2, PAC, IT, MvC2, MtW}, \]
then deordering would have been sufficient for arriving at the optimal plan
in Figure~\ref{fig:reordered-ass-plan}a.


\section{Planning Formalisms}\label{sec:formalisms}


This section defines actions, plans and related concepts,
which basically appear in two different guises in this \paper.
Definitions and tractability results will mostly be cast in a
general, axiomatic framework in order to be as general and independent
of formalism as possible.
Hardness results, on the other hand, will mostly be cast in a specific
formalism, \textsc{Ground Tweak}, and often subject to further restrictions,
this in order to strengthen the results.
Both these formalisms are defined below.
In addition to these, a third formalism will be used, but its definition
will be deferred until it is used, in Section~\ref{sec:restr-cases}.

\subsection{The Axiomatic Planning Framework}

The axiomatic framework makes only a minimum of assumptions about 
the underlying formalism.
It may be instantiated to any planning formalism that defines
some concept of a \emph{planning problem\/}
a domain of entities called \emph{actions\/} and
a \emph{validity\/} test.
The planning problem is assumed to consist of \emph{planning
problem instances} (\textsc{ppi}s),\footnote{
  This is the complexity-theoretic terminology for problems. Planning
  problem instances in the sense of this \paper\ are sometimes referred
  to as planning problems in the planning literature.}
with no further assumptions about  the inner structure of these.
%The validity test is a truth-valued function taking a \textsc{ppi\/} and 
The validity test is a truth-valued function taking a \textsc{ppi\/} and 
a sequence of actions as arguments.
If the validity test is true for a \textsc{ppi\/} $\ppi$ and an action sequence
$\seq{\act_1,\ldots,\act_n}$, then the action sequence 
$\seq{\act_1,\ldots,\act_n}$  is said to \emph{solve\/} $\ppi$.
While the inner structure of the \textsc{ppi}s and the exact definition of 
the validity test are crucial for any specific planning formalism,
many results in this \paper\ can be proven without making any such
further assumptions.
Results on the computational complexity of certain problems will make
an assumption about the complexity of the validity test, though.
Based on these concepts, the notion of plans can be defined in the usual
way.



%
\begin{definition}
A \emph{total-order plan (t.o.~plan)\/} is a sequence 
$\plan=\seq{\act_1,\ldots,\act_n}$ of actions, which can alternatively be
denoted by the tuple $\tuple{\set{\act_1,\ldots,\act_n},\prec}$
where for $1\leq k,l \leq n$, $\act_k\prec\act_l$ iff $k<l$.
Given a \textsc{ppi} $\ppi$, $P$ is said to be \emph{$\ppi$-valid\/} iff 
the validity test is true for $\ppi$ and $\plan$.

A \emph{partial-order plan (p.o.~plan)} is a tuple
$\plan=\tuple{\actset,\prec}$ where $\actset$ is a set of actions and 
$\prec$ is a strict ( ie. irreflexive) partial order on $\actset$.
The validity test is extended to p.o.~plans s.t.
given a \textsc{ppi} $\ppi$, $\plan$ is $\ppi$-valid iff
$\tuple{\actset,\precb}$ is valid for every topological sorting 
$\precb$ of $\prec$.
\end{definition}

The actions of a t.o.~plan must be executed in the specified order, while
unordered actions in a p.o.~plan may be executed in either order.
That is, a p.o.~plan can be viewed as a compact representation for a set
of t.o.~plans.
There is no implicit assumption that unordered actions
can be executed in parallel; 
parallel plans will be defined in Section~\ref{sec:parallel-plans}.
p.o.~plans will  be viewed as \emph{directed acyclic graphs\/} 
in figures with the transitive arcs often tacitly omitted to
enhance readability.
Furthermore, all proofs and algorithms in this \paper\ are based on this definition,
\ie\ assuming the order of a plan is transitively closed, while many practical
planners do not bother about transitive closures. This difference does not
affect any of the results presented here.

\subsection{The Ground TWEAK Formalism}

The Ground TWEAK (GT) formalism is the TWEAK language~\cite{Chapman:ai87}
restricted to ground actions.
This formalism is a variation on propositional STRIPS and it is known to
be equivalent under polynomial transformation to most other common
variants on propositional STRIPS \cite{Backstrom:ai95}.
In brief, an action has a precondition and a postcondition, both being
sets of ground literals.

In order to define the GT formalism, the following two definitions
are required.
Given some set $S$, the notion $\seqset{S}$ denotes the set of all sequences
formed by members of $S$, allowing repetition of elements and including the
empty sequence.
The symbol `$\concat$\,' will be used to denote the
sequence concatenation operator.
Further, given a set $\atomset$ of propositional atoms, the set $\litsetp$
of literals over $\atomset$ is defined as
$\litsetp = \atomset \union \set{\lnot\atom \st \atom\in\atomset}$.
Since no other formulae will be allowed than atoms and negated atoms, a
double negation $\lnot\lnot\atom$ will be treated as identical to
the unnegated atom $\atom$.
Finally, given a set of literals $L$, the negation $\Neg(L)$ of $L$ is
defined as $\Neg(L)=\set{\lnot\atom \st \atom\in L} \union
\set{\atom \st \lnot\atom\in L}$ and $L$ is said to be \emph{consistent\/} iff
there is no atom $\atom$ s.t. both $\atom\in L$ and $\lnot\atom\in L$.


\begin{definition}
  An instance of the \emph{\GT\ planning problem\/} is a quadruple
  $\ppi=\tuple{\atomset,\opset,\init,\goal}$ where
\begin{itemize}
\item $\atomset$ is a finite set of \emph{atoms};
\item $\opset$ is a finite set of \emph{operators\/} of the form
  $\tuple{\pre,\post}$ where $\pre,\post\subseteq\litsetp$ are
  consistent and denote the \emph{pre\/} and \emph{post condition\/}
  respectively;
\item $\init,\goal\subseteq\litsetp$ are consistent and denote the
  \emph{initial\/} and \emph{goal state\/} respectively.
\end{itemize}
\end{definition}
%
For $\op=\tuple{\pre,\post}\subseteq\opset$, we write $\pre(\op)$ and
$\post(\op)$ to denote $\pre$ and $\post$ respectively.  A sequence
$\seq{\op_1,\ldots,\op_n}\in\opseqset$ of operators is called a 
  \emph{\GT\ plan\/} (or simply a plan) over~$\ppi$.

\begin{sloppypar}
\begin{definition}\label{df:GT-solve}
  The ternary relation $\valgt\subseteq\opseqset\cprod 2^\litsetp\cprod
  2^\litsetp$ is defined s.t. for arbitrary
  $\seq{\op_1,\ldots,\op_n}\in\opseqset$ and
  $\state,\stateb\subseteq\litsetp$,
  $\valgt(\seq{\op_1,\ldots,\op_n},\state,\stateb)$ holds iff either
\begin{enumerate}
\item $n=0$ and $\stateb\subseteq\state$ or
\item $n>0$, $\pre(\op_1)\subseteq\state$ and \\ 
  $\valgt(\seq{\op_2,\ldots,\op_n},
  (\state-\Neg(\post(\op_1))\union\post(\op_1),\stateb)$.
\end{enumerate}
%
A t.o.~plan $\seq{\op_1,\ldots,\op_n}\in\opseqset$ solves
 $\ppi$ iff $\valgt(\seq{\op_1,\ldots,\op_n},\init,\goal)$.
\end{definition}
\end{sloppypar}

An action is a unique instance of an operator, \ie\ a set of actions may
contain several instances of the same operator, and it inherits its
pre- and post-conditions from the operator it instantiates.
Since all problems in this \paper\ will consider some fixed set of actions,
the atom and operator sets will frequently be tacitly omitted from the
GT \textsc{ppi}s.
In figures, GT actions will be shown as boxes, with precondition literals
to the left and postcondition literals to the right.



\section{Least Constrained Plans}\label{sec:least-constrainment}

It seems to have been generally assumed in the planning community that there
is no difference between t.o.~plans and p.o.~plans in the sense that a 
t.o.~plan can easily be converted into a p.o.~plan and \emph{vice versa}.
However, while a p.o.~plan can be trivially converted into a t.o.~plan in 
low-order polynomial time by topological sorting, it is less obvious that
also the converse holds.
At least three algorithms 
for converting t.o.~plans into p.o.~plans have been presented in the literature
\cite{Pednault:rap86,Regnier:Fade:ewsp91,Veloso:etal:iapsc90} 
(all these algorithms will be analyzed later in this \paper).
The claim that a t.o.~plan can easily be converted into a p.o.~plan is
vacuously true since any t.o.~plan is already a p.o.~plan, 
by definition.
Hence, no computation at all needs to be done.
This is hardly what the algorithms were intended to compute, however.
In order to be useful, such an algorithm must output a p.o.~plan 
satisfying some interesting criterion, ideally some optimality criterion.
In fact, two of the algorithms mentioned above are claimed to produce optimal 
plans according to certain criteria.
For instance,  Veloso \emph{et al.} \citeyear[p.~207]{Veloso:etal:iapsc90}
claim their algorithm to  produce \emph{least constrained\/} plans.
They do not define what they mean by this term, however, and theirs is hardly
the only paper in the literature using this term without further definition.

Unfortunately, it is by no means obvious what constitutes an intuitive or 
good criterion for when a p.o.
plan is least constrained and, to some extent, this also depends on the
purpose of achieving least-constrainment.
The major motivation for producing p.o.~plans instead of t.o.~plans
\cite<see for instance>{Tate:ijcai75} is that a p.o. 
plan can be post-processed by a  scheduler according to further criteria,
such as release times and deadlines or resource limits.
Either the actions are ordered into an (ideally) optimal sequence or,
given criteria for parallel execution, into a parallel plan that can
be executed faster than if the actions were executed in sequence.
In both cases, the less constrained the original plan is, the greater is the 
chance of arriving at an optimal schedule or optimal parallel execution 
respectively.
Both of the algorithms mentioned above are motivated by the goal of exploiting
possible parallelism to decrease execution time.

It is not only interesting to make t.o.~plans partially ordered, but also to
make partially ordered plans more partially ordered, that is, to generalise
the ordering.
An algorithm for this task has been presented in the literature in the context
of case-based planning \cite{Kambhampati:Kedar:ai94}.
Since t.o.~plan are just a special case of p.o.~plans, this section will study
the general problem of making partially ordered plans less constrained.

\subsection{Least-constrainment Criteria}

There is, naturally, an infinitude of possible definitions of 
least-constrainment.
Some seem more reasonable than others, however.
Three intuitively reasonable candidates are defined and analyzed below.
Although other definitions are possible, it is questionable whether
considerably better or more natural definitions, with respect to the purposes
mentioned above, can be defined without using more information than
is usually present in a t.o. or p.o.~plan.


\begin{definition}
Let $\plan=\tuple{\actset,\prec}$ and 
$\planb=\tuple{\actset,\prec'}$ be two p.o.~plans and
$\ppi$ a \textsc{ppi}. Then,
\begin{enumerate}
\item $\planb$ is a \emph{reordering\/} of $\plan$ wrt. $\ppi$ iff
both $\plan$ and $\planb$ are $\ppi$-valid.
\item $\planb$ is a \emph{deordering\/} of $\plan$ wrt. $\ppi$ iff 
$\planb$ is a reordering of $\plan$ and $\prec'\subseteq\prec$
\item $\planb$ is a \emph{proper deordering\/} of $\plan$  wrt. $\ppi$ iff 
$\planb$ is a reordering of $\plan$ and $\prec'\subset\prec$
\end{enumerate}
\end{definition}

\begin{definition}
  Given a \textsc{ppi\/} $\ppi$ and two p.o.~plans $\plan=\tuple{\actset,\prec}$ and 
$\planb=\tuple{\actset,\prec'}$, 
\begin{enumerate}
\item $\planb$ is a \emph{minimal-constrained deordering\/} of $\plan$  
  wrt. $\ppi$ iff
  \begin{enumerate}
  \item $\planb$ is a deordering $\plan$  wrt. $\ppi$ and
  \item there is no proper deordering of $\planb$ wrt. $\ppi$;
  \end{enumerate}

\item $\planb$ is a \emph{minimum-constrained deordering\/} of $\plan$  
  wrt. $\ppi$ iff
  \begin{enumerate}
  \item $\planb$ is a deordering $\plan$  wrt. $\ppi$ and
  \item there is no  deordering $\tuple{\actset,\prec''}$of $\planb$ 
    wrt. $\ppi$ s.t. $\card{\prec''} < \card{\prec}$;
  \end{enumerate}

\item $\planb$ is a \emph{minimum-constrained reordering\/} of $\plan$  
  wrt. $\ppi$ iff
  \begin{enumerate}
  \item $\planb$ is a reordering $\plan$  wrt. $\ppi$ and
  \item there is no  reordering $\tuple{\actset,\prec''}$of $\planb$ 
    wrt. $\ppi$ s.t. $\card{\prec''} < \card{\prec}$;
  \end{enumerate}
\end{enumerate}
\end{definition}


\noindent
Note that the previous publication~\cite{Backstrom:ewsp93}
used the terms \emph{LC1-minimality\/} for minimal-constrained deordering
and \emph{LC2-minimality\/} for minimum-constrained reordering.
This change in terminology has been done with the hope that more will be gained
in clarity than is lost by confusion.

It is easy to see that minimum-constrainment is a stronger criterion than
minimal-constrainment---any minimum-constrained deordering of a plan $\plan$ 
is a   minimal-constrained deordering of $\plan$, but the opposite is not true.
As an example, consider the plan in Figure~\ref{fig:lc-min}a.
If removing all ordering constraints from action C, the result is the plan 
in Figure~\ref{fig:lc-min}b, which is still valid.
This plan has an order of size 3 (there is one implicit transitive order) and
it is a minimal-constrained deordering since no further deordering
can be made.
It is not a minimum-constrained deordering, however, since
if instead breaking the ordering constraints between the subsequences AB and
CB, the result is the plan in Figure~\ref{fig:lc-min}c, which is also valid.
This plan has an ordering of size 2 and it can easily be seen that
it is a minimum-constrained deordering, and that it happens to coincide with the
minimum-constrained reordering in this case.
This coincidence is not always the case, however, since a reordering is allowed 
to do more modifications than a deordering; a minimum deordering can obviously 
never have a smaller ordering relation than a minimum reordering.
Examples of this difference was shown already in Section~\ref{sec:example},
where Figure~\ref{fig:deordered-ass-plan}a shows a minimum-constrained
deordering and Figure~\ref{fig:deordered-ass-plan}b shows a minimum-constrained
reordering.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \input{lc-min-ex.latex}
    \caption{The difference between minimal and minimum constrained deorderings.}
    \label{fig:lc-min}
  \end{center}
\end{figure}

Other alternative definitions of least-constrainment could be, for instance,
to maximize the unorderdness or to minimize the length of the longest chain
in the modified plan.
However, to find a de-/reordering which  has as many pairs of unordered actions
as possible is the dual of computing a minimum de-/reordering and it is, thus,
already covered.
Minimizing the length of the longest chain is a condition which may be relevant
when actions can be executed in parallel and the overall execution time is
to be minimized.
However, since the number of ordering constraints is quadratic in the length of 
a chain (because of transitive arcs), minimizing the size of the relation
will often be a reasonable approximation of minimizing the chain length.
Furthermore, minimizing the longest chain is still a rather weak condition for
this purpose, so it is better to study directly the problem of finding shortest
parallel executions of plans, which will be done later in this \paper.

Another issue is whether to minimize the size of the ordering relation as
given, or to reduce the transitive or reductive closure of it.
Since plans may have superfluous orderings with no particular purpose, it is
reasonable to standardize matters and either add all possible transitive arcs,
getting the transitive closure, or to remove all transitive arcs, getting the
reductive closure.
The choice between these two is not important for the results to be proven.
However, minimizing the transitive closure will give a preference to plans
with many unordered short chains of actions over plans with a few long chains,
and so seems to coincide better with  the term 'least constrained'.

\subsection{Computing Least-constrained Plans}

Minimal deordering is weaker than the two other least-constrainment
criteria considered, but it is the least costly to achieve---it is the only one of
the three criteria which can be satisfied by a polynomial-time modification
to a plan.

\begin{definition}

  The search problem \textsc{Minimal-Constrained Deordering (MlCD)\/}  is
  defined as follows:\\
  Given: A \textsc{ppi\/} $\ppi$ and a $\ppi$-valid plan $\plan$.\\
  Output: A minimal-constrained deordering of $\plan$ wrt. $\ppi$.
\end{definition}

\begin{theorem}\label{th:MlCD-polynomial}
  \textsc{MlCD\/} can be solved in polynomial time
  if validity for p.o.~plans can be tested in polynomial time.
\end{theorem}


\begin{proof}
  Consider algorithm MLD in Figure~\ref{fig:MLD-algorithm} and let
  $\planb=\tuple{\actset,\precb}$ be the plan output by the algorithm
  on input $\plan=\tuple{\actset,\prec}$.
  The plan $\planb$ is obviously a valid deordering of $\plan$ wrt. $\ppi$.
  It is further obvious from the termination condition in the while loop
  that there is no other ordering $\precc\subset\precb$ s.t. 
  $\tuple{\actset,\precc}$ is $\ppi$-valid.
  It follows that $\planb$ is a minimal-constrained deordering.
  Since the algorithm obviously runs in polynomial time, the theorem follows.
\end{proof}

\noindent
Furthermore, if validity testing is expensive, this will be the dominating
cost in the \textsc{MLD} algorithm.

\begin{corollary}
  If validity testing for p.o.~plans can be solved in time $O(f(n))$ for some
  function $f(n)$, then \textsc{MlCD\/} can be solved in 
  $O(\max\{n^{7/2},n^2f(n)\})$ time.
\end{corollary}

\begin{figure}[htb]
\begin{program}
\prgprocedure MLD
\prgbeginblock
  \prglin Input:  A valid p.o.~plan $\plan=\tuple{\actset,\prec}$ and a 
    \textsc{ppi\/} $\ppi$
  \prglin Output: A minimal deordering of $\plan$
\prgendblock
\prgwhile there is some $\edge\in\prec$ s.t.  
     $\tuple{\actset,(\prec \setdiff \set{\edge})^+}$ is $\ppi$-valid \prgdo
  \prglin remove $\edge$ from $\prec$
\prgendwhile
\prglin \prgreturn $\tuple{\actset,\prec^+}$; 
\end{program}
\caption{The minimal-deordering algorithm MLD}
\label{fig:MLD-algorithm}
\end{figure}

In particular, note that plan validation is polynomial for 
the usual variant of
propositional STRIPS without conditional actions 
\cite[Theorem~5.9]{Nebel:Backstrom:ai94}.
More precisely, this proof pertains to the \emph{Common Propositional
STRIPS formalism (CPS)\/} and, thus, holds also for the other common
variants of propositional STRIPS, like Ground TWEAK~\cite{Backstrom:ai95}.
Furthermore, note that in practice it may not be necessary to compute 
the transitive closure either for the output plan or for validating a plan
in the algorithm.

While minimum de-/reordering are stronger criteria than minimal deordering,
they are also more costly to achieve.

\begin{definition}
  The decision problem \textsc{Minimum-Constrained Deordering (MmCD)\/}  is
  defined as follows:\\
  Given: A \textsc{ppi\/} $\ppi$, a $\ppi$-valid plan $\plan$ 
  and  an integer $k \geq 0$.\\
  Question: Is there a deordering $\tuple{\actset,\prec}$ of $\plan$ s.t.
  $\card{\prec} \leq k$?
\end{definition}

\begin{definition}
  The decision problem \textsc{Minimum-Constrained Reordering (MmCR)\/}  is
  defined as follows:\\
  Given: A \textsc{ppi\/} $\ppi$, a $\ppi$-valid plan $\plan$ 
  and  an integer $k \geq 0$.\\
  Question: Is there a reordering $\tuple{\actset,\prec}$ of $\plan$ s.t.
  $\card{\prec} \leq k$?
\end{definition}

\begin{theorem}\label{th:MmCD-NPhard}
  \textsc{Minimum-Constrained Deordering\/} is NP-hard.
\end{theorem}

\begin{proof}
Proof by reduction from \textsc{Minimum Cover\/}
\cite[p.~222]{Garey:Johnson:CI}, which is NP-complete.
Let $S=\set{p_1,\ldots,p_n}$ be a set of atoms, $C=\set{C_1,\ldots,C_m}$ a
set of subsets of $S$ and $k\leq\card{C}$ a positive integer.
A \emph{cover\/} of size $k$ for $S$ is a subset $C'\subseteq C$ s.t. 
$\card{C'}\leq k$ and $S\subseteq\union_{T\in C'}T$.
Construct, in polynomial time, the GT \textsc{ppi\/} 
$\ppi=\tuple{\emptyset,\set{r}}$ and the $\ppi$-valid
t.o.~plan $\plan=\seq{\act_1,\ldots,\act_m,\act_S}$ where 
$\pre(\act_i)=\emptyset$ and
$\post(\act_i)=C_i$ for $1\leq i\leq m$, and further
$\pre(\act_S)=S$ and $\post(\act_S)=\set{r}$.
Obviously, $S$ has a minimum cover of size $k$ iff there exists some
$\ppi$-valid p.o.~plan 
$\planb=\tuple{\set{\act_1,\ldots,\act_m,\act_S} ,\prec}$ 
s.t. $\card{\prec}\leq k$, since only those actions contributing to the cover need
remain ordered wrt. to $\act_S$
\end{proof}

\begin{corollary}\label{co:MmCR-NPhard}
  \textsc{Minimum-Constrained Reordering\/} is NP-hard.
\end{corollary}

\begin{corollary}
  \textsc{Minimum-Constrained Deordering\/} and 
  \textsc{Minimum-Con\-strained \linebreak Reordering\/} both remain NP-hard even 
  when 
  restricted to   GT plans where  the actions have only positive pre- and
  post-conditions.
\end{corollary}

\begin{theorem}\label{th:MmCD/MmCR-containment}
  If validity for p.o.~plans is in some complexity class C, then 
  \textsc{Minimum-Constrained Deordering\/} and
  \textsc{Minimum-Constrained Reordering\/} are in $NP^C\!$.
\end{theorem}


\begin{proof}
  Guess a solution, verify that it is a de-/reordering and then validate 
  it using an oracle for C.
\end{proof}

\noindent
For most common planning formalisms without conditional actions and 
context-dependent effects, minimal de-/reordering is NP-complete.

\begin{theorem}
  If validity for p.o.~plans can be tested in polynomial time, then 
  \textsc{Minimum-Constrained Deordering\/} and
  \textsc{Minimum-Constrained Reordering\/} are NP-complete.
\end{theorem}

\begin{proof}
  Immediate from Theorems~\ref{th:MmCD-NPhard} and~\ref{th:MmCD/MmCR-containment}
  and from Corollary~\ref{co:MmCR-NPhard}.
\end{proof}

It follows immediately that the corresponding search problems, that is,
the problems of \emph{generating\/} a minimum-constrained de-/reordering 
are also NP-hard (and even NP-equivalent if validity 
testing is tractable). 

Furthermore, \textsc{MmCD} and \textsc{MmCR} are not only hard to solve optimally,
but even to approximate.
Neither of these problems is in the approximation class 
APX~\cite{Crescenzi:Panconesi:ic91}, \ie\ neither
problem can be approximated within a constant factor.
(Both here and elsewhere in this \paper\ the term approximation is used in the
constructive sense, that is the results refer to the existence/non-existence
of algorithms producing an approximate solution in polynomial time).

\begin{sloppypar}
\begin{theorem}
  \textsc{Minimum-Constrained Deordering\/} and
  \textsc{Minimum- Con\-strained Reordering\/} cannot 
  be approximated within
  a constant unless $NP\in\text{DTIME}(n^{poly\ log\ n})$.
\end{theorem}
\end{sloppypar}

\begin{proof}
  Suppose there were a polynomial-time algorithm A  approximating
  \textsc{MmCD} within a constant. 
  Since the reduction in  the proof of Theorem~\ref{th:MmCD-NPhard} preserves
  the solutions exactly, also approximations are preserved.
  Hence,  \textsc{Minimum Cover} could  be approximated within a constant, 
  but this is impossible unless  
  $NP\in\text{DTIME}(n^{poly\ log\ n})$ \cite{Lund:Yannakakis:jacm94}, 
  which contradicts the assumption.
  The case for \textsc{MmCR} is a trivial consequence.
\end{proof}

If using the number of propositional atoms in the plan as a measure of its size,
this bound can be strengthened to $(1-\epsilon)\ln\card{\atomset}$ for
arbitrary $\epsilon$ unless $NP\in\text{DTIME}(n^{\log\log\ n})$
 by substituting such a result for \textsc{Minimum Cover}
\cite{Feige:stoc96} in the proof above.

 

\section{Parallel Plans}\label{sec:parallel-plans}

In order to study the problem of finding a shortest parallel execution of
a plan, the formalisms used so far are not quite sufficient.
Since they lack a capability of modelling when actions can be executed in 
parallel or not, it is impossible to say with any reasonable precision how a 
certain action ordering will affect the parallel execution time.
Partial-order plans are sometimes referred to as parallel plans in 
literature.
This is misleading, however.
That two actions are left unordered in such a plan means that they can be executed 
in either order, without affecting the validity of the plan, but in the general
case there is no guarantee that the plan will remain valid also if the
executions of the actions overlap temporally.
In some cases, unorderedness means that parallel or overlapping execution is
allowed, while in other cases it does not mean that, depending on the action
modelling and its underlying domain assumptions.
In the first case, the plan must have a stronger ordering committment, any
two actions that must not have overlapping executions must be ordered, thus
making the plan over-committed.

In order to distinguish the two cases, a concept of parallel plans will be
introduced below. 
A parallel plan is a partial-order plan with an extra relation,
a \emph{non-concurrency relation}, which tells which actions must not be
executed in parallel.
In this \paper\ two actions are considered parallel if their executions have
any temporal overlap at all.
Plans where all unordered actions can be executed in parallel constitute 
the special case of \emph{definite\/} parallel plans.


\begin{definition}\label{def:par-po-plan}
A \emph{parallel plan\/} is a triple 
$\plan=\tuple{\actset,\prec,\nonpar}$,
where $\tuple{\actset,\prec}$ is a p.o.~plan and $\nonpar$ is an
irreflexive, symmetric relation on $\actset$.
A \emph{definite\/} parallel p.o plan is a parallel plan
$\plan=\tuple{\actset,\prec,\nonpar}$ s.t.
$\nonpar \subseteq (\prec\union\prec^{-1}) $.
\end{definition}

\noindent
Intuitively, a parallel plan is a p.o.~plan extended with an extra
relation, $\nonpar$ (a \emph{non-concurrency\/} relation), expressing which of 
the actions must not be executed in parallel.
This relation is primarily intended to convey information about actions that
are unordered under the $\prec$ relation, although it is allowed to relate
also such actions.
That is, the $\nonpar$ relation is intended to capture information about
whether two actions can be executed in parallel or not, in general.
That two actions are ordered in a plan forbids executing them in parallel in 
this particular plan, but does not necessarily mean that the actions could
not be executed in parallel under different circumstances. 
Planning algorithms frequently produce overcommitted orderings on plans, 
and the whole purpose of this \paper\ is to study the problem of optimizing plans 
by finding and removing such overcommitted orderings.
Hence, there are no  restrictions in general on the relation $\nonpar$  in 
addition to those in Definition~\ref{def:par-po-plan}.
For instance,  $\act\prec\actb$ does not imply that $\act\nonpar\actb$.
However,  the non-concurrency relation will frequently be constrained to
satisfy the post-exclusion principle.
%
\begin{definition}
  A parallel GT plan $\plan=\tuple{\actset,\prec,\nonpar}$ satisfies
  the \emph{post-exclusion principle\/} iff for all actions $\act,\actb\in\actset$,
   $\act\nonpar\actb$ whenever there is some atom $\atom$ s.t.
   $\atom\in\post(\act)$ and $\lnot\atom\in\post(\actb)$.
\end{definition}

The definition of plan validity is directly inherited from p.o.~plans.
%
\begin{definition}
  Given a \textsc{ppi\/} $\ppi$, a parallel plan $\tuple{\actset,\prec,\nonpar}$
  is $\ppi$-valid iff the p.o.~plan $\tuple{\actset,\prec}$ is $\ppi$-valid.
\end{definition}

\noindent
The non-concurrency relation is, thus, not relevant for deciding whether a plan
is valid or not.
Instead, it is used for constraining how parallel plans may be executed and it is
the core concept behind the definition of parallel executions.

Consider, for instance, the GT plan 
$\tuple{\set{A,B,C},\set{\tuple{A,B}},\set{\tuple{B,C}}}$ which is shown
in Figure~\ref{fig:nonpar-ex} (arrows denote ordering relations and dashed 
lines denote nonconcurrency relations).
This plan is valid wrt. the \textsc{ppi\/} $\ppi=\tuple{\emptyset,\set{r,s}}$, 
that is the final value of the atom $q$ does not matter.
Since $B\nonpar C$ holds the actions B and C are constrained not 
to be executed in parallel, but may be executed in either order, that is,
the plan is not definite.
This could be because the post-exclusion principle is employed, or for some
other reason.
Although $A\nonpar B$ does not hold the actions A and B clearly cannot be 
executed in parallel, since $A\prec B$ holds.
There are four ways to execute this plan, in either of the
three sequences A,B,C; A,C,B and C,A,B, or by executing A and C in parallel,
followed by B (unit length is assumed).
Also note that this plan would no longer be valid if the goal contained either
$q$ or $\lnot q$, since the final truth value of $q$ depends on the actual
execution order.
Furthermore, any reordering of the plan would have to keep the ordering 
constraint $A\prec B$ to satisfy the validity criterion, why it is not
necessary to have the constraint $A\nonpar B$.
It would do no harm here  to include this restriction, but in more
complex plans it may be an over-constrainment, if there are several producers
for the atom $p$ to choose between, for instance.
To sum up, the non-concurrency relation should primarily be used to mark which
actions must not be in parallel in addition to those already forbidden to be
in parallel because of validity.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \input{nonpar-ex.pstex_t}
    \caption{A parallel plan}
    \label{fig:nonpar-ex}
  \end{center}
\end{figure}

\noindent

This framework for parallel plans admits  expressing possible parallelism only;
necessary parallelism is out of the scope of this \paper\ and requires a
planner having access to and being able to make use of further additional 
information, perhaps a temporal algebra.
Furthermore, a set of non-concurrent actions can easily be expressed by making
all actions in the set pairwise non-concurrent, but the formalism is not
sufficient to say that $k$ of the actions, but not more, in such a set may 
be executed in parallel.
Similarly, it is not possible to express that an action must executed before
or after an interval, or that two sets of actions must have non-overlapping
executions.

\begin{definition}
  Let $\plan=\tuple{\actset,\prec,\nonpar}$ be a parallel plan
  and let the function $\duration: \actset\mapsto\naturals$ denote the
  duration of each action.
  A \emph{parallel execution\/} of $\plan$ is a function
  $\release: \actset\mapsto\naturals$, denoting release times for the
  actions in $\actset$, satisfying that for all $\act,\actb\in\actset$,
  \begin{enumerate}
  \item if $\act\prec\actb$, then 
    $\release(\act)+\duration(\act)\leq\release(\actb)$ and
  \item if $\act\nonpar\actb$, then either
    \begin{enumerate}
    \item $\release(\act)+\duration(\act)\leq\release(\actb)$ or
    \item $\release(\actb)+\duration(\actb)\leq\release(\act)$.
    \end{enumerate}
  \end{enumerate}
  The \emph{length\/} of the parallel execution is defined as
  $\max_{\act\in\actset}\set{\release(\act)+\duration(\act)}$,
  \ie, the latest finishing time of any action.
  A \emph{minimum parallel execution\/} of plan is a parallel execution
  with minimum length among all parallel executions of the plan.
  The \emph{length\/} of a parallel plan $\plan$, denoted $\length(\plan)$,
  is the length of the minimum parallel execution(s) for $\plan$.
\end{definition}

\noindent
Obviously, every parallel plan has a parallel
execution of length $\sum_{\act\in\actset}\duration(a)$ (which is the
trivial case of sequential execution).
Furthermore,
in certain cases, hardness results will be strengthened by restricting the
duration function.

\begin{definition}
  The special case where $\duration(\act)=1$ for all $\act\in\actset$
  is referred to as the \emph{unit time assumption.\/}
\end{definition}

Deciding whether a release-time function is a parallel execution is tractable.

\begin{theorem}\label{th:verify-par-exec}
  Given a parallel plan $\plan=\tuple{\actset,\prec,\nonpar}$, a
  duration function $\duration: \actset\mapsto\naturals$ and
  a release-time function $\release: \actset\mapsto\naturals$, it can be decided in
  polynomial time whether $\release$ is a parallel execution for $\plan$
  and, in the case it is, what the length of this execution is.
\end{theorem}

\begin{proof}
  Trivial.
\end{proof}

Consider the plan in Figure~\ref{fig:nonpar-ex} and three release-time 
functions $\release_1$, $\release_2$ and $\release_3$, defined as follows
\begin{eqnarray*}
  \release_1(A)=1 & \release_1(B)=2 & \release_1(C)=3 \\
  \release_2(A)=1 & \release_2(B)=2 & \release_2(C)=1 \\
  \release_3(A)=1 & \release_3(B)=2 & \release_3(C)=2.
\end{eqnarray*}
Both $\release_1$ and $\release_2$ are parallel executions of the plan, while
$\release_3$ is not.
Furthermore, $\release_2$ is a minimum parallel execution for the plan, having
length 2.
However, computing the minimum parallel execution of a parallel plan is 
difficult in the general case.

\begin{definition}
  The decision problem \textsc{Parallel Plan Length (PPL)} is defined as 
  follows:\\
  Given: A parallel plan $\plan=\tuple{\actset,\prec,\nonpar}$,
  a duration function $\duration$ and an integer~$k$.\\
  Question: Does $\plan$ have a parallel execution of length $k$ or
  shorter?
\end{definition}

\begin{theorem}\label{th:PPL-NPhard}
  \textsc{Parallel Plan Length} is NP-hard.
\end{theorem}

\begin{proof}
Hardness is proven by transformation from  
\textsc{Graph K-Colourability} \cite[p. 191]{Garey:Johnson:CI}, which is 
NP-complete.
Let $G=\tuple{V,E}$ be an arbitrary undirected graph, where
$V=\set{v_1,\ldots,v_n}$.
Construct, in polynomial time, a GT \textsc{ppi\/} as follows.
Define the \textsc{ppi\/} $\ppi=\tuple{\emptyset,\set{\atom_1,\ldots,\atom_n}}$.
Also define the parallel plan $\plan=\tuple{\actset,\emptyset,\nonpar}$,
where $\actset$ contains one action $\act_i$ for each vertex $v_i\in V$,
s.t. $\pre(\act_i) =\emptyset$ and 
$\post(\act_i)=\set{\atom_i,\atomb_i}\union
 \set{\lnot\atomb_j \st \set{v_i,v_j}\in E}$.
Finally, let $\act_i\nonpar\act_j$ iff $\set{v_i,v_j}\in E$, which satisfies
the post-exclusion principle.
The plan $\plan$ just constructed is obviously $\ppi$-valid.
It is easy to see that $G$ is $k$-colourable iff $\plan$ has a parallel
execution of length $k$ wrt. $\ppi$ since each colour of $G$ will correspond
to a unique release time in the parallel execution of $\plan$.
\end{proof}

\begin{corollary}
  \textsc{Parallel Plan Length} remains NP-hard  even when restricted to
  GT actions with empty preconditions and under the assumption of unit time and 
  the post-exclusion principle.
\end{corollary}

\begin{theorem}\label{th:PPL-in-NP}
  \textsc{Parallel Plan Length} is in NP.
\end{theorem}

\begin{proof}
  Guess a parallel execution. Then verify it, which can be done in polynomial
  time according to Theorem~\ref{th:verify-par-exec}.
\end{proof}

\noindent
Computing a minimum parallel execution of a plan is tractable for the special case
of definite plans, however.

\begin{theorem}\label{th:definite-MPE-polynomial}
  \textsc{Parallel Plan Length} can be solved in polynomial
  time for definite parallel plans.
\end{theorem}

\begin{proof}
  Use  the algorithm DPPL (Figure~\ref{fig:DPPL-algorithm}),
  which is a straightforward stratification algorithm for directed DAGs.
\end{proof}

\begin{figure}[htb]
\begin{program}
\prgprocedure DPPL
\prgbeginblock
  \prglin Input:  A definite parallel plan $\plan=\tuple{\actset,\prec,\nonpar}$
  \prglin Output: A minimum parallel execution $\release$ for $\plan$
\prgendblock
\prglin Construct the directed graph $G=\tuple{\actset,\prec}$
\prgfor all $\act\in\actset$ \prgdo
  \prglin $\release(\act) \prgassn 0$
\prgendfor
\prgwhile $\actset \neq \emptyset$ \prgdo
  \prglin Select some  node $\act\in\actset$ without predecessors in $\actset$
  \prgfor all $\actb\in\actset$ s.t. $\act\prec\actb$ \prgdo
    \prglin $\release(\actb) \prgassn
      \max(\release(\actb),\release(\act)+\duration(\act))$
    \prglin $\actset \prgassn \actset-\set{\act}$
  \prgendfor
\prgendwhile
\prglin \prgreturn $\release$
\end{program}
\caption{Algorithm for computing a minimum parallel execution for definite 
  parallel plans.}
\label{fig:DPPL-algorithm}
\end{figure}

\section{Reordering Parallel Plans}\label{sec:parallel-reordering}

Having defined the concept of parallel plan, it is possible to define concepts
similar to the previous least-constrainment criteria which are more appropriate
for minimizing the execution time of parallel plans.

\begin{definition}
Let $\plan=\tuple{\actset,\prec,\nonpar}$ and 
$\planb=\tuple{\actset,\prec',\nonpar}$ be two parallel plans and
$\ppi$ a \textsc{ppi}. Then,
\begin{enumerate}
\item $\planb$ is a \emph{parallel reordering\/} of $\plan$ wrt. $\ppi$ iff 
both $\plan$ and $\planb$ are $\ppi$-valid;
\item $\planb$ is a \emph{parallel deordering\/} of $\plan$ wrt. $\ppi$ iff 
$\planb$ is a parallel reordering of $\plan$ and $\prec'\subseteq\prec$;
\item $\planb$ is a \emph{minimum parallel reordering\/} of $\plan$ wrt. $\ppi$ 
  iff 
  \begin{enumerate}
  \item $\planb$ is a parallel reordering of $\plan$ wrt. $\ppi$ and
  \item no other parallel reordering of $\plan$ wrt. $\ppi$ is of shorter length 
    than  $\planb$;
  \end{enumerate}
\item $\planb$ is a \emph{minimum parallel deordering\/} of $\plan$ wrt. $\ppi$ 
  iff 
  \begin{enumerate}
  \item $\planb$ is a parallel deordering of $\plan$ wrt. $\ppi$ and
  \item no other parallel deordering of $\plan$ wrt. $\ppi$ is of shorter length
    than $\planb$.
  \end{enumerate}
\end{enumerate}
\end{definition}

\noindent
Modifying plans to satisfy either of the latter two criteria is difficult 
in the general case, however.

\begin{definition}
The decision problem \textsc{Minimum Parallel Deordering \textsc{(MmPD)}} 
is defined as  follows.\\
Given: a \textsc{ppi\/} $\ppi$, a parallel plan $\plan$, a duration function
$\duration$ and an integer~$k$.\\ 
Question: Does $\plan$ have a deordering with a  parallel execution of
length $k$ wrt.~$\ppi$?
\end{definition}

\begin{definition}
The decision problem \textsc{Minimum Parallel Reordering \textsc{(MmPR)}} 
is defined as follows.\\
Given: a \textsc{ppi\/} $\ppi$, a parallel plan $\plan$, a duration function
$\duration$ and an integer~$k$.\\ 
Question: Does $\plan$ have a reordering with a  parallel execution of
length $k$ wrt.~$\ppi$?
\end{definition}


\begin{theorem}\label{th:MmPD-NPhard}
  \textsc{Minimum Parallel Deordering} is NP-hard.
\end{theorem}

\begin{proof}
  Similar to the proof of Theorem~\ref{th:MmPD-NPhard}.
  Given a graph $G$ and an integer $k$, construct a \textsc{ppi\/} $\ppi$ and a plan 
  $\plan=\tuple{\actset,\prec,\nonpar}$ in the   same way as in the proof 
  of Theorem~\ref{th:PPL-NPhard}, but let $\prec$ be an arbitrary total order 
  on $\actset$.
  Obviously, $\plan$ is $\ppi$-valid and 
  $\planb=\tuple{\actset,\emptyset,\nonpar}$ is a deordering of $\plan$ s.t.
  no  other deordering of $\plan$ is shorter than  $\planb$.
  Hence, $\planb$, and thus $\plan$, has a deordering with a parallel execution of 
  length $k$ iff $G$ is $k$-colourable.
\end{proof}

\begin{corollary}\label{co:MmPR-NPhard}
  \textsc{Minimum Parallel Reordering} is NP-hard.
\end{corollary}

\begin{corollary}
  \textsc{Minimum Parallel Deordering} and
  \textsc{Minimum Parallel Reordering} remain NP-hard even when restricted to
  totally ordered GT plans  and under the assumptions of unit time and 
  simple concurrency.
\end{corollary}

Note that the restriction to definite input plans is covered by this corollary.
If output plans are also required to be definite, then the reordering case
remains NP-hard.

\begin{theorem}
  \textsc{Minimum Parallel Reordering} remains NP-hard also when the output plan
  is restricted to be definite.
\end{theorem}



\begin{proof}
  Reuse the proof for Theorem~\ref{th:MmPD-NPhard} as follows.
  Let $\release$ be a shortest parallel execution for the plan $\planb$ and
  assume this execution is of length $n$.
  Construct an order $\precb$ on $\actset$ s.t. for all actions 
  $\act,\actb\in\actset$, $\act\precb\actb$ iff 
  $\release(\act)<\release(\actb)$.
  Obviously the plan $\tuple{\actset,\precb,\nonpar}$ is a definite 
  minimum parallel reordering of $\plan$.
  It follows that $\plan$ has a definite parallel reordering of length $k$ iff
  $G$ is $k$-colourable.
\end{proof}

It is an open question whether  minimum deordering remains NP-hard when also
output plans must be definite, but an important special case is polynomial,
as will be proven in the next section.

\begin{theorem}\label{th:MmPR-containment}
   \textsc{Minimum Parallel Deordering} and \textsc{Minimum Parallel Reordering}
   are in $NP^C$ if validation of   p.o.~plans is in some complexity class $C$.
\end{theorem}

\begin{proof}
  Given a plan $\tuple{\actset,\prec,\nonpar}$, a duration function $\duration$
  and a parameter $k$, guess a de/reordering $\precb$ and a release-time function 
  $\release$.
  Then verify, using an oracle for $C$, that 
  $\tuple{\actset,\precb,\nonpar}$ is valid.
  Finally,  verify that  $\release$ is a parallel  execution of length $\leq k$,
  which is polynomial according to Theorem~\ref{th:verify-par-exec}.
\end{proof}

\begin{theorem}
  Minimum parallel de-/reordering is NP-complete if p.o.~plans can be validated
  in polynomial time.
\end{theorem}

\begin{proof}
  Immediate from Theorems~\ref{th:MmPD-NPhard} and~\ref{th:MmPR-containment}
  and Corollary~\ref{co:MmPR-NPhard}.
\end{proof}

The problems \textsc{MmPD} and \textsc{MmPR} are not only hard to solve
optimally, but also  to approximate.


\begin{theorem}
  \textsc{Minimum Parallel Deordering} and \textsc{Minimum Parallel Reordering}
   cannot be approximated within  $\card{\actset}^{1/7-\epsilon}$
   for any $\epsilon>0$,  unless P=NP.
\end{theorem}

\begin{proof}
  Suppose there were a polynomial-time  algorithm A approximating 
  \textsc{MmCD} within $\card{\actset}^{1/7-\epsilon}$ for some
  $\epsilon>0$.
  Then it is immediate from the proof of 
  Theorem~\ref{th:MmPD-NPhard} that also \textsc{Graph K-Colourability}
  could  be approximated within $\card{\actset}^{1/7-\epsilon}$,
  which is impossible unless  P=NP \cite{Bellare:etal:focs95}.
\end{proof} 

\noindent
With the same reasoning, this bound can be strengthened to
$\card{\actset}^{1-\epsilon}$, 
under the assumption that co-RP$\neq$NP~\cite{Feige:Kilian:ccc96}.


\section{Restricted Cases}\label{sec:restr-cases}

Since the problems of computing  minimum de-/reorderings are very difficult,
and are even difficult to approximate, an alternative way of tackling them could
be to study restricted cases.
One special case already considered is the restriction to definite plans only.
While the problem \textsc{MmPR} is still NP-complete under this restriction,
it is an open question whether also \textsc{MmPD} is NP-complete.
A positive result can be proven, though, to the effect that \textsc{MmPD}
is polynomial for definite plans for a large class of planning languages, including 
most of the commonly used ones.
This result will be proven by generalising an algorithm from the literature
for deordering total-order plans.

Based on the (not necessarily true) argument that it is easier to generate a 
t.o.~plan than a p.o.~plan when using complex action representations,
Regnier and Fade \citeyear{Regnier:Fade:ewsp91,Regnier:Fade:ria91} have presented 
an algorithm for  converting a t.o.~plan into a p.o.~plan.
The resulting plan has the property that all its unordered actions can be 
executed in parallel, that is, the plan is definite.
The authors of the algorithm further claim  that the algorithm finds all pairs 
of actions that can be executed in parallel and, hence, the plan can be 
post-processed to find an optimal parallel execution.
They do not define what they mean by this criterion, however.

Incidentally, the algorithm proposed by Regnier and Fade is a special case of 
an algorithm earlier proposed for the same problem 
by Pednault~\citeyear{Pednault:rap86}, who did not make any claims about
optimality.
If removing from Regnier and Fade's algorithm all details relevant only
for their particular implementation and planning language, the two
algorithms  coincide and they are thus presented here as one single algorithm, 
the PRF algorithm\footnote{Here and afterwards, the algorithms from the literature
will be referred to by acronyms consisting of the initials of its authors,
in this case Pednault, Regnier and Fade.} (Figure~\ref{fig:PRF-algorithm}).
PRF is slightly modified from the original algorithms.
First, it does not assume that the input plan is totally ordered, since it turns out to
be sufficient that it is a definite partial-order plan.
Second, PRF returns a parallel plan, rather than a p.o.~plan---a harmless modification
since the only additional piece of information is the non-concurrency relation,
which is already given as input, either explicitly or implicitly.
Third, PRF returns the transitive closure of its ordering relation.
This is by no means necessary, and is motivated, as usual, by conforming to
the definitions of this \paper.

\begin{figure}[h]
\begin{program}
\prgprocedure PRF;
\prgbeginblock
  \prglin Input: A \textsc{ppi\/} $\ppi$, a $\ppi$-valid definite p.o.~plan 
  $\tuple{\actset,\prec}$
    and a non-concurrency relation~$\nonpar$
  \prglin Output: A $\ppi$-valid parallel plan
\prgendblock
\prgfor all  $\act,\actb\in\actset$ s.t. $\act\prec\actb$ \prgdo
 \prgif  $\act \nonpar \actb$ \prgthen
  \prglin Order $\act\precb\actb$;
 \prgendif
\prgendfor
\prglin \prgreturn $\tuple{\actset,\precb^+,\nonpar}$; 
\end{program}
\caption{The PRF algorithm}
\label{fig:PRF-algorithm}
\end{figure}

Obviously, PRF computes a deordering of its input, and  it is unclear whether it is possible
to compute a minimal definite deordering in polynomial time.
However, the algorithm has been abstracted here to a very general formalism,
and an analysis for restricted formalisms reveals more about its performance.
The language used by Regnier and Fade is unnecessarily restricted so the algorithm
will be shown to work for a considerably more general formalism, based on
generalising and abstracting the concepts of producers, consumers and threats
used in most common planners and planning languages, \eg\ STRIPS and TWEAK.
This formalism will be referred to as the \emph{Producer-Consumer-Threat 
formalism (PCT)}.

Let $prod(\act,\cond)$ denote that $\act$ produces the condition $\cond$,
$cons(\act,\cond)$ that $\act$ consumes $\cond$ and
$threat(\act,\cond)$ that $\act$ is a threat to $\cond$.
To simplify the definitions, the standard transformation will be used of simulating
the initial and goal states with actions.
That is, every PCT plan contains an action ordered before all other actions
which consumes nothing and produces the initial state.
Similarly, there is an action ordered after all other actions which consumes
the goal state and produces nothing.
This means that the \textsc{ppi\/} is contained within the plan itself, so all 
references to \textsc{ppi}s can be omitted in the following.
Validity of plans can then be defined as follows.

\begin{definition}
A t.o. PCT plan $\seq{\act_1,\ldots,\act_n}$ is valid iff
for all $i$, $1\leq i\leq n$ and all conditions $\cond$ s.t. 
$cons(\act_i,\cond)$, there is some $j$, $1\leq j<i$ s.t. 
$prod(\act_j,\cond)$
and there is no $k$, $j\leq k\leq i$ s.t. $threat(\act_k,\cond)$.
A p.o. PCT plan is valid iff all topological sortings of it are valid.
\end{definition}

Chapman's Modal-truth Criterion (MTC) \cite{Chapman:ai87}
can be abstracted to the PCT formalism and be analogously used for validating
p.o.~plans.

\begin{definition}\label{df:AMTC}
  The \emph{modal truth criterion (MTC)\/} for a PCT plan 
  $\tuple{\actset,\prec}$ is:
  \begin{center}
  \begin{tabbing}
    $\forall \act_C \forall \cond ($\=$cons(\act_C,\cond)\limp$ \+\\
    $\exists \act_P($\=$prod(\act_P,\cond)\land \act_P\prec\act_C\land$ \+\\
    $\forall \act_T($\=$threat(\act_T,\cond)\limp$ \+\\
    $\act_C\prec\act_T\lor$\\
    $\exists \act_W(prod(\act_W,\cond) \land 
    \act_T\prec\act_W \land \act_W\prec\act_C))))$
  \end{tabbing}
  \end{center}
\end{definition}

\begin{theorem}\label{th:MTC-is-validity}
  The MTC holds for a PCT plan $\plan$ iff it is valid.
\end{theorem}

\begin{proof}
  Trivial generalization of the proofs leading to Theorem~5.9 in Nebel and 
  Bäckström \citeyear{Nebel:Backstrom:ai94}.
\end{proof}

Only a minimum of constraints  for when two actions may not be executed
 in parallel will be required.
These constraints are  obeyed by most planners in the AI literature.


\begin{definition}\label{df:simple-concurrency}
  \emph{Simple concurrency\/} holds if for all actions $\act$, $\actb$
  s.t. $\act\neq\actb$, the non-concurrency relation satisfies the following
  three conditions
  \begin{enumerate}
  \item $prod(\act,\cond) \land cons(\actb,\cond) \limp \act\nonpar\actb$
  \item $prod(\act,\cond) \land threat(\actb,\cond) \limp \act\nonpar\actb$
  \item $cons(\act,\cond) \land threat(\actb,\cond) \limp \act\nonpar\actb$
  \end{enumerate}
\end{definition}

\noindent
Note that it is not required that two producers, two consumers or 
two threats of
the same condition are non-concurrent, thus allowing, for instance,
plans with multiple producers, \eg\ Nebel and 
Bäckström~\citeyear[Fig.~4]{Nebel:Backstrom:ai94} and
Kambhampati~\citeyear{Kambhampati:ai94}.
The axioms do not prevent adding such restrictions, though.
Furthermore, note that the definition only states a necessary condition for
non-concurrency---it is perfectly legal to add further non-concurrency
constraints on the actions in a plan.
It may also be worth noting that the MTC requires producers and threats to be
ordered only if there is a correpsonding consumer, while a definite plan
satisfying the simple concurrency criterion always require them to be ordered.

The following observation about PRF is immediate from the algorithm
and  will be used in the proofs below.

\begin{observation}\label{lm:PRF-characterization}
  If $\tuple{\actset,\prec,\nonpar}$ is the input to PRF and
  $\tuple{\actset,\precb,\nonpar}$ is the corresponding output,
  then it holds that
  $\act\precb\actb \tiff \act\prec\actb \tand \act\nonpar\actb$.
\end{observation}

\noindent
Based on this lemma, it can be proven that PRF preserves validity.

\begin{lemma}\label{lm:PRF-preserves-validity}
  If the plan input to PRF is a valid PCT plan and $\nonpar$ satisfies the
  simple concurrency criterion, then the output plan is valid.
\end{lemma}

\begin{proof}
  Let $\plan=\tuple{\actset,\prec,\nonpar}$ be the input plan and
  $\planb=\tuple{\actset,\precb,\nonpar}$ the output plan.
  Since $\plan$ is valid, it follows from Theorem~\ref{th:MTC-is-validity}
  that the MTC holds for $\plan$.
  Adding the implied simple-concurrency constraints to the MTC yields 
  the  following  condition:
  \begin{center}
  \begin{tabbing}
    $\forall \act_C \forall \cond ($\=$cons(\act_C,\cond)\limp$ \+\\
    $\exists \act_P($\=$prod(\act_P,\cond)\land 
      \act_P\prec\act_C \land \act_P\nonpar\act_C\land$ \+\\
    $\forall \act_T($\=$threat(\act_T,\cond)\limp$ \+\\
    $(\act_C\prec\act_T \land \act_C\nonpar\act_T) \lor $\\
    $\exists \act_W(prod(\act_W,\cond) \land 
    $\=$\act_T\prec\act_W \land  \act_T\nonpar\act_W \land $\+\\
    $\act_W\prec\act_C \land \act_W\nonpar\act_C))))$.
  \end{tabbing}
  \end{center}
  By applying  Observation~\ref{lm:PRF-characterization} this can be simplified
  to:
  \begin{center}
  \begin{tabbing}
    $\forall \act_C \forall \cond ($\=$cons(\act_C,\cond)\limp$ \+\\
    $\exists \act_P($\=$prod(\act_P,\cond)\land \act_P\precb\act_C\land$ \+\\
    $\forall \act_T($\=$threat(\act_T,\cond)\limp$ \+\\
    $\act_C\precb\act_T\lor$\\
    $\exists \act_W(prod(\act_W,\cond) \land 
    \act_T\precb\act_W \land \act_W\precb\act_C))))$,
  \end{tabbing}
  \end{center}
  which is the MTC for the plan $\planb$.
  Once again using Theorem~\ref{th:MTC-is-validity}, it follows that $\planb$
  is valid.
\end{proof}

\noindent
This allows for proving that PRF produces definite minimum deorderings
of definite PCT plans under simple concurrency.

\begin{theorem}\label{th:PRF-min-deordering}
  If using the PCT formalism and  simple concurrency, then
  PRF produces a minimum-deordered definite version of its input.
\end{theorem}

\begin{proof}
  Let $\plan=\tuple{\actset,\prec,\nonpar}$ be the input plan, which is assumed
  valid and definite, and   $\planb=\tuple{\actset,\precb,\nonpar}$ 
  the output plan.
  It is obvious that $\precb\subseteq\prec$ and it follows from
  Lemma~\ref{lm:PRF-preserves-validity} that $\planb$ is valid, so
  $\planb$ is a deordering of $\plan$.
  It remains to prove that $\planb$ is a minimum deordering of $\plan$.

  Suppose that $\plan$ has a deordering 
  $\planc=\tuple{\actset,\precc,\nonpar}$ s.t. $\card{\precc}<\card{\precb}$.
  Then, there must be some $\act,\actb\in\actset$ s.t.
  $\act\precb\actb$, but not $\act\precc\actb$.
  It can be assumed that $\act\precb\actb$ is not a transitive arc in $\precb$,
  since the transitive closure is anyway computed at the end of the algorithm.
  Since the order $\precb$ is produced by PRF, it follows from
  Observation~\ref{lm:PRF-characterization} that $\act\prec\actb$ and 
  $\act\nonpar\actb$.
  Because of the latter constraint, it is necessary that either,
  $\act\precc\actb$ or $\actb\precc\act$ holds, but only the former is
  possible since $\act\prec\actb$ and $\planc$ is a deordering of $\plan$.
  This  contradicts the assumption, so $\planb$ must be a minimum deordering 
  of $\plan$.
\end{proof}

Since PRF is a polynomial algorithm, it follows that definite minimum deorderings 
of definite PCT plans can be computed in polynomial time under simple concurrency.
Furthermore, since PRF produces definite plans it is possible to actually
compute the shortest parallel execution efficiently.

\begin{theorem}
  If the plan input to PRF is a valid and definite PCT plan satisfying 
  the simple concurrency criterion, then PRF outputs a definite minimum
  deordering of this plan.
\end{theorem} 

\begin{proof}
  PRF runs in polynomial time and  obviously produces definite parallel plans.
  Hence, it follows from Theorem~\ref{th:definite-MPE-polynomial} that a minimum 
  parallel execution for the output plan can be found in polynomial time, 
  which proves the theorem.
\end{proof}

\noindent
It seems likely that this is what Regnier and Fade meant with their optimality
claim, although for a special instance of the PCT formalism.
This result says nothing about the difficulty of finding
a minimum reordering of a plan, since PRF only considers deorderings.
Since minimum deorderings do not approximate minimum reorderings well,
it can be suspected that it is more difficult to compute the latter.
The following theorem confirms this suspicion, showing that the latter problem
remains NP-hard under quite severe restrictions, including the following two.

\begin{definition}
  A GT action $\act$ is \emph{toggling\/} iff for all literals 
  $\lit\in\post(\act)$, it is also the case that $\lnot\lit\in\pre(\act)$.
  A GT action $\act$ is \emph{unary\/} iff $\card{\post(\act)}=1$.
\end{definition}

\begin{theorem}\label{th:MmPD-restr-NPhard}
  \textsc{Minimum Parallel Reordering} remains NP-hard even when restricted to
  total-order GT plans with only toggling unary actions and under
  the assumption of unit time, simple concurrency and that no actions are 
  redundant.
\end{theorem}
%
The proof of this theorem appears in Appendix~A.

While minimum reorderings are more difficult to compute than minimum deorderings,
they can also produce arbitrarily better results.


\begin{theorem}\label{th:RF-no-perf-guarantee}
\textsc{Minimum Parallel Deordering} cannot approximate 
\textsc{Minimum Parallel Reordering} within $\card{A}^k$
for any constant $k\geq 0$.
\end{theorem}
%
The proof of this theorem appears in Appendix~A.

\begin{corollary}
\textsc{Minimum Parallel Deordering} cannot approximate 
\textsc{Minimum Parallel Reordering} within $\card{A}^k$
for any constant $k\geq 0$ even when the problems are restricted to 
GT plans with only positive preconditions and under the assumption of
simple concurrency.
\end{corollary}

It may, thus, appear as though minimum reordering is a preferable, albeit
more costly, operation than minimum deordering.
However, if the plan modification is to be followed by scheduling, it is
no longer obvious that a reordering is to prefer.
Since scheduling may take further information and constraints into account,
\eg\ upper and lower bounds on the release time and limited resources,
a feasible schedule for the original plan may no longer be a feasible schedule for
a reordering of the same plan.
That is, some or all feasible solutions may be lost when reordering a plan.
In contrast to this, deordering a plan is harmless since all previously feasible
schedules are preserved in the deordering.
Of course, the de-/reordered plan may have new and better schedules than the old
plan, which is why the problems studied in this \paper\ are interesting at all.
However, while minimum deordering is a safe and, usually cheap, operation, 
minimum reordering is neither and must thus be applied with more care.
To find a reordering of a plan with an optimum schedule would require combining
minimum reordering and scheduling into one single computation, but it is out
of the scope of this \paper\ to study such combinations.
Suffice it to observe that such a computation is never cheaper than either of
its constituent computations.

\section{Related work}
\label{sec:related-work}

This section analyses and discusses some algorithms suggested in the literature
for generalising the ordering of a plan, in addition to the PRF algorithm
already analysed in the preceeding section.
Also some planners that generate plans with some optimality flavour on the
ordering are discussed.

Some of the algorithms to be analysed use the common trick of simulating
the initial state and the goal of a planning instance by two extra operators, 
in the following way.
Let $\plan=\tuple{\actset,\prec}$ be a plan and $\ppi=\tuple{\init,\goal}$
a \textsc{ppi}, both in the GT language.
Introduce two extra actions $\act_\init$, with
$\pre(\act_\init)=\emptyset$ and $\post(\act_\init)=\init$, and $\act_\goal$,
with $\pre(\act_\goal)=\goal$ and $\post(\act_\goal)=\emptyset$.
Define the plan $\planb=\tuple{\actset\union\set{\act_\init,\act_\goal},\precb}$ 
where $\precb = \prec\union\set{\act_\init\prec\act, \act\prec\act_\goal \suchthat
\act\in\actset}\union\set{\act_\init\prec\act_\goal}$, that is $\act_\init$ 
is ordered before all other actions and
$\act_\goal$ is ordered after all other actions.
The plan $\planb$ is a representation of both the plan $\plan$ and 
the \textsc{ppi\/} $\ppi$.
Such a combined representation will be referred to as a \emph{self-contained plan}.
A self-contained plan is valid iff it is valid wrt. to the \textsc{ppi\/} 
$\tuple{\emptyset,\emptyset}$.
It is trivial to convert a plan and a \textsc{ppi\/} into a corresponding 
self-contained plan and vice versa.
Hence, both ways of representing a plan will be used alternately without 
further notice.

\subsection{The VPC Algorithm}\label{S:find-lc}


Veloso \emph{et al.} \citeyear{Veloso:etal:iapsc90} have presented an algorithm
(here referred to as VPC\footnote{In the original publication the algorithm was
named Build\_Partial\_Order.})
for converting t.o.~plans into  `least-constrained' p.o.~plans.
They use the algorithm in the following context.
First a total-order planner (\textsc{NoLimit}) is used to produce a t.o.~plan.
VPC converts this plan into a p.o.~plan which  is then post-processed
 to determine  which actions can be executed in parallel.
The action language used is a STRIPS-style language allowing quantifiers
and context-dependent effects.
However, the plans produced by the planner, and thus input to VPC, are
ground and without context-dependent effects.
That is, they are ordinary propositional STRIPS plans.
The VPC algorithm is presented in Figure~\ref{fig:VPC-algorithm}, with
a few minor differences in presentation as compared to its original
appearance:
First, the algorithm is presented in the GT formalism, in order to minimize the
number of formalisms in this \paper, but all  preconditions are
assumed to be positive, thus coinciding with the original algorithm.
Second, while the original algorithm returns the transitive reduction of
the computed order it instead returns the transitive closure here, an
unimportant difference in order to coincide with the definition of
plans in this \paper.
Furthermore, Veloso\footnote{Personal communication, oct. 1993.}
has pointed out that the 
published version of the VPC algorithm is incorrect and that a corrected
version exists.
The version presented in Figure~\ref{fig:VPC-algorithm} is this 
corrected version. A proposition is a primary effect if it appears either in the goal or in
the subgoaling chain of a goal proposition.

\begin{figure}
\begin{program}
\prgprocedure VPC;
\prgbeginblock
  \prglin Input: a valid self-contained t.o.~plan $\seq{\act_1,\ldots,\act_n}$
  \prgcontlin where $\act_1=\act_\init$ and $\act_n=\act_\goal$
  \prglin Output: A  self-contained valid p.o.~plan
\prgendblock
\prgfor $1\leq i\leq n$ \prgdo
 \prgfor $\atom\in \precond(\act_i)$ \prgdo
  \prglin Find max $k<i$ s.t. $\atom\in \post(\act_k)$;
   \prgif such a $k$ exists \prgthen 
    \prglin Order $\act_k\prec\act_i$
 \prgendfor
 \prgfor $\lnot\atom\in \post(\act_i)$ \prgdo
  \prgfor $1\leq k< i$ s.t. $\atom\in \precond(\act_k)$ \prgdo
   \prglin Order $\act_k\prec\act_i$
  \prgendfor
 \prgendfor
 \prgfor each primary effect $\atom\in\post(\act_i)$ \prgdo
   \prgfor $1\leq k\leq i$ s.t. $\lnot\atom\in\post(\act_k)$ \prgdo
     \prglin Order $\act_i\prec\act_k$
   \prgendfor
 \prgendfor
\prgendfor
\prgfor $1<i<n$ \prgdo
  \prglin Order $\act_\init\prec\act_i$ and $\act_i\prec\act_\goal$
\prgendfor
\prglin \prgreturn $\tuple{\set{\act_1,\ldots,\act_n},\prec^+}$;
\end{program}

\caption{The VPC algorithm}
\label{fig:VPC-algorithm}
\end{figure}

VPC is a greedy algorithm which constructs an entirely new partial order
by analysing the action conditions, using the original total order only 
to guide  the greedy strategy.
The algorithm is claimed \cite[p.~207]{Veloso:etal:iapsc90} to produce
a `least-constrained' p.o.~plan, although no definition is given of what this
means.
Veloso\footnote{Veloso, \emph{ibid.}} has confirmed that the term
`least constrained plan' was used in a `loose sense' and no optimality
claim was intended.
However, if this term is not defined, then it is impossible to know what problem
the algorithm is intended to solve or how to judge whether it makes any 
improvement over using no algorithm at all.
In the absence of such a definition from its authors, the algorithm will be 
analysed with respect to the least-constrainment criteria defined in
Section~\ref{sec:least-constrainment}.
This is admittedly  a somewhat unfair analysis, but it reveals some 
interesting facts about the algorithm, and about what problems it does not solve.
It is immediate from Theorem~\ref{th:MmCD-NPhard} and
Corollary~\ref{co:MmCR-NPhard}  that VPC cannot be expected to
produce minimum-constrained de-/reorderings.
Perhaps more surprisingly, VPC does not even guarantee that its output is a 
\emph{minimal}-constrained deordering of its input, a problem already proven
trivially polynomial (Theorem~\ref{th:MlCD-polynomial}).
This is illustrated by the following example.

Suppose a total-order planner is given the \textsc{ppi\/} 
$\ppi=\tuple{\emptyset,\set{r,s}}$ as input.
It may then return either of the $\ppi$-valid t.o.~plans $\seq{a,b,c}$ and 
$\seq{a,c,b}$, with action conditions as shown in Figure~\ref{fig:VPC-fail-ex}.
When used as input to VPC, these two t.o.~plans will
give quite different results---the plan $\seq{a,c,b}$ will be converted
to  the p.o.~plan $\plan_1$ in Figure~\ref{fig:VPC-fail-ex},
while the plan $\seq{a,b,c}$ will be converted to the p.o.~plan
$\plan_2$ in Figure~\ref{fig:VPC-fail-ex}.
That is, in the first case VPC produces a plan which is  not only a 
minimal-constrained deordering but even a minimum-constrained deordering,
while in the second case it does not even produce a minimal-constrained 
deordering.\footnote{
  Note that transitive arcs are omitted in the figures, so $\plan_2$ really
  has an ordering relation of size three.
  Although this example would not work if plans had been defined in 
  the equally reasonable way that ordering relations should be intransitive,
  it is possible to construe similar examples also for this case.}

The reason that VPC may fail to produce a minimal-constrained deordering
is that it uses a non-admissible greedy strategy.
Whenever it needs to find an operator $\act$ achieving an effect
required by the precondition of another operator $\actb$, it chooses the
last such action ordered before $\actb$ in the input t.o.~plan.
However, there may be other actions earlier in the plan having 
the same effect and being a better choice.

\begin{figure}
\setlength{\unitlength}{0.7mm}
\thicklines
\begin{center}
\begin{picture}(80,30)(0,0)
% Actions
\fgact{0,10}{a}
\fgact{40,20}{b}
\fgact{40,0}{c}
% Conditions
\fgcnd{12,19}{p}
\fgcnd{12,11}{q}
\fgcnd{37,28}{p}
\fgcnd{53,28}{q}
\fgcnd{53,22}{r}
\fgcnd{37,2}{q}
\fgcnd{53,8}{s}
% Orderings
\put(10,15){\vector(3,1){30}}
\put(10,15){\vector(3,-1){30}}
\put(25,-5){\makebox(0,0){$\plan_1$}}
\end{picture}
%
\begin{picture}(80,30)(0,0)
% Actions
\fgact{0,10}{a}
\fgact{30,10}{b}
\fgact{60,10}{c}
% Conditions
\fgcnd{13,18}{p}
\fgcnd{13,12}{q}
\fgcnd{27,18}{p}
\fgcnd{43,18}{q}
\fgcnd{43,12}{r}
\fgcnd{57,18}{q}
\fgcnd{73,18}{s}
% Orderings
\put(10,15){\vector(1,0){20}}
\put(40,15){\vector(1,0){20}}
\put(35,-5){\makebox(0,0){$\plan_2$}}
\end{picture}
\end{center}

\caption{The p.o.~plans in the failure  example for VPC.}
\label{fig:VPC-fail-ex}
\end{figure}


\subsection{The KK algorithm}

Kambhampati and Kedar~\citeyear{Kambhampati:Kedar:ai94} have presented an 
algorithm for generalising the ordering of a p.o.~plan, using explanation-based 
generalisation.
The algorithm  is based on first constructing a validation structure for the plan 
and then use this as a guide in the generalisation phase.
In the original paper, these computations are divided into two separate
algorithms (EXP-MTC and EXP-ORD-GEN), but are here compacted into one single
algorithm, KK (Figure~\ref{fig:KK-algorithm}).
Furthermore, the version presented here is restricted to ground GT plans, while
the original algorithm can also handle partially instantiated plans.
This is no restriction for the results to be shown below.

\begin{figure}[htb]
  \begin{center}
    \leavevmode
    \begin{program}
      \prgprocedure KK
      \prgbeginblock
        \prglin Input: A valid self-contained p.o.~plan $\tuple{\actset,\prec}$
        \prglin Output: A deordering of the input plan
      \prgendblock
      \prgcomment Build a validation structure $\valstruct$ for the plan
      \prglin $\valstruct\prgassn\emptyset$
      \prglin Let $\seq{\act_1,\ldots,\act_n}$ be a topologically sorted version
        of $\tuple{\actset,\prec}$
      \prgfor $1\leq i\leq n$ \prgdo
        \prgfor $\atom\in \precond(\act_i)$ \prgdo
          \prglin Find min $k<i$ s.t. 
          \prgbeginblock
            \prglin 1. $\atom\in \post(\act_k)$ and
            \prglin 2. there is no $j$ s.t. $k<j<i$ and $\lnot\atom\in\post(\act_j)$
          \prgendblock
          \prglin Add $\clink{\act_k,\atom,\act_i}$ to $\valstruct$
        \prgendfor
      \prgendfor
      \prgcomment Construct a generalised ordering $\precb$ for the plan
      \prgfor each $\tuple{\act,\actb}\in\prec$ \prgdo
        \prglin Add $\tuple{\act,\actb}$ to $\precb$ if either of the following
          holds
          \prgbeginblock
          \prglin 1. $\act=\act_\init$ or $\act=\act_\goal$
          \prglin 2. $\clink{\act,\atom,\actb}\in\valstruct$ for some $\atom$
          \prglin 3. $\clink{\actc,\atom,\act}\in\valstruct$ and
            $\lnot\atom\in\post(\actb)$
          \prglin 4. $\clink{\actb,\atom,\actc}\in\valstruct$ and
            $\lnot\atom\in\post(\act)$  
          \prgendblock
      \prgendfor
      \prglin \prgreturn $\tuple{\actset,\precb}$    
    \end{program}

    \caption{The KK algorithm}
    \label{fig:KK-algorithm}
  \end{center}
\end{figure}

The first part of the KK algorithm constructs a validation structure $\valstruct$
for the plan, that is, an explanation for each precondition of every action in
the plan.
The validity criterion underlying this phase is a simplified version of
Chapmans modal-truth criterion \cite{Chapman:ai87} without white knights.
Since the algorithm is simplified to only handle ground plans here, an explanation
is a causal link $\clink{\act_P,\atom,\act_C}$, meaning that the action $\act_P$
produces the condition $\atom$ which is consumed by the action $\act_C$.
The algorithm constructs exactly one causal link for each precondition, and it
chooses the earliest producer of $\atom$ preceeding $\act_C$ with
no intervening action producing $\lnot\atom$ between this producer and $\act_C$.
The second phase of the algorithm builds a generalised ordering $\precb$ for the
plan based on this validation structure.
To put things simply, only those orderings of the original plan are kept which
either correspond to a causal link in the validation structure or that is
required to prevent a threatening action to be unordered wrt. the actions in
such a causal link.

\begin{sloppypar}
It turns out that also the KK algorithm fails in generating plans that are
guaranteed to be even  minimal-constrained deorderings.
Consider the t.o.~plan $\seq{A,B,C,D}$ with action conditions as indicated
in Figure~\ref{fig:KK-fail}.
This t.o.~plan is valid for the \textsc{ppi\/} $\tuple{\emptyset,\set{r,s,t,u}}$.
Since the KK algorithm always chooses the earliest possible producer of a
precondition for the validation structure, it will build the validation 
structure $\{\clink{A,p,D}, \clink{A,s,\act_\goal}, \clink{B,q,D}, 
\clink{B,t,\act_\goal}, \clink{C,r,\act_\goal}, \clink{D,u,\act_\goal}\}$.
Hence, the final ordering produced by KK will be as shown in 
Figure~\ref{fig:KK-fail}a.
However, this plan is not a minimal-constrained deordering of the original
plan, since it can be further deordered as shown in Figure~\ref{fig:KK-fail}b
and remain valid.
In this example, the input plan was totally ordered.
In the case of partially ordered input plans, the behaviour of the algorithm
depends on the particular topological order choosen.
So the algorithm may or may not find a minimal-constrained deordering, but it
is impossible to guarantee that it will succeed for all plans.
Similarly, the authors mention that one may consider different ways of
constructing the validation structure.
This would clearly also modify the behaviour and it remains an open question
whether it is possible to generate, in polynomial time, a validation structure
that guarantees that a minimal-constrained deordering is constructed in the
second phase of the algorithm.
Finding a validation structure that  guarantees a minimum-constrained deordering
is obviously an NP-hard problem since the second phase of the algorithm is
polynomial.

\end{sloppypar}

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \input{KK-fail.latex}
    \caption{Failure example for the KK algorithm}
    \label{fig:KK-fail}
  \end{center}
\end{figure}


\subsection{Planners with Optimality Guarantees}

The planning algorithm \textsc{Graphplan}~\cite{Blum:Furst:ai97} 
has a notion of time steps and tries to pack as many non-interacting actions 
as possible into one single time step.
Furthermore, \textsc{Graphplan} finds the shortest plan, using the number of time
steps as the measure.
If assuming unit time and that all actions considered as non-interacting by
\textsc{Graphplan} can be executed in parallel, then there is no plan
having a shorter parallel execution than the plan produced by \textsc{Graphplan}.
That is, \textsc{Graphplan} produces minimum reordered parallel plans under
these assumptions.
The second assumption is no limitation in practice, since each non-concurrency
relation can be encoded by introducing a new atom and letting one of the interacting
actions add it while the other one deletes it.
The unit time assumption is more serious, however, especially since this
assumption is likely not to hold in most applications.
In the car-assembly scenario in Section~\ref{sec:example}, for instance, 
\textsc{Graphplan} would produce a plan that corresponds to the plan in
Figure~\ref{fig:reordered-ass-plan}.
Hence, the plan produced under the unit-time assumption happens to coincide with
the optimal plan when taking actual execution times into account.
This is just a fortunate coincidence, however, depending on the particular
durations of actions in this example.
Suppose instead that the durations of the actions are slightly different
such that PAC has duration 2 and MvT1 has duration 8.
Then the plan produced by \textsc{Graphplan}, which corresponds to the plan
in Figure~\ref{fig:reordered-ass-plan}, does not have a faster schedule than
19 time units.
This is not optimal since the plan in Figure~\ref{fig:deordered-ass-plan}
can be scheduled to execute in 17 time units for these particular duration times.
Furthermore, it must be remembered that \textsc{Graphplan} is anyway restricted
to those cases where a GT-equivalent planning language is sufficient,
although recent improvements extend it to somewhat more expressive languages
\cite{Gazen:Knoblock:ecp97,Koehler:etal:ecp97}.

Knoblock~\citeyear{Knoblock:aips94} has modified the UCPOP planner with a 
resource concept
which makes it avoid unordered interacting actions.
This means that the resulting planner produces definite parallel plans.
Knoblock further modified the evaluation heuristic of the search to take
parallel execution time into account.
It thus seems as if this planner might be able to produce minimum reordered
parallel plans, but the paper does not provide sufficient details to 
determine whether this is the case.
It is also unclear whether the heuristic can handle actions with different
duration times.

Yet another example is the polynomial-time planner for the SAS$^+$-IAO planning
language~\cite{Jonsson:Backstrom:ai98a} which
produces plans which are minimum-constrained reordered.
That is,  for this restricted formalism it is  clearly possible to optimise
the ordering in polynomial time.


\section{Discussion}\label{sec:discussion}

The previous section listed a few planning algorithms from the literature
that produce or attempt to produce plans which are least constrained or
minimum parallel reordered.
They do so only under certain restrictions, though.
Furthermore, plans are not always generated `from scratch', but can also be
generated by modifying some already existing plan, referred to as case-based
planning, or by repairing a plan that has failed during the execution phase.
In such cases, the old plan may contain many ordering relations that will be
obsolete in the modified/repaired plan. In fact, the KK algorithm
\cite{Kambhampati:Kedar:ai94} is motivated in the context of case-based planning.
It is also important to remember that today, and probably for a long time into
the future, very few plans are generated entirely by computer programs.
The vast majority of plans in various applications are designed by humans,
possibly with computer support.
Already for quite small plans, it is very difficult for a human to see whether
the ordering constraints are optimal or not, so computer support for such
analyses is vital for designing optimal plans.
For the same reason, also  hierarchical-task-network planners, \eg\  
\textsc{O-Plan}~\cite{Currie:Tate:ai91} and \textsc{Sipe}~\cite{Wilkins:PP},
produce plans where reordering actions could lead to better schedules.
Such a planner often commits to one of the two possible orderings for a pair
of actions based on expert-knowledge rules.
However, it is hardly possible for a human expert to design rules that in all
situations will guarantee that the optimal ordering choice is made.

On the coarseness level of complexity analysis it does not matter whether the 
tasks of planning, plan optimization and scheduling are integrated or separated 
since  the total resulting complexity will be the same in both cases---the latter
two computations are at most NP-complete and will, thus, be dominated by the
planning, which is PSPACE-complete or worse.
However, for good reasons this has not prevented the research community from
studying planning and scheduling as separate problems, since understanding each
problem in isolation also helps understanding the overall process.
For the same reason, it is important to also study separately the problems
discussed and analysed in this \paper.
Furthermore, on a more fine-grained, practical level there might be considerable 
differences in efficiency between integrating the three computations and
doing them separately.
For instance, even if all three computations take exponential time, each of
the problems considered in isolation may have fewer parameters, in which case
it may be much more efficient to solve them in isolation.
On the other hand, solving the whole problem at once may make it easier to
do global optimisation.
Which is the better will depend both on which methods are used and on various
properties of the actual application, and it seems unlikely that one of 
the methods should always be the better.

As has been shown in this \paper, minimum reordering is a much better
optimality criterion than minimum deordering, if only considering the
overall parallel execution time.
However, this is not necessarily true if also considering further metric 
constraints for subsequent scheduling.
Deordering a plan can only add to the number of feasible schedules, while
reordering may also remove some or, in the worst case, all feasible schedules.
On the other hand, reordering may also lead to new and better schedules not
reachable via deordering.
Deordering can thus be viewed as a safe and, sometimes, cheap way
to allow for better schedules, while reordering is an expensive method which
has a potential for generating considerably better plans, but which may also
make things worse. 
If using reordering in practice in cases where also metric scheduling constraints
are involved, it seems necessary to use feedback from the scheduler to control
the reordering process, or to try other reorderings.
One could imagine a reordering algorithm which uses either heuristic search
or randomized local-search methods {\`a} la GSAT \cite{Selman:etal:aaai92}
to find reorderings and then use the scheduler as evaluation function for
the proposed reorderings.

While the plan modifications studied in this \paper\ may add considerably to
the optimizations that are possible with traditional scheduling only, there
is still a further potential of optimization left to study---modifying not only the
action order, but also the set of actions.
Such modification is already done in plan adaptation, but then only for generating
a new plan from old cases, and optimizations in the sense of this \paper\ are
not considered.
Some preliminary studies of action-set modifications appear in the literature,
though.
Fink and Yang~\citeyear{Fink:Yang:cscsi92} study the problem of
removing redundant actions from total-order plans, defining a spectrum of
redundancy criteria and analysing the complexity of achieving these.
It is less clear that it is interesting to study action addition; adding actions 
to a plan could obviously not improve the execution time of it if it is to
be executed sequentially.
However, in the case of parallel execution of plans it has been shown that 
adding actions  to a plan can sometimes allow for faster 
execution~\cite{Backstrom:ecai94}.
Finally, if allowing both removal and addition of actions, an even greater 
potential for optimising plans seems available, but this problems seems not
yet studied in the literature.

\section{Conclusions}\label{sec:conclusions}

This \paper\ studies the problem of modifying the action ordering of a plan in 
order to optimise the plan according to various criteria.
One of these criteria is to make a plan less constrained and the other is
to minimize its parallel execution time.
Three candidate definitions are proposed for the first of these criteria,
constituting a spectrum of increasing optimality guarantees.
Two of these are based on deordering plans, which means that ordering relations
may only be removed, not added, while the last one builds on reordering, where
arbitrary modifications to the ordering are allowed.
The first of the three candidates, subset-minimal deordering, is tractable
to achieve, while the other two, deordering or reordering a plan to minimize
the size of the ordering, are both NP-hard and even difficult to approximate.

Similarly, optimising the parallel execution time of a plan is studied both
for deordering and reordering of plans.
In the general case, both of these computations are NP-hard and difficult to
approximate.
However, based on an algorithm from the literature it is shown that optimal 
deorderings can be computed in polynomial time for definite plans for a class
of planning  languages based on the notions of producers, consumers and threats, 
which includes most of the commonly used planning languages.
Computing optimal reorderings can potentially lead to even faster parallel
executions, but this problem remains NP-hard and difficult to approximate
even under quite severe restrictions.
Furthermore, deordering a plan is safe with respect to subsequent scheduling,
while reordering a plan may remove feasible schedules, making deordering
a good, but often suboptimal, approach in practice.


\subsection*{Acknowledgements}
Tom Bylander, Thomas Drakengren, Mark Drummond, Alexander Horz, Peter Jonsson, 
Bernhard Nebel, Erik Sandewall, Sylvie Thibeaux and
the anonymous referees provided helpful comments on this article and previous
versions of it.
The research was supported by the Swedish Research Council for
Engineering Sciences (TFR) under grants Dnr. 92-143 and 95-731.


\section*{Appendix A}

\textbf{Theorem~\ref{th:MmPD-restr-NPhard}}
  \emph{\textsc{Minimum Parallel Reordering\/} remains NP-hard even when 
  restricted to total-order GT plans with only toggling unary actions and under
  the assumption of unit time, simple concurrency and that no actions are 
redundant.}

\mbox{}

\begin{proof}
  Proof by reduction from 3SAT~\cite[p.~259]{Garey:Johnson:CI}.
  Let $\atomset=\set{\atom_1,\ldots,\atom_n}$ be a set of atoms and
  $\clauseset=\set{C_1,\ldots,C_m}$ a set of clauses over $\atomset$ s.t.
  for $1\leq i\leq m$, $C_i=\set{\lit_{i,1},\lit_{i,2},\lit_{i,3}}$ is
  a set of three literals over $\atomset$.

  First define the set of atoms
  \[ \atomsetb = \set{p^F_i, p^T_i, q_i \st 1\leq i\leq n} \union
                 \set{c_{i,j}, r_{i,j} \st 1\leq i\leq n, 1\leq j\leq 3}. \]
  Then define a GT \textsc{ppi\/} $\ppi=\tuple{\init,\goal}$ with initial and 
  goal states  defined as  
  \begin{eqnarray*}
    \init & = & \Neg(\atomsetb)\\
    \goal & = & \set{p^F_i, p^T_i, \lnot q_i \st 1\leq i\leq n} \union
                 \set{c_{i,j}, \lnot r_{i,j} \st 1\leq i\leq n, 1\leq j\leq 3}
  \end{eqnarray*}
  Also, for each atom $\atom_i\in\atomset$, define four actions
  according to Table~\ref{tab:atom-actions}.

  \begin{table}[hb]
    \begin{center}
      \leavevmode
        \[
  \begin{array}[bt]{|l|l|l|}
    \hline
    \text{operator} & \text{precond.} & \text{postcond.} \\
    \hline
    A^F_i & \lnot p^F_i, \lnot q_i & p^F_i \\
    A^T_i & \lnot p^T_i, q_i & p^T_i \\
    A^+_i & \lnot q_i & q_i \\
    A^-_i & q_i & \lnot q_i \\
    \hline
  \end{array}
  \]
      \caption{Generic actions for each atom $p_i$ in the proof of 
        Theorem~\ref{th:MmPD-restr-NPhard}. }
      \label{tab:atom-actions}
    \end{center}
  \end{table}

  \noindent
  Further, for each clause $C_i\in C$, define nine actions
  according to Table~\ref{tab:clause-actions}
  where 
  \[ \lit^*_{i,j} = \left\{
    \begin{array}[c]{ll}
      p^F_k & \tif \lit_{i,j} = \lnot \atom_k\\
      p^T_k & \tif \lit_{i,j} = \atom_k.
    \end{array}
  \right. \]

  \begin{table}[ht]
    \begin{center}
      \leavevmode
        \[ 
  \begin{array}[tb]{|l|l|l|}
    \hline
    \text{operator} & \text{precond.} & \text{postcond.} \\
    \hline
    B^+_{i,1} & \lit^*_{i,1}, r_{i,1}, \lnot r_{i,2}, \lnot r_{1,3}, 
      \lnot c_{i,1} & c_{i,1} \\
    B^+_{i,2} & \lit^*_{i,2}, \lnot r_{i,1}, r_{i,2}, \lnot r_{1,3}, 
      \lnot c_{i,2} & c_{i,2} \\
    B^+_{i,3} & \lit^*_{i,3}, \lnot r_{i,1}, \lnot r_{i,2}, r_{1,3}, 
    \lnot c_{i,3} & c_{i,3}\\
    C^+_{i,1} & \lnot r_{i,1} & r_{i,1} \\
    C^-_{i,1} &  r_{i,1} & \lnot r_{i,1} \\
    C^+_{i,2} & \lnot r_{i,2} & r_{i,2} \\
    C^-_{i,2} &  r_{i,2} & \lnot r_{i,2} \\
    C^+_{i,3} & \lnot r_{i,3} & r_{i,3} \\
    C^-_{i,3} &  r_{i,3} & \lnot r_{i,3} \\
    \hline
  \end{array}
  \]
      \caption{Generic atoms for each clause $C_i$ in the proof of
        Theorem~\ref{th:MmPD-restr-NPhard}. }
      \label{tab:clause-actions}
    \end{center}
  \end{table}
%
  \noindent
  Let $\actset$ be the set of all $4n + 9m$ actions thus defined.
  Clearly there is some total order $\prec$ s.t. the plan 
  $\plan=\tuple{\actset,\prec}$   is $\ppi$-valid.
  It is also obvious that none of the actions is redundant.

  It is a trivial observation that
  any parallel execution $\release$ of any $\ppi$-valid reordering of
  $\plan$ must satisfy that for each $i$, $1\leq i\leq n$, either
  \[ \release(A^F_i) < \release(A^+_i) < \release(A^T_i) < \release(A^-_i) \]
  or
  \[ \release(A^+_i) < \release(A^T_i) < \release(A^-_i) <\release(A^F_i), \]
  and for each $i$, $1\leq i\leq m$, 
  \[ \release(C^+_{i,k_1}) < \release(B^+_{i,k_1}) < 
     \left\{\!\begin{array}[c]{l}
         \release(C^-_{i,k_1})\\ \release(C^+_{i,k_2}) 
       \end{array}\!\right\}
     < \release(B^+_{i,k_2}) < 
     \left\{\!\begin{array}[c]{l}
         \release(C^-_{i,k_2})\\ \release(C^+_{i,k_3}) 
       \end{array}\!\right\}
     < \release(B^+_{i,k_3}) < \release(C^-_{i,k_3}), \]
  where $k_1,k_2,k_3$ is a permutation of the numbers $1,2,3$.
  (This is to be interpreted s.t. the actions $C^-_{i,k_1}$ and $C^+_{i,k_2}$
  can be released in either order, or simultaneously, and analogously for the
  actions $C^-_{i,k_2}$ and $C^+_{i,k_3}$).


  The remainder of this proof shall show that $\plan$ can be reordered to
  have a parallel execution of length 8 iff the set $\clauseset$
  of clauses is satisfiable.

\emph{if:\/}
  Suppose $C$ is satisfiable.
  Let $\intrp$ be a truth assignment for the atoms in $\atomset$  that
  satisfies $\clauseset$.
  Wlg. assume $\intrp(p_i)=T$ for all $i$.
  Further, for each clause $C_j$, let $\lit_j$ be any literal in $C_j$ which
  is satisfied by $\intrp$.
  Disregarding  the action order for a moment, choose a release-time function 
  $r$ for   the actions as follows.
  For $1\leq i\leq n$, let
    \[ \release(A^+_i) = 0,\ 
       \release(A^T_i) = 1,\  
       \release(A^-_i) = 2,\  
       \release(A^F_i) = 3. \]
  Further, for each $j$,  $1\leq j\leq m$, choose $k_1$ s.t.   
  $\lit_{j,k_1}\in C_j$  is satisfied by $\intrp$ (at least one such choice
  must exist by the assumption).
  Let  $\lit_{j,k_2}$ and $\lit_{j,k_3}$ be the remaining two literals
  in $C_j$. 
  Assign release times s.t. for $1\leq h\leq 3$,
  \[ \release(C^+_{j,k_h})=2h-1,\ 
     \release(B^+_{j,k_h})=2h\ ,
     \release(C^-_{j,k_h})=2h+1. \]
  Now define the partial order $\precb$ on $\actset$ s.t.
  for all actions $\act,\actb\in\actset$,
  $\act\precb\actb$ iff $\release(\act)<\release(\actb)$.
  Clearly, the plan $\tuple{\actset,\precb}$ is a $\ppi$-valid
  reordering of $\plan$ and $\release$ is a parallel execution of length 8 
  for $\tuple{\actset,\precb}$.
  (Note that no other choice of $\intrp$ could force a longer execution,
   while there is an execution of length 7 in the case where $\clauseset$ is
   satisfied by setting all atoms false.)

\emph{only if:\/}
  Suppose $\clauseset$ is not satisfiable.
  Further suppose that $\planb$ is a minimum reordering of $\plan$ and that
  $\release$ is a parallel execution of length 8 or shorter for $\planb$.
  Wlg.  assume that every action is released as early as possible by $\release$.
  Then,  according to the observation above it must hold  for each $i$, 
  $1\leq i\leq n$, that either
    \[ \release(A^F_i) = 0,\   
       \release(A^+_i) = 1,\    
       \release(A^T_i) = 2,\    
       \release(A^-_i) = 3 \]
       or
    \[ \release(A^+_i) = 0,\   
       \release(A^T_i) = 1,\    
       \release(A^-_i) = 2,\    
       \release(A^F_i) = 3. \]
   Hence, exactly  one of the atoms $p^F_i$ and $p^T_i$ is true at time 2.
   Let $p^*_i$ denote this atom.
   Since $\release$ is of length 8, it follows from the earlier observation that
   for all $j$, $1\leq j\leq m$, $\release(B^+_{j,k})\leq 2$ for some $k$, 
   $1\leq k\leq 3$.
   Hence, $\lit_{j,k}=p^*_i$ for some $i$, since $\planb$ is $\ppi$-valid and
   $\release$ is a parallel execution for $\planb$.
   Define an interpretation $\intrp$ s.t. for all $i$, $1\leq i\leq n$,
   \[ \intrp(p_i) = \left\{
          \begin{array}[c]{ll}
            F, & \tif p^*_i = p^F_i \\
            T, & \totherwise.
          \end{array} \right. \]
  However, this interpretation is obviously a model for $\clauseset$, 
  which contradicts the assumption.
  It follows that $\release$ must be of length 9 or longer.   

  This concludes the proof and shows that $\clauseset$ is satisfiable iff
  $\plan$ has a reordering with a parallel execution of length 8 or not.
\end{proof}

\textbf{Theorem ~\ref{th:RF-no-perf-guarantee}}
\emph{
\textsc{Minimum Parallel Deordering\/} cannot approximate 
\textsc{Minimum Parallel Reordering\/} within $\card{A}^k$
for any constant $k\geq 0$.}

\mbox{}

\begin{proof}
The proof assumes GT plans and simple concurrency.
First, define the generic actions $a^k_i(m)$, $b^k_i$ and $c^k_i(m)$ according to
Table~\ref{tab:MmPD-approx-MmPR-actions}.
%
\begin{table}[hb]
\label{tab:MmPD-approx-MmPR-actions}
\[
  \begin{array}[c]{|l|l|l|}
    \hline
    \text{action} & \text{pre-condition} & \text{post-condition} \\
    \hline
    a^k_i(m) & \set{p^k_i} & 
      \set{p^{k-1}_{(i-1)m+1},\ldots,p^{k-1}_{im},\lnot q^{k-1}_{(i-1)m}} \\
    b^{k}_i & \set{p^{k}_i} & \set{q^{k}_i} \\
    c^k_i(m) & \set{q^{k-1}_{(i-1)m+1},\ldots,q^{k-1}_{im}} &
      \post(c^k_i(m)) = \set{q^k_i}.\\
    \hline
  \end{array}
\]
\caption{Generic actions for the proof of Theorem~\ref{th:RF-no-perf-guarantee}.}
\end{table}
%
Further, define recursively the generic plans
\[ \plan^k_i(m) = \left\{
     \begin{array}[c]{ll}
\seq{a^1_{(i-1)m+1}(1),b^0_{(i-1)m+1},c^1_{(i-1)m+1}(1),\ldots,
     a^1_{im}(1),b^0_{im},c^1_{im}(1)}, 
  & \text{for\ } k=1 \\
\seq{a^k_{(i-1)m+1}(m);\plan^{k-1}_{(i-1)m+1}(m);c^k_1(m),\ldots,
     a^k_{im}(m);\plan^{k-1}_{im}(m);c^k_{im}(m)},
  & \text{for\ } k>1.
     \end{array}\right. \]
Furthermore, for arbitrary $k,n>0$ define the \textsc{ppi\/} $\ppi^k_n =
\tuple{\set{p^k_1,\ldots,p^k_n},\set{q^k_1,\ldots,q^k_n}}$.

Now, prove the claim that for arbitrary $k,n>0$, the plan $\plan^k_1(n)$
  \begin{enumerate}
  \item is $\ppi^k_n$-valid,
  \item has no deordering of length less than $3n^k+\sum_{i=1}^{k-1}2n^i$ and
  \item has a reordering of length $2k+1$.
  \end{enumerate}
\noindent
Proof by induction over $k$.

\emph{Base case (k=1):}
Choose an arbitrary  $n>0$.
The plan $\plan^1_1(n)$ is obviously $\ppi^k_n$-valid and has no deordering
other than itself, which is of length $3n$.
Consider the reordering $\planb^1_1(n)$ of $\plan^1_1(n)$ with the same actions and
with ordering relation $\prec$ defined s.t.  for all $i$, $1\leq i\leq n$, 
$a^1_i(1) \prec b^0_i \prec c^1_i(1)$ and for all $i$, $1< i\leq n$, 
$a^1_i(1) \prec b^0_{i-1}$.
This reordering is $\ppi^k(n)$-valid and has a parallel execution 
$\release^1_1(n)$ of length 3, defined s.t. for all $i$, $1\leq i\leq n$, 
$\release^1_1(n)(a^1_i(1)) = 1$, $\release^1_1(n)(b^0_i) = 2$ and 
$\release^1_1(n)(c^1_i(1)) = 3$.
(This plan is shown in Figure~\ref{fig:RF-no-perf-guarantee}.)
The claim is thus satisfied for the base case.


\begin{figure}[ht]
\begin{center}
\input{approx.latex}
%
\caption{The reordering $\planb^2_1(n)$ of the plan $\plan^2_1(n)$ as an example of
the induction case in the proof of Theorem~\ref{th:RF-no-perf-guarantee}
(solid arrows denote orderings required by producer-consumer relationships and are
labelled with the atom produced/consumed,
while dashed arrows denote ordering constraints to avoid threats and are labelled with
the possibly conflicting atom). }
\label{fig:RF-no-perf-guarantee}
\end{center}
\end{figure}

\emph{Induction:}
Suppose the claim is satisfied for all $l < k$, for some $k\geq 1$ and prove
that the claim holds also for $l = k$.
Choose an arbitrary  $n>0$.
It follows from the induction hypothesis that none of the subplans
$\plan^{k-1}_1(n)\ldots,\plan^{k-1}_n(n)$ can be deordered, so they have to
remain totally ordered.
Furthermore, for all $i$, $1\leq i\leq n$, it is necessary that the action
$a^{k}_i(n)$ is ordered before the subplan $\plan^{k-1}_i(n)$ and that
the action $c^k_i(n)$ is ordered after it.
It is also clear that for no $i$, $1\leq i\leq n$ can the order
$c^k_i(n)\prec a^{k}_{i+1}(n)$ be removed without making the plan invalid.
Hence, $\plan^k_1(n)$ has no other deordering than itself, which is of length 
\begin{eqnarray*}
 \lefteqn{\sum_{i=1}^{n}(2 + \length(\plan^{k-1}_i(n)) = 
   n(2 + \length(\plan^{k-1}_1(n))) } \\
 & = &  2n + n(3n^{k-1} + \sum_{i=1}^{k-2}2n^i) = 3n^{k} + \sum_{i=1}^{k-1}2n^i, 
\end{eqnarray*}

which proves the deordering case of the claim.

For the reordering case, define a reordering $\planb^{k}_1(n)$ of 
$\plan^{k}_1(n)$ with 
the same actions and with ordering relation defined as follows.
For each subplan $\plan^{k-1}_i(n)$ of $\plan^{k}_1(n)$, reorder its actions
so it has length $2(k-1)+1$, which is possible according to 
the induction hypothesis.
Further, for each $i$, $1\leq i\leq n$, and each $j$, $(i-1)n+1 \leq j\leq in$
order $a^{k}_{i}(n) \prec a^{k-1}_j(n)$ and $c^{k-1}_j(n)\prec c^k_i(n)$
(or $a^{k}_{i+1}(n) \prec a^{k-1}_j(1)$ and $c^{k-1}_j(1)\prec c^k_i(n)$
for the case $k=2$).
Hence, each segment of the type $a^k_i(n);\plan^{k-1}_i(n);c^k_i(n)$ is
reordered to have length $2k+1$.
Finally, for each $i$, $1\leq i\leq n$, order 
$a^{k}_{i}(n) \prec a^{k-1}_{(i-1)n}(n)$
(or $a^{k}_{i}(n) \prec a^{k-1}_{(i-1)n}(1)$ for the case $k=2$).
The plan $\planb^{k}_1(n)$ is  $\ppi^k(n)$-valid since the  subplans 
$\plan^{k-1}_1(n),\ldots,\plan^{k-1}_n(n)$ do not have any atoms in common and,
thus, the $\nonpar$ relation does not hold between any two actions belonging
to different such subplans.
This  reordered plan  can be executed under the parallel execution 
$\release^k_i(n)$ defined s.t.
$\release^k_i(n)(a^{k}_{i}(n)) = 1$,
$\release^k_i(n)(c^{k}_{i}(n)) = 2k+1$ and for all $i$, $1\leq i\leq n$ and all
actions $a'\in\planb^{k-1}_i(n)$,
$\release^k_i(n)(a')=\release^{k-1}_i(n)(a')+1$.
Since this is a parallel execution of length $2k+1$ for the reordered plan,
the claim holds also for $k$.

This concludes the induction, so the claim holds for all $k>0$.
Since 
\[ \frac{3n^k+\sum_{i=1}^{k-1}2n^i}{2k+1} \geq 
   \frac{1}{(2k+1)3^{k-1}}\card{\actset}^k \]
for all $k>0$, the theorem holds.
\end{proof}

%\bibliography{strings,abstracts,papers,xref,books}

\begin{thebibliography}{}

\bibitem[\protect\BCAY{B{\"a}ckstr{\"o}m}{B{\"a}ckstr{\"o}m}{1993}]{Backstrom:%
ewsp93}
B{\"a}ckstr{\"o}m, C. \BBOP1993\BBCP.
\newblock \BBOQ Finding least constrained plans and optimal parallel executions
  is harder than we thought\BBCQ\
\newblock In B{\"a}ckstr{\"o}m, C.\BBACOMMA\  \BBA\ Sandewall, E.\BEDS, {\Bem
  Current Trends in {AI} Planning: EWSP'93---2nd European Workshop on
  Planning}, \BPGS\ 46--59\ Vadstena, Sweden. IOS Press.

\bibitem[\protect\BCAY{B{\"a}ckstr{\"o}m}{B{\"a}ckstr{\"o}m}{1994}]{Backstrom:%
ecai94}
B{\"a}ckstr{\"o}m, C. \BBOP1994\BBCP.
\newblock \BBOQ Executing parallel plans faster by adding actions\BBCQ\
\newblock In Cohn, A.~G.\BED, {\Bem Proceedings of the 11th European Conference
  on Artificial Intelligence (ECAI'94)}, \BPGS\ 615--619\ Amsterdam,
  Netherlands. Wiley.

\bibitem[\protect\BCAY{B{\"a}ckstr{\"o}m}{B{\"a}ckstr{\"o}m}{1995}]{Backstrom:%
ai95}
B{\"a}ckstr{\"o}m, C. \BBOP1995\BBCP.
\newblock \BBOQ Expressive equivalence of planning formalisms\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 76\/}(1--2), 17--34.

\bibitem[\protect\BCAY{B{\"a}ckstr{\"o}m \BBA\ Klein}{B{\"a}ckstr{\"o}m \BBA\
  Klein}{1991}]{Backstrom:Klein:ijcai91}
B{\"a}ckstr{\"o}m, C.\BBACOMMA\  \BBA\ Klein, I. \BBOP1991\BBCP.
\newblock \BBOQ Parallel non-binary planning in polynomial time\BBCQ\
\newblock In Reiter, R.\BBACOMMA\  \BBA\ Mylopoulos, J.\BEDS, {\Bem Proceedings
  of the 12th International Joint Conference on Artificial Intelligence
  (IJCAI'91)}, \BPGS\ 268--273\ Sydney, Australia. Morgan Kaufmann.

\bibitem[\protect\BCAY{Bellare, Goldreich, \BBA\ Sudan}{Bellare
  et~al.}{1995}]{Bellare:etal:focs95}
Bellare, M., Goldreich, O., \BBA\ Sudan, M. \BBOP1995\BBCP.
\newblock \BBOQ Free bits, {PCPs} and non-approximability---towards tighter
  results\BBCQ\
\newblock In {\Bem Proceedings of the 36th Annual {IEEE} Symposium on the
  Foundations of Computer Science (FOCS'95)}, \BPGS\ 422--431\ Milwaukee, WI, USA.
  IEEE Computer Society.

\bibitem[\protect\BCAY{Blum \BBA\ Furst}{Blum \BBA\
  Furst}{1997}]{Blum:Furst:ai97}
Blum, A.~L.\BBACOMMA\  \BBA\ Furst, M.~L. \BBOP1997\BBCP.
\newblock \BBOQ Fast planning through planning graph analysis\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 90\/}(1--2), 281--300.

\bibitem[\protect\BCAY{Chapman}{Chapman}{1987}]{Chapman:ai87}
Chapman, D. \BBOP1987\BBCP.
\newblock \BBOQ Planning for conjunctive goals\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 32\/}(3), 333--377.

\bibitem[\protect\BCAY{Crescenzi \BBA\ Panconesi}{Crescenzi \BBA\
  Panconesi}{1991}]{Crescenzi:Panconesi:ic91}
Crescenzi, P.\BBACOMMA\  \BBA\ Panconesi, A. \BBOP1991\BBCP.
\newblock \BBOQ Completeness in approximation classes\BBCQ\
\newblock {\Bem Information and Computation}, {\Bem 93\/}(2), 241--262.

\bibitem[\protect\BCAY{Currie \BBA\ Tate}{Currie \BBA\
  Tate}{1991}]{Currie:Tate:ai91}
Currie, K.\BBACOMMA\  \BBA\ Tate, A. \BBOP1991\BBCP.
\newblock \BBOQ {O-Plan}: {T}he open planning architecture\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 52\/}(1), 49--86.

\bibitem[\protect\BCAY{Feige \BBA\ Kilian}{Feige \BBA\
  Kilian}{1996}]{Feige:Kilian:ccc96}
Feige, U.\BBACOMMA\  \BBA\ Kilian, J. \BBOP1996\BBCP.
\newblock \BBOQ Zero knowledge and the chromatic number\BBCQ\
\newblock In {\Bem 11th Annual {IEEE} Conference on Computational Compelxity
  {(CCC'96)}}\ Philadelphia, PA, USA. IEEE Computer Society.

\bibitem[\protect\BCAY{Feige}{Feige}{1996}]{Feige:stoc96}
Feige, U. \BBOP1996\BBCP.
\newblock \BBOQ A threshold of {$\ln n$} for approximating set cover
  (preliminary version)\BBCQ\
\newblock In {\Bem Proceedings of 28th Annual ACM Symposium on Theory of Computing
  (STOC'96)},
  \BPGS\ 314--318\ Philadelphia, PA, USA. ACM.

\bibitem[\protect\BCAY{Fink \BBA\ Yang}{Fink \BBA\
  Yang}{1992}]{Fink:Yang:cscsi92}
Fink, E.\BBACOMMA\  \BBA\ Yang, Q. \BBOP1992\BBCP.
\newblock \BBOQ Formalizing plan justifications\BBCQ\
\newblock In {\Bem Proceedings of the 9th Conference of the Canadian Society
  for Computational Studies of Intelligence (CSCSI'92)}, \BPGS\ 9--14\
  Vancouver, BC, Canada.

\bibitem[\protect\BCAY{Garey \BBA\ Johnson}{Garey \BBA\
  Johnson}{1979}]{Garey:Johnson:CI}
Garey, M.\BBACOMMA\  \BBA\ Johnson, D. \BBOP1979\BBCP.
\newblock {\Bem Computers and Intractability: {A} Guide to the Theory of
  {NP}-Completeness}.
\newblock Freeman, New York.

\bibitem[\protect\BCAY{Gazen \BBA\ Knoblock}{Gazen \BBA\
  Knoblock}{1997}]{Gazen:Knoblock:ecp97}
Gazen, C.\BBACOMMA\  \BBA\ Knoblock, C. \BBOP1997\BBCP.
\newblock \BBOQ Combining the expressivity of {UCPOP} with the efficiency of
  Graphplan\BBCQ\ 
\newblock In Steel\BBACOMMA\ \BBA\ Alami \citeyear{ecp97}, \BPGS\ 221--233.

\bibitem[\protect\BCAY{Ghallab \BBA\ Laruelle}{Ghallab \BBA\
  Laruelle}{1994}]{Ghallab:Laruelle:aips94}
Ghallab, M.\BBACOMMA\  \BBA\ Laruelle, H. \BBOP1994\BBCP.
\newblock \BBOQ Representation and control in {IxTeT}, a temporal planner\BBCQ\ 
\newblock In Hammond \citeyear{aips94}, \BPGS\ 61--67.

\bibitem[\protect\BCAY{Hammond}{Hammond}{1994}]{aips94}
Hammond, K.\BED. \BBOP1994\BBCP.
\newblock {\Bem Proceedings of the 2nd International Conference on
  Artificial Intelligence Planning Systems (AIPS'94)}, Chicago, IL, USA. AAAI
  Press.

\bibitem[\protect\BCAY{Jonsson \BBA\ B{\"a}ckstr{\"o}m}{Jonsson \BBA\
  B{\"a}ckstr{\"o}m}{1998}]{Jonsson:Backstrom:ai98a}
Jonsson, P.\BBACOMMA\  \BBA\ B{\"a}ckstr{\"o}m, C. \BBOP1998\BBCP.
\newblock \BBOQ State-variable planning under structural restrictions:
  Algorithms and complexity\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 100\/}(1--2), 125--176.

\bibitem[\protect\BCAY{Kambhampati}{Kambhampati}{1994}]{Kambhampati:ai94}
Kambhampati, S. \BBOP1994\BBCP.
\newblock \BBOQ Multi-contributor causal structures for planning: A
  formalization and evaluation\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 69\/}(1--2), 235--278.

\bibitem[\protect\BCAY{Kambhampati \BBA\ Kedar}{Kambhampati \BBA\
  Kedar}{1994}]{Kambhampati:Kedar:ai94}
Kambhampati, S.\BBACOMMA\  \BBA\ Kedar, S. \BBOP1994\BBCP.
\newblock \BBOQ A unified framework for explanation-based generalization of
  partially ordered and partially instantiated plans\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 67\/}(1), 29--70.

\bibitem[\protect\BCAY{Klein, Jonsson, \BBA\ B{\"a}ckstr{\"o}m}{Klein
  et~al.}{1995}]{Klein:etal:ewsp95}
Klein, I., Jonsson, P., \BBA\ B{\"a}ckstr{\"o}m, C. \BBOP1995\BBCP.
\newblock \BBOQ Tractable planning for an assembly line\BBCQ\
\newblock In Ghallab, M.\BBACOMMA\  \BBA\ Milani, A.\BEDS, {\Bem New Directions
  in {AI} Planning: EWSP'95---3rd European Workshop on Planning}, Frontiers in
  {AI} and Applications, \BPGS\ 313--324\ Assisi, Italy. IOS Press.

\bibitem[\protect\BCAY{Klein, Jonsson, \BBA\ B{\"a}ckstr{\"o}m}{Klein
  et~al.}{1998}]{Klein:etal:aieng98}
Klein, I., Jonsson, P., \BBA\ B{\"a}ckstr{\"o}m, C. \BBOP1998\BBCP.
\newblock \BBOQ Efficient planning for a miniature assembly line\BBCQ\
\newblock {\Bem Artificial Intelligence in Engineering},  {\Bem 13\/}(1), 69--81.

\bibitem[\protect\BCAY{Knoblock}{Knoblock}{1994}]{Knoblock:aips94}
Knoblock, C. \BBOP1994\BBCP.
\newblock \BBOQ Generating parallel execution plans with a partial-order
  planner\BBCQ\ 
\newblock In Hammond \citeyear{aips94}.

\bibitem[\protect\BCAY{K{\"o}hler, Nebel, Hoffman, \BBA\ Dimopoulos}{K{\"o}hler
  et~al.}{1997}]{Koehler:etal:ecp97}
K{\"o}hler, J., Nebel, B., Hoffman, J., \BBA\ Dimopoulos, Y. \BBOP1997\BBCP.
\newblock \BBOQ Extending planning graphs to an {ADL} subset\BBCQ\ 
\newblock In Steel\BBACOMMA\ \BBA\ Alami \citeyear{ecp97}, \BPGS\ 273--285.

\bibitem[\protect\BCAY{Lund \BBA\ Yannakakis}{Lund \BBA\
  Yannakakis}{1994}]{Lund:Yannakakis:jacm94}
Lund, C.\BBACOMMA\  \BBA\ Yannakakis, M. \BBOP1994\BBCP.
\newblock \BBOQ On the hardness of approximating minimization problems\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 41\/}(5), 960--981.

\bibitem[\protect\BCAY{Nebel \BBA\ B{\"a}ckstr{\"o}m}{Nebel \BBA\
  B{\"a}ckstr{\"o}m}{1994}]{Nebel:Backstrom:ai94}
Nebel, B.\BBACOMMA\  \BBA\ B{\"a}ckstr{\"o}m, C. \BBOP1994\BBCP.
\newblock \BBOQ On the computational complexity of temporal projection,
  planning and plan validation\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 66\/}(1), 125--160.

\bibitem[\protect\BCAY{Pednault}{Pednault}{1986}]{Pednault:rap86}
Pednault, E. P.~D. \BBOP1986\BBCP.
\newblock \BBOQ Formulating multiagent, dynamic-world problems in the classical
  planning framework\BBCQ\
\newblock In Georgeff, M.\BBACOMMA\  \BBA\ Lansky, A.~L.\BEDS, {\Bem Reasoning
  about Actions and Plans, Proceedings of the 1986 Workshop}, \BPGS\ 47--82\
  Timberline, OR, USA. Morgan Kaufmann.

\bibitem[\protect\BCAY{Regnier \BBA\ Fade}{Regnier \BBA\
  Fade}{1991a}]{Regnier:Fade:ewsp91}
Regnier, P.\BBACOMMA\  \BBA\ Fade, B. \BBOP1991a\BBCP.
\newblock \BBOQ Complete determination of parallel actions and temporal
  optimization in linear plans of action\BBCQ\
\newblock In Hertzberg, J.\BED, {\Bem European Workshop on Planning},
  \lowercase{\BVOL}\ 522 of {\Bem Lecture Notes in Artificial Intelligence},
  \BPGS\ 100--111\ Sankt Augustin, Germany. Springer.

\bibitem[\protect\BCAY{Regnier \BBA\ Fade}{Regnier \BBA\
  Fade}{1991b}]{Regnier:Fade:ria91}
Regnier, P.\BBACOMMA\  \BBA\ Fade, B. \BBOP1991b\BBCP.
\newblock \BBOQ D\'etermination du parall\'elisme maximal et optimisation
  temporelle dans les plans d'actions lin\'eaires\BBCQ\
\newblock {\Bem Revue d'intelligence artificielle}, {\Bem 5\/}(2), 67--88.

\bibitem[\protect\BCAY{Selman, Levesque, \BBA\ Mitchell}{Selman
  et~al.}{1992}]{Selman:etal:aaai92}
Selman, B., Levesque, H., \BBA\ Mitchell, D. \BBOP1992\BBCP.
\newblock \BBOQ A new method for solving hard satisfiability problems\BBCQ\
\newblock In {\Bem Proceedings of the 10th (US) National Conference on
  Artificial Intelligence (AAAI'92)}, \BPGS\ 440--446\ San Jos\'e, CA, USA.
  American Association for Artificial Intelligence.

\bibitem[\protect\BCAY{Steel \BBA\ Alami}{Steel \BBA\ Alami}{1997}]{ecp97}
Steel, S.\BBACOMMA\  \BBA\ Alami, R.\BEDS. \BBOP1997\BBCP.
\newblock {\Bem 4th European Conference on Planning, ECP'97},
  \lowercase{\BVOL}\ 1348 of {\Bem Lecture Notes in Artificial Intelligence},
  Toulouse, France. Springer.

\bibitem[\protect\BCAY{Str{\"o}mberg}{Str{\"o}mberg}{1991}]{Stromberg:SLB}
Str{\"o}mberg, J.-E. \BBOP1991\BBCP.
\newblock \BBOQ Styrning av {LEGO}-bilfabrik. {A}ndra omarbetade
  upplagan\BBCQ\
\newblock Department of Electrical Engineering, Link{\"o}ping University.

\bibitem[\protect\BCAY{Tate}{Tate}{1975}]{Tate:ijcai75}
Tate, A. \BBOP1975\BBCP.
\newblock \BBOQ Interacting goals and their use\BBCQ\
\newblock In {\Bem Proceedings of the 4th International Joint Conference on
  Artificial Intelligence (IJCAI'75)}, \BPGS\ 215--218\ Tbilisi, USSR. IJCAI,
  William Kaufmann.

\bibitem[\protect\BCAY{Veloso, P\'erez, \BBA\ Carbonell}{Veloso
  et~al.}{1990}]{Veloso:etal:iapsc90}
Veloso, M.~M., P\'erez, M.~A., \BBA\ Carbonell, J.~G. \BBOP1990\BBCP.
\newblock \BBOQ Nonlinear planning with parallel resource allocation\BBCQ\
\newblock In Sycara, K.~P.\BED, {\Bem Workshop on Innovative Approaches to
  Planning, Scheduling and Control}, \BPGS\ 207--212\ San Diego, CA, USA.
  Morgan Kaufmann.

\bibitem[\protect\BCAY{Vere}{Vere}{1983}]{Vere:pami83}
Vere, S.~A. \BBOP1983\BBCP.
\newblock \BBOQ Planning in time: Windows and durations for activities and
  goals\BBCQ\
\newblock {\Bem IEEE Transactions on Pattern Analysis and Machine
  Intelligence}, {\Bem PAMI-5\/}(3), 246--267.

\bibitem[\protect\BCAY{Wilkins}{Wilkins}{1988}]{Wilkins:PP}
Wilkins, D.~E. \BBOP1988\BBCP.
\newblock {\Bem Practical Planning}.
\newblock Morgan Kaufmann, San Mateo, CA.

\end{thebibliography}


\end{document}