%-*- Mode:TeX; Default-character-style: (:SWISS :ROMAN :NORMAL) -*-

\documentstyle[reduced]{aaai}
\newcommand{\mf}[2]{#1}
\setlength{\unitlength}{.86mm}
%\special{legal}
%\special{tray 3}
\begin{document}

\title{Dominance and Subsumption in Constraint-Posting Planning}
\author{Michael P. Wellman\footnotemark\\
MIT Laboratory for Computer Science\\
545 Technology Square\\
Cambridge, MA  02139}
%\title{}
%\author{\footnotemark}

\maketitle

\begin{abstract}

By integrating a dominance prover into the plan search process, the traditional
constraint-posting planning paradigm can be generalized to permit partially
satisfiable goals.  In this approach, the view of planning as theorem proving is
retained, although the emphasis is on proving theorems about dominance
relations on classes of candidate plans.  Plan classes are generated by
posting constraints at various levels of abstraction, then classified within a
plan lattice that manages inheritance of properties and dominance
characteristics.  An analysis of {\sc tweak} demonstrates how to recast
existing planning ideas in this framework, providing insight into the planner's
capabilities with a dominance-proving interpretation.  The plan lattice
representation highlights the role of plan subsumption in optimizing search.

\end{abstract}

\footnotetext{Supported by National Institutes of Health Grant No.\
R01~LM04493 from the National Library of Medicine.}

\section{Introduction}

One glaring limitation of the traditional AI robot planning paradigm is its view
of goals as logical predicates on world states.  Such a view precludes the
consideration of uncertainty except in rare cases where either uncertainty is
adequately captured in tolerances or execution monitoring with replanning is
viable.  Even in the absence of uncertainty, planning to satisfy goal predicates
provides no mechanism to choose among the plans that achieve the goal nor
any guidance about what to do when no such plan exists.  The literature has
offered ad hoc solutions to overcome some of these limitations in specific
cases, for example, simple resource allocation mechanisms or domain-specific
meta-planning rules.

Alternate views, such as Bayesian decision theory, offer more comprehensive
choice criteria but do not address the planning task of {\it constructing}
strategies from more primitive actions.

In this paper I describe a formal framework for planning that permits the
broader range of choice criteria necessary in an environment of partially
satisfiable goals with multiple objectives.  At the same time it can
incorporate many of the principles, representations, and techniques of existing
research on planning.  Central to the framework is the notion of planning as the
derivation and propagation of dominance relations among classes of candidate
plans.

Definitions and explanations of the structures constituting the planning
framework are provided in the sections below.  The theoretical apparatus is
illustrated with an investigation of {\sc tweak}, a nonlinear constraint-posting
planner~\cite{Chapman85a}.  Although {\sc tweak} is defined in terms of
logical goal predicates, an interpretation in terms of the dominance relation
provides insight into its capabilities and efficiency.  An analysis of {\sc
tweak}'s search procedure highlights the role of plan subsumption
computations in this approach to planning.

\section{The Plan Lattice}\label{plan-lattice}

Let $\cal L$ be the planning language, or equivalently, the set of all
syntactically valid plans.  For example, if $A=\{a_1,\ldots,a_n\}$ is an
alphabet of primitive actions, then ${\cal L} = A^*$ is the language of linear
plans.  The language of nonlinear plans is similar, extended by an encoding for
partial orders.  A {\it plan class} is any set of plans, ${\cal P} \subseteq
{\cal L}$.  $\cal P$ is also called a {\it partial plan} when it represents a set
of constraints that incompletely specifies the plan we are concerned about.

We can view the planning process as one of incrementally adding constraints to
candidate plan classes until some problem is solved regarding the plan to be
executed.  In traditional planning the problem is to identify a plan that
satisfies the given goal.  With a more versatile evaluation criterion, the
problem is to find the best plan.  Except for some special cases where
convenient optimization techniques are applicable, it is not possible to
determine whether a given plan is optimal by examining it in isolation.  It may
be more reasonable to answer questions about the optimal plan without
necessarily constructing a complete description.

The partial plans generated during the planning process can be organized in a
specialization lattice according to the subset relation.  An example of a plan
specialization lattice appears in Figure~\ref{specialization-graph}.  The node in
the graph marked ``$A^* a_1 A^*$'' denotes the set of all plans with at least
one instance of action $a_1$.  The set of plans {\it beginning} with $a_1$ forms
a subclass, as does the set of plans where $a_1$ is followed by $a_2$.

\begin{figure}[htbp]
\begin{picture}(130,35)(20,3)
\put(65,29){\makebox(10,10){$\cal L$}}
\put(70,30){\line(0,-1){8}}
\put(70,30){\line(-4,-1){30}}
\put(70,30){\line(4,-1){30}}
\put(35,15){\makebox(10,10){$ A^* a_1 A^*$}}
\put(40,16){\line(-2,-1){18}}
\put(40,16){\line(2,-1){15}}
\put(40,16){\line(6,-1){45}}
\put(65,15){\makebox(10,10){$ A^* a_2 A^*$}}
\put(70,16){\line(-2,-1){15}}
\put(70,16){\line(6,-1){45}}
\put(95,15){\makebox(10,10){$ A^* a_3 A^*$}}
\put(100,16){\line(-2,-1){15}}
\put(100,16){\line(2,-1){15}}
\put(20,0){\makebox(10,10){$a_1 A^*$}}
\put(50,0){\makebox(10,10){$ A^* a_1 a_2 A^*$}}
\put(80,0){\makebox(10,10){$ A^* a_1 a_3 A^*$}}
\put(110,0){\makebox(10,10){$ A^* a_2 a_3 A^*$}}
\end{picture}
\caption{A plan specialization lattice.}
\label{specialization-graph}
\end{figure}

The plan lattice representation of a search space supports a {\it
constraint-posting} approach to planning.  A constraint-posting planner,
illustrated best by {\sc molgen}~\cite{Stefik81a}, can be more
efficient than a planner that evaluates only complete plans.  Flexibility is
gained by allowing many forms of constraints rather than, for instance, just
adding actions to a sequence or specifying exact bindings for variables.
However, these advantages depend on having some justification for the
constraints based on properties of the partial plan.  For example, {\sc molgen}
knows that for a {\it screen} operation to be useful, it must select the
appropriate bacteria.  Thus, when adding a {\it screen} step to a plan, {\sc
molgen} is justified in posting a constraint of the form ({\bf resists} {\it
antibiotic-1 bacterium-4}\/); constraining the antibiotic to a particular chemical
agent would be unjustifiably specific at this stage.

By adding only the constraints that have the best justifications, a planner
implements a {\it least commitment} strategy.  An extreme form of least
commitment propagates only provable properties of admissible plans.  In
practice, however, real planners, like {\sc molgen}, have to make guesses
when no provable constraints are available.  The least commitment heuristic
tends to minimize both the likelihood of wrong guesses and the extent of
backtracking required to recover from such mistakes.  A policy of working on
plan classes at high levels of abstraction is simply a particular form of least
commitment strategy.  Because it avoids backtracking, a search procedure that
preserves the entire lattice of partial plans corresponds to ``no commitment''
planning.

\section{Dominance in the Plan Lattice}

To speak meaningfully of dominance among plan classes, we need to introduce
a {\it preference relation}, $\succ$, over plans.  In categorical planning, for
example, one plan is preferred to another if it achieves the goal and the other
does not.  To state this in terms of the {\it situation
calculus}~\cite{McCarthy-Hayes}, we write:
\begin{eqnarray}\label{predicate-preference}
\pi_1\succ \pi_2 & \Leftrightarrow & G(result(robot,\pi_1,s_i))\wedge\;\; \nonumber\\
 & & \;\;\;\; \neg G(result(robot,\pi_2,s_i)).
\end{eqnarray}
$G$ is the goal predicate, defined on situations resulting from the robot
performing a plan in a given situation.  Here $s_i$ denotes the initial situation.
Two plans that both achieve or do not achieve the goal are equally preferred,
or {\it indifferent}, denoted by $\sim$.  The expression $\pi_1\succeq \pi_2$
means that $\pi_1$ is preferred or indifferent to $\pi_2$.

The preference relation characterizes the choice criterion employed by the
planner.  A planner based on expected utility takes
\begin{equation}
\pi_1\succ \pi_2\Leftrightarrow E\left[u(\pi_1)\right] >
E\left[u(\pi_2)\right].
\end{equation}
The discussion of dominance that follows does not depend on any particular
criterion for plan choice.  Although we assume that $\succeq$ is a total order
on plans, we do not insist that the planner be given a complete or even an
explicit description of the preference relation.

We say that a class of plans {\it dominates} another if, for any plan in the
second class, some plan in the first class is preferred or indifferent.  It should
be emphasized that it is possible to prove dominance without identifying the
superior plan---otherwise this approach provides no advantage over
branch-and-bound search.  The dominance relation, $D$, is defined as follows:
\begin{equation}\label{weak-dom}
D({\cal P}_1,{\cal P}_2)\stackrel{\rm def}{=} \forall\pi_2\in {\cal P}_2\; \exists
{\pi}_1\in {\cal P}_1\; \pi_1\succeq \pi_2.
\end{equation}
The strict version of dominance, $D'$, is defined similarly, except that here a
particular plan in the first class is preferred to any in the
second.\footnote{This difference is required because of the possibility of
infinite plan classes with no maximal elements.  If~(\ref{strict-dom}) were
exactly a strict version of~(\ref{weak-dom}), then such a class would strictly
dominate itself.  For the same reason, a definition of weak dominance that
merely substituted $\succeq$ for $\succ$ in~(\ref{strict-dom}) would not entail
the reflexive property.  Assuming every plan class has a maximal plan is
unreasonable, even if it is appropriate to require that $\cal L$ does.}
\begin{equation}\label{strict-dom}
D'({\cal P}_1,{\cal P}_2)\stackrel{\rm def}{=} \exists \hat{\pi}_1\in {\cal
P}_1\;\forall\pi_2\in {\cal P}_2\; \hat{\pi}_1\succ \pi_2.
\end{equation}
Clearly, strict dominance implies dominance.  In addition, the properties below
follow easily from the definitions:
\begin{equation}\label{order}
D\mbox{ is reflexive, transitive, and complete.}
\end{equation}
\begin{equation}
D'\mbox{ is anti-reflexive, transitive, and asymmetric.}
\end{equation}
\begin{equation}
D({\cal P}_1,{\cal P}_2)\Leftrightarrow\neg D'({\cal P}_2,{\cal P}_1)
\end{equation}
\begin{equation}\label{dom-inherit}
{\cal P}_2\subseteq {\cal P}_1 \Rightarrow D({\cal P}_1,{\cal P}_2)
\end{equation}
\begin{equation}\label{p-unions}
D({\cal P}_1,{\cal P}_2)\wedge D({\cal P}_3,{\cal P}_4)\Rightarrow D({\cal
P}_1\cup {\cal P}_3, {\cal P}_2\cup {\cal P}_4)
\end{equation}
\begin{equation}\label{disjunct}
D({\cal P}_1,{\cal P}_3)\vee D({\cal P}_2,{\cal P}_3)\Leftrightarrow D({\cal
P}_1\cup {\cal P}_2, {\cal P}_3)
\end{equation}
\begin{equation}\label{inherit-strict}
D'({\cal P}_1,{\cal P}_2)\wedge D({\cal P}_2,{\cal P}_3)\Rightarrow D'({\cal
P}_1,{\cal P}_3)
\end{equation}

These properties serve as dominance propagation rules within the plan lattice.
By~(\ref{dom-inherit}) and the transitivity of $D$, dominance by a particular
class is inherited in the plan lattice.  Strict dominance is also inherited,
by~(\ref{inherit-strict}) and weak dominance inheritance.  Thus, markers or
links indicating dominance relations need be stored only at the upper envelope
of classes to which they apply.  Dominance is propagated upwards in the
lattice by application of the union properties (\ref{p-unions}
and~\ref{disjunct}), which also hold for $D'$.

A plan class is {\it restricted} by asserting that it is weakly dominated by one
of its subsets.  In the {\sc molgen} example given above, if ${\cal P}_1$ is
the class of plans that include the {\it screen} operation, and ${\cal P}_2$ is
the subclass that includes the {\bf resists} relation as well, then $D({\cal
P}_2,{\cal P}_1)$ asserts that ({\bf resists} {\it antibiotic-1 bacterium-4}\/)
is a {\it valid} constraint.  The new dominance assertion represents progress
because it lets us focus our attention on a smaller set of plans.  Thus,
deriving these restrictions is an important task of the dominance prover.

Constraints might be posted to explore the search space even though the
dominance relation does not provably hold.  Often, such constraints are
justified by identifiable {\it assumptions} that imply dominance.  We can
express this case by asserting the {\it conditional dominance relation},
$D_S$, for $S$ an assumption proposition
\begin{equation}\label{conditional-dom}
D_S({\cal P}_1,{\cal P}_2)\stackrel{\rm def}{=} S\Rightarrow D({\cal
P}_1,{\cal P}_2).
\end{equation}

Normal dominance is just $D_{\bf true}$.  As an example of conditional
dominance, suppose that we are uncertain about the identity of the organism of
interest; it could be either {\it bacterium-2} or {\it bacterium-3}.  For $i=2$
and $3$, let $S_i$ be the proposition ``Bacterium-$i$ is the organism of
interest'' and ${\cal P}_i$ the plan class that restricts ${\cal P}_1$ to those
plans in which the {\bf resists} relation holds between {\it antibiotic-1} and
{\it bacterium-}$i$.  Then we have $D_{S_2}({\cal P}_2,{\cal P}_1)$,
$D_{S_3}({\cal P}_3,{\cal P}_1)$, and $S_2\vee S_3$.  By the definition of
conditional dominance~(\ref{conditional-dom}), we get $D({\cal P}_2,{\cal
P}_1)\vee D({\cal P}_3,{\cal P}_1)$.  Application of~(\ref{disjunct}) yields the
result $D({\cal P}_2\cup {\cal P}_3,{\cal P}_1)$.

Of particular value are conditional dominance relations where $S$ itself
contains dominance assertions.  For example, if $S'\equiv D({\cal
P}_1,{\cal L})$, then $D_{S'}({\cal P}_2,{\cal P}_1)$ asserts that given the optimal
plan is in ${\cal P}_1$ we can further confine attention to ${\cal
P}_2$.\footnote{In categorical planning, $D_{S'}$ is the same as $D$ (that is,
$D_{S'}({\cal P}_1,{\cal P}_2)\Leftrightarrow D({\cal P}_1,{\cal P}_2)$) due to
the binary nature of the preference relation~(\ref{predicate-preference}).} This
is one way to derive the restrictions mentioned above.  In fact, this is
precisely the strategy employed by both Pednault~\cite{Pednault85} and
Chapman~\cite{Chapman85b} to limit the search space of their planners.  We
will see how this works for the latter example in Section~V below.

Reasoning about conditional dominance can be implemented straightforwardly
via any mechanism for reason maintenance~\cite{deKleer86,McAllester82}.
The interesting task for the dominance prover is to come up with meaningful
conditions that imply useful dominance relations.

\section{Planning}\label{planning}

A program manipulates the plan lattice by repeatedly performing the following
steps (not in any particular order):
\begin{itemize}
\item Generate new plan classes by adding constraints to undominated
classes.
\item Construct and refine the prediction/evaluation part of the world model.
\item Derive and propagate dominance relations among plan classes. 
Strengthen conditional dominance relations.
\end{itemize}

We will say that a program performing these tasks is {\it planning}.  Note that
in this view planning is not a search for a single plan to execute, but an
exploration of properties of admissible plans.  A planner performs useful work
by refining the plan lattice, even if the lowest-level classes are never reduced
to singleton sets.  If, after much computation, the planner has narrowed the
admissible plans to a set that contains $10^{400}$ or possibly an uncountable
infinity of plans, this may seem like little progress.  But if we can determine
that all plans contain, for example, an appendectomy, we solve a significant
problem.\footnote{Plan classes with such huge cardinalities should be the
norm, not exceptions.  If the plan language includes real-valued parameters,
then all but the tightest constraints still leave an uncountable set of candidate
plans.  The plan class ``Administer a dose of drug $X$ within the next minute''
includes individual plans where the drug is given at any point in the 60-second
interval.}

The prevailing view of planning as construction of a completely specified
course of action is never totally accurate.  Planners devote their resources to
isolated {\it decisions}, as in whether or not to perform an appendectomy,
without specifying all other features of the plan.  A plan to obtain some
bananas is complete only with respect to a {\it have-bananas} goal; in the
larger context of satisfying all physical and emotional needs forever, the
agent never stops planning.  Figuring out how to get the bananas is a small
act of refinement on {\sc the big plan}.

The framework presented so far should be regarded as an abstract model of
planning with partially satisfiable objectives.  It generalizes the case of goal
predicates and applies to uncertain situations.  Rather than prove that a plan
necessarily achieves a goal, as in traditional AI planning, the planner tries to
prove properties of the optimal plan.  These properties define the class of
admissible plans.

To instantiate\label{instantiate} the abstract model to a particular planning
mechanism, one needs to specify:
\begin{itemize}
\item The plan language, $\cal L$.
\item A constraint language (representation for partial plans).
\item A domain modeling language, including a way to describe the effects of
actions and a representation for the preference relation, $\succ$.
\item A dominance prover.
\end{itemize}
The structures described earlier---the plan lattice and dominance
relations---serve mainly as theoretical machinery for analysis of this class of
planners.  Specifying the languages and the dominance prover is the real work
in designing a planner.

As a simple illustration, consider mathematical optimization techniques as
planners.  Optimization is a special case of dominance
proving where the program tries to find a singleton dominator, often in one
step.  For example, if our plan language is $\Re^n$ and the domain model
consists of a linear objective function and a set of linear constraints among the
elements of the vector, then our dominance prover should be a linear
programming algorithm.  In this case there are no partial plans.
Branch-and-bound integer programming is an example of an optimization
procedure that does make use of partial plans and explicit dominance proving.

In the development of the planning model up to now, we have paid little
attention to efficiency.  The computational value of planners in this framework
depends on a judicious choice of the languages and algorithms that define it.
Although it is difficult to characterize efficiency at the present level of
generality, there are a few high-level issues that can be identified at this
point.  First, the addition of constraints during lattice refinement cannot be
arbitrary.  The planner must generate constraints that relate to the problem at
hand and are meaningful to the dominance prover.  Unless the prover can
establish dominance relations on the lattice, refinement is irrelevant.  Second,
it is important to consolidate the plan lattice to avoid redundancy and further
the propagation of dominance relations.  We will examine this topic further in
Sections VI and~VII below.

\section{An Extended Illustration: Tweak}\label{tweak}

In the introduction I suggested that existing planning work can be recast in this
framework.  In this section I examine {\sc
tweak}~\cite{Chapman85a,Chapman85b}, a nonlinear planner that captures
much of the state-of-the-art in a neat algorithm.  Though {\sc tweak} belongs
to the mainstream planning tradition in considering only goal predicates, its
main ideas can be expressed clearly in terms of the plan lattice and
dominance relation.

As described in the previous section, the way to instantiate this planning
framework is to define the various representations appearing in and operations
performed on the plan lattice.  The plan language for {\sc tweak} is
particularly simple.  A plan is a sequence of steps, each specifying an action
applied to some objects.  The term ``nonlinear'' refers not to plans, but to the
representation for incomplete plans, or plan classes.\footnote{A planner with
a parallel execution capability (for example, a multi-agent planner) could
actually have a nonlinear plan language.  The constraint language for such a
planner would be more complex.} A plan class is nonlinear if it specifies only
a partial order on its steps.  There are two other sources of incompleteness in
{\sc tweak}: steps may be missing, and steps may refer to variables rather
than constant objects.  Thus any partial plan in {\sc tweak} may be specified
by the steps it includes, the ordering constraints on the steps, and the
constraints on the designations of variables in the steps.

The domain modeling language is also quite simple.  The effects of actions are
completely described by finite sets of pre- and post-conditions on each step.
A world model corresponding to each plan class records the status of goal and
condition propositions in a propositional database.  Finally, $\succeq$ is
defined by the categorical planning preference
relation~(\ref{predicate-preference}).  In {\sc tweak}, $G$ is simply a
conjunction of propositions.

The interesting part of {\sc tweak} is not these representation languages, but
the dominance properties that are applied.  The power of the planning
algorithm derives from the fact that, given a partial plan, we need to consider
only a few types of constraints to guarantee that if a satisfactory completion
of the partial plan exists, one also exists among its constrained subclasses.
Constraints are posted via {\it plan modification operators.} For our purposes
it helps to regard these operators as functions that return constrained plan
classes given a starting plan class and possibly some other arguments.  We
need five plan modification operators:

\begin{itemize} \item $addstep({\cal P},t)$ \item $order({\cal P},s,t)$ \item
$codesignate({\cal P},x,y)$ \item $noncodesignate({\cal P},x,y)$ \item
$ifcodesignate({\cal P},x,y,z,w)$ \end{itemize}

Each returns the set of elements of $\cal P$ that satisfy the indicated
constraint.  $Addstep$ constrains the partial plan to include an instance of step
$t$.  $Order$ confines $\cal P$ to those plans in which step $s$ is applied
before step $t$.  Note that if this (or the result of any modification operation)
is a contradiction, then the function returns the empty plan class.  Analogously,
if the constraint is already implied, the operator is the identity function on
$\cal P$.  The $codesignate$ (abbreviated $cod$\/) and $noncodesignate$
($ncod$\/) functions add the appropriate constraints to the elements indicated.
In general, there may be several ways to implement a codesignation among
complex elements (such as predicate instances) in terms of their primitive
constituents.  Finally, the $ifcodesignate$ ($ifcod$\/) function constrains $z$
and $w$ to codesignate if $x$ and $y$ do.

{\sc Tweak} is defined by a nondeterministic procedure that achieves a goal by
applying combinations of these operators to a partial plan.  Chapman presents
the procedure as a simple graph (\cite[page~1024]{Chapman85a},
\cite[page~11]{Chapman85b}) where the paths from start to end exhaust the
possible sequences of plan modifications that can restrict a partial plan $\cal
P$ to achieve a goal proposition $p$ at step $s$.  A completely analogous
description in our functional notation is the expression appearing in
Figure~\ref{tweak-algorithm}.  This complicated expression, consisting of a
combination of plan classes formed by various modifications on $\cal P$,
represents the set of plans nondeterministically explored by Chapman's
algorithm.

\begin{figure}[htbp]
\begin{tabbing}
$\bigcap\;$\= $\bigcup_{t\in E}\;$\= $\bigcap\;$\=
${\cal A}_t$\\
\>\>\>$\bigcup_{u\in conseq(t)}\; {\cal B}_{t,u}$\\
\>$\bigcap_{c\in C}\; \bigcup\;$\= ${\cal C}_c$\\
\>\>$\bigcap_{q\in conseq(c)}\; \bigcup\;$\= ${\cal D}_q$\\
\>\>\>$\bigcup_{w\in W}\; \bigcap\;$\= ${\cal E}_{c,w}$\\
\>\>\>\>${\cal F}_{w}$\\
\>\>\>\>$\bigcup_{r\in conseq(w)} \;{\cal G}_{q,w,r}$
\end{tabbing}
\flushleft{\bf key:}

\begin{math}
\begin{array}{lcl}
{\cal A}_t & = & order(addstep({\cal P},t),t,s)\\
{\cal B}_{t,u} & = & cod(addstep({\cal P},t),u,p)\\
{\cal C}_c & = & order({\cal P},s,c)\\
{\cal D}_q & = & ncod({\cal P},p,q)\\
{\cal E}_{c,w} & = & order(addstep({\cal P},w),c,w)\\
{\cal F}_{w} & = & order(addstep({\cal P},w),w,s)\\
{\cal G}_{q,w,r} & = & ifcod(addstep({\cal P},w),p,q,r,p)
\end{array}
\end{math}
\caption{The {\sc tweak} algorithm.}\label{tweak-algorithm}
\end{figure}

Let ${\cal P}'$ denote this plan class.  In the figure, $E$ is the set of {\it
establishers}\/; that is, actions that possibly assert the goal proposition.  $C$
and $W$ are the potential {\it clobberers} (actions that negate the goal) and
{\it white knights} (actions that re-establish the goal), respectively.  The
function $conseq$ on steps returns the consequent propositions, or
postconditions, of the action.  That there is a plan in ${\cal P}'$ that achieves
the goal if there is one in $\cal P$ can be captured by asserting $D({\cal
P}',{\cal P})$.  This is a restriction, because each of the components of the
${\cal P}'$ expression is itself a subset of $\cal P$.

The main theoretical contribution of {\sc tweak} boils down to this dominance
condition.  {\sc Tweak} refines $\cal P$ by adding constraints until it finds a
partial plan that necessarily achieves the goal, that is, a class provably
containing only goal-achieving plans.  The theoretical apparatus we have
developed can help us understand this process.

Each term in the expression of Figure~\ref{tweak-algorithm} corresponds to a
plan class which is a subset of $\cal P$.  These distinguished plan classes
serve as intermediate structure in the plan lattice depicted in
Figure~\ref{tweak-lattice}.  This lattice reflects a decomposition of the search
space based on the {\sc tweak} algorithm.  The plan classes with subscripts
denote parameterized classes; a complete diagram of this lattice would
include, for instance, an ${\cal A}_t$ for every $t\in E$.  For the directed
links, the plan class pointed to is defined by the boxed set operation applied
to the others.  Thus ${\cal K}_t\stackrel{\rm def}{=} {\cal B}_t\cap {\cal
A}_t$ and ${\cal I}_c\stackrel{\rm def}{=} \bigcap_q{\cal I}_{c,q}$.  All
connections indicate specialization of plan classes from higher to lower levels.

\begin{figure}[htbp]
\begin{picture}(105,61)(37,7)
\put(81,60){\makebox(10,10){$\cal P$}}
\put(86,62){\line(-4,-1){45}}
\put(86,62){\line(-3,-1){35}}
\put(86,62){\line(-2,-1){25}}
\put(86,62){\line(-5,-6){10}}
\put(86,62){\line(4,-1){50}}
\put(86,62){\line(3,-1){40}}
\put(86,62){\line(2,-1){25}}
\put(86,62){\line(5,-6){10}}
\put(36,42){\makebox(10,10){${\cal B}_t$}}
\put(41,39){\vector(0,1){5}}
\put(46,42){\makebox(10,10){${\cal A}_t$}}
\put(51,44){\line(0,-1){5}}
\put(56,42){\makebox(10,10){$\cal K$}}
\put(61,39){\vector(0,1){5}}
\put(71,42){\makebox(10,10){${\cal J}_c$}}
\put(76,44){\line(0,-1){5}}
\put(91,42){\makebox(10,10){${\cal I}_{c,q}$}}
\put(96,44){\line(0,-1){5}}
\put(106,42){\makebox(10,10){${\cal E}_{c,w}$}}
\put(121,42){\makebox(10,10){${\cal F}_w$}}
\put(126,44){\line(0,-1){5}}
\put(131,42){\makebox(10,10){${\cal G}_{q,w}$}}
\put(136,39){\vector(0,1){5}}
\put(38.5,34){\framebox(5,5){$\cup_u$}}
\put(41,34){\line(0,-1){5}}
\put(48.5,34){\framebox(5,5){$\cap$}}
\put(51,39){\line(-2,1){10}}
\put(51,34){\vector(0,-1){5}}
\put(58.5,34){\framebox(5,5){$\cup_t$}}
\put(61,34){\line(-2,-1){10}}
\put(73.5,34){\framebox(5,5){$\cap_c$}}
\put(76,34){\vector(0,-1){5}}
\put(83.5,34){\framebox(5,5){$\cup$}}
\put(86,39){\vector(-2,1){9}}
\put(86,34){\line(0,-1){5}}
\put(86,34){\line(2,-1){9}}
\put(93.5,34){\framebox(5,5){$\cap_q$}}
\put(96,34){\vector(0,-1){5}}
\put(103.5,34){\framebox(5,5){$\cup$}}
\put(106,39){\vector(-2,1){9}}
\put(106,34){\line(0,-1){5}}
\put(106,34){\line(2,-1){10}}
\put(123.5,34){\framebox(5,5){$\cap$}}
\put(126,39){\line(-3,1){15}}
\put(126,39){\line(2,1){10}}
\put(126,34){\line(0,-1){16}}
\put(126,18){\vector(-1,-1){10}}
\put(133.5,34){\framebox(5,5){$\cup_r$}}
\put(136,34){\line(0,-1){5}}
\put(36,21){\makebox(10,10){${\cal B}_{t,u}$}}
\put(46,21){\makebox(10,10){${\cal K}_t$}}
\put(71,21){\makebox(10,10){${\cal J}$}}
\put(76,23){\line(0,-1){5}}
\put(81,21){\makebox(10,10){${\cal C}_{c}$}}
\put(91,21){\makebox(10,10){${\cal I}_{c}$}}
\put(101,21){\makebox(10,10){${\cal D}_{q}$}}
\put(111,21){\makebox(10,10){${\cal H}_{c,q}$}}
\put(116,18){\vector(0,1){5}}
\put(131,21){\makebox(10,10){${\cal G}_{q,w,r}$}}
\put(73.5,13){\framebox(5,5){$\cap$}}
\put(76,18){\line(-3,5){15}}
\put(76,13){\vector(0,-1){5}}
\put(113.5,13){\framebox(5,5){$\cup_w$}}
\put(116,13){\line(0,-1){5}}
\put(70,0){\makebox(10,10){${\cal P}'$}}
\put(111,0){\makebox(10,10){${\cal H}_{c,q,w}$}}
\end{picture}
\caption{The plan lattice corresponding to the space searched by the {\sc
tweak} algorithm.}\label{tweak-lattice}
\end{figure}

Because it would be difficult for the planner to generate a description of ${\cal
P}'$ directly from the definition of Figure~\ref{tweak-algorithm}, in practice it
is necessary to manipulate representations of these intermediate classes.  The
{\sc tweak} search procedure nondeterministically chooses intermediate plan
classes to instantiate and combine until it finds a subset of ${\cal P}'$ that
necessarily achieves $p$ at $s$.  In the process, the algorithm recursively
invokes itself, taking one of the intermediate classes as $\cal P$ and forming
the structure of Figure~\ref{tweak-lattice} beneath it.

\section{Classification and Dependency-Directed Search}\label{dependency}

It is possible that a recursive invocation of the {\sc tweak} dominance relation
would reveal that some intermediate plan classes at one level are dominated
by more restricted classes at lower levels.  More generally, propagation
via~(\ref{dom-inherit}) through~(\ref{inherit-strict}) may uncover dominance
conditions within or between levels which can be exploited to reduce the search
space.

These possibilities suggest an addition to the planning steps listed at the
beginning of Section~IV\@.  When partial plans are generated, they
are {\it classified} by finding their greatest lower and least upper bounds in
the plan lattice.\footnote{The term {\it classified} is used here in the same
sense that concepts are classified in {\sc kl-one}~\cite{Schmolze83}.  Swartout
and Neches~\cite{Swartout86} represent plans by the goals they are intended
to achieve and employ a classifier to construct a taxonomy of intents.  Their
decision-making program selects from the taxonomy the most specific plan for
the purpose at hand.  Because this taxonomy comprises {\it complete} plans,
their use of classification falls outside of the planning framework developed
here.} Classification serves to consolidate the lattice, resulting in a maximal
propagation of the known dominance conditions.

The dominance relation provides us with a class of {\it nogood} sets to be
used in pruning the search space.  Planners without a notion of dominance can
consider only contradictory plans (that is, empty plan classes) to be nogood;
other pruning criteria must be built into the control mechanism.  The discussion
above illustrates that although {\sc tweak}'s search procedure implicitly takes
advantage of the fact $D({\cal P}',{\cal P})$, it cannot exploit the dominance
consequences for intermediate plan classes.

Consolidating the plan lattice through classification prevents redundancy in plan
space search.  Notice, for example, that the plan class ${\cal D}_q$ depends
only on $q$, even though its position in the expression for ${\cal P}'$ is within
the scope of $c$.  A chronologically backtracking search would generate this
class for every $(c,q)$ pair encountered during the iteration, resulting in a
duplication of effort if clobberers share consequents.

A simple dependency-recording mechanism would most likely avoid this and
similar redundancies.  A clever enough scheme might even recognize that
${\cal A}_t$ and ${\cal F}_w$ are the same when $t=w$.  However, it is
doubtful that any of the standard dependency maintenance mechanisms would
catch the more subtle relationships that hold between classes created on
successive recursive invocations of the planning algorithm.  A precise
characterization of avoidable redundancies is rarely offered in descriptions of
planners.

Following the terminology used by de Kleer in describing his {\it
assumption-based} truth maintenance system (ATMS)~\cite{deKleer86}, each
plan class is an {\it assumption context}\/ represented by the plan
modification operators defining it.  The plan specialization lattice corresponds
to the context lattice of the ATMS with context subset replaced by plan
subsumption.  Indeed, an implementation using an ATMS would be just as
powerful as the classification scheme presented here, {\it provided that} we
could construct a propositional interface~\cite{deKleer86a} capable of
communicating the relevant implications of partial plans.  In our case, though,
this does not appear feasible.  A mapping of partial plans to sets of
propositions would force us to create distinctions (for instance, in unique
identifiers for steps) that would fail to preserve isomorphism characteristics.

Like the assumption-based approach, the plan lattice structure facilitates the
exploration of multiple consistent contexts simultaneously.\footnote{This
contrasts with the dependency-directed backtracking employed by {\sc
tweak}.  The design of {\sc schemer}~\cite{Zabih87,Zabih87a}---a
dependency-directed interpreter for a non-deterministic {\sc
lisp}---illustrates this difference and highlights the issues in constructing a
propositional interface for arbitrary dependencies.} But contrary to the ATMS
view, we are not interested in finding all solutions (the class of all plans that
achieve the goal).  Therefore, we can restrict the domain of assumption sets
that need to be considered to those explicitly created as plan classes by the
planning algorithm.

To recap, the scheme presented here offers two sources of benefits with
respect to plan search efficiency.  First, the dominance relation provides a
major new class of nogoods which may potentially shrink the search space.
Second, consolidation of the lattice through classification of partial plans
takes advantage of dependencies that might be obscured by an interface with
a propositional TMS.

\section{The Complexity of Subsumption}\label{subsumption}

As for knowledge representation mechanisms, the key operation in plan
classification is the computation of subsumption relations~\cite{Tractability}.
We saw above that classifying plans as they are generated minimizes the
search space.\footnote{For true optimality we must also determine the most
general plan class that is dominated.  This corresponds to extracting the
minimal nogood assumption set, which is not generally feasible.  Note that
minimality is with respect to a particular constraint language; slight changes
may have dramatic effects on the dominance prover's ability to derive nogood
sets at high levels of generality.  For example, Pednault~\cite{Pednault85}
achieves stronger dominance results by including protected conditions as
constraints on plans.} Conversely, a perfect dependency mechanism is in effect
computing these subsumptions.

Unfortunately, nonlinear plan subsumption is NP-complete.\footnote{The proof,
by reduction from {\sc exact cover by 3-sets}, was provided by Ronald L.\
Rivest, personal communication.} This is true even for plan classes derived
exclusively from $addstep$ and $order$ operators, that is, partial orders on
steps.  The exponential potential of subsumption lies in the combinatorial
number of possible mappings between the steps of the two plan classes.  If,
however, we can specify the correspondences between steps (for example,
which {\it put-on} in ${\cal P}_1$ corresponds to which in ${\cal P}_2$), then
subsumption is at worst quadratic.  In practice we will generally not have
complete correspondences, but typically the possible mappings between steps
will be highly constrained.  Actions may map only to others of the same type,
therefore the computation will not be prohibitive as long as plan classes do
not contain many steps of a single type.  Codesignation constraints also help
to restrict the possible mappings, as do explicit identifications among steps
which may be provided by the planner when introducing steps in several
partial plans at once.  Finally, we might consider restricting the constraint
language so that subsumption is tractable, perhaps to tree-shaped partial
orders.

The effect on subsumption complexity of proposed extensions to the constraint
language should also be considered.  For example, we could allow actions
themselves to be expressed at multiple levels of abstraction (as in the
sequence {\it low-dose steroid therapy} is-a {\it steroid therapy} is-a {\it
drug therapy}\/) without significant cost in complexity, as long as action
subsumption itself is not expensive.\footnote{Given a static action lattice,
action subsumption takes logarithmic time.  If actions are described more
flexibly---perhaps as dynamically generated {\sc kl-one} concepts---then
subsumption is more complex~\cite{Tractability}.}  Extending the plan
modification operators to include union and intersection, as suggested by
Figure~\ref{tweak-lattice}, is not as benign.  Intersection (conjunction)
presents no problem because the plan modification operators associate and
commute, but computing subsumption among classes that are unions
(disjunctions) of other classes appears substantially more difficult.

\section{Summary}

In this paper I have introduced and applied some analytical tools for studying
and designing constraint-posting planners.  The main components of this
framework are a specialization lattice and a dominance relation defined over
plan classes.  These concepts were motivated with simple examples from {\sc
molgen} and a more detailed account of {\sc tweak}.  The power of the {\sc
tweak} algorithm resides in a central dominance result which allows the planner
to restrict attention to a small subset of the possible completions of a partial
plan.  Explicit characterization of the dominance relation allows the planner to
recognize that certain plan classes need not be explored, even though they
might contain a valid plan.  Although standard dependency-directed
backtracking methods improve search efficiency, the only way to ensure
complete lack of redundancy is to classify the partial plans in the lattice by
computing subsumption among plan classes.  This problem is NP-complete for
nonlinear planning, but constraints commonly arising in practice may render the
computation tractable.  Recognizing the centrality of subsumption suggests a
novel approach to analyzing the complexity implications of plan constraint
languages.

The true test of the scheme presented here will be how well it supports tasks
that require planning in the presence of uncertainty and partially satisfiable
objectives.  I am currently applying this framework to the design of a planner
for the task of formulating decision models from a large medical knowledge
base.  The domain modeling language and dominance prover proposed for this
task are based on ongoing work on qualitative influence
networks~\cite{Wellman87a,Wellman87d}.

\section*{Acknowledgments}

Discussions with Zak Kohane, Ramesh Patil, Ron Rivest, Elisha Sacks, Peter
Szolovits, Kate Unrath, Tom Wu, and Ramin Zabih contributed to the style and
content of this paper.

\bibliographystyle{aaai}
\bibliography{/u/publish/bib/bib}

\end{document}

Outstanding suggestions:

- use Chapman's diagram
- nail down complexity of tree-shaped partial orders
- reduce hand-waviness of complexity discussion
- some constraint languages (FOPC) undecidable
- define ``constraint''