\documentstyle[jair,twoside,11pt,theapa]{article}

%% revised after receiving reviewers' comments
%% final version

\input epsf       % the file that defines the macros for including eps
                  % figures 
\epsfverbosetrue  % TeX will report the size of each figure

\input verbatim   % some useful macros for program listings
\input my-abbrevs % useful abbreviations

\special{papersize=8.5in,11in}   % gives the right papersize to dvips

\jairheading{4}{1996}{287--339}{1/96}{5/96}
\ShortHeadings{Planning for Contingencies: A Decision-based Approach}
{Pryor \& Collins}
\firstpageno{287}   % to be changed


\title{Planning for Contingencies: A Decision-based Approach}

\author{\name Louise Pryor \email louisep@aisb.ed.ac.uk \\
        \addr Department of Artificial Intelligence, University of
        Edinburgh\\  
              80 South Bridge\\ 
              Edinburgh EH1 1HN, Scotland 
        \AND
        \name Gregg Collins \email collins@ils.nwu.edu\\
        \addr The Institute for the Learning Sciences, Northwestern
        University\\ 
              1890 Maple Avenue\\
              Evanston, IL 60201, USA}

\date{}

\begin{document}

\maketitle

\begin{abstract}
  A fundamental assumption made by classical AI planners is that there
  is no uncertainty in the world: the planner has full knowledge of
  the conditions under which the plan will be executed and the outcome
  of every action is fully predictable.  These planners cannot
  therefore construct contingency plans, \ie, plans in which
  different actions are performed in different circumstances.  In this
  paper we discuss some issues that arise in the representation and
  construction of contingency plans and describe \cass, a
  partial-order contingency planner.  \Cass\ uses explicit
  decision-steps that enable the agent executing the plan to decide
  which plan branch to follow.  The decision-steps in a plan result in
  subgoals to acquire knowledge, which are planned for in the same way
  as any other subgoals.  \Cass\ thus distinguishes the process of
  gathering information from the process of making decisions.  The
  explicit representation of decisions in \cass\ allows a coherent
  approach to the problems of contingent planning, and provides a
  solid base for extensions such as the use of different
  decision-making procedures.

\end{abstract}

\section{Introduction}
\label{sect:intro}

Many plans that we use in our everyday lives specify ways of coping
with various problems that might arise during their execution.  In
other words, they incorporate {\em contingency plans\/}. The
contingencies involved in a plan are often made explicit when the plan
is communicated to another agent, \eg, ``try taking Western Avenue,
but if it's blocked use Ashland,'' or ``crank the lawnmower once or
twice, and if it still doesn't start jiggle the spark plug.''
So-called {\em classical planners\/}\footnote{This category includes
  systems such as \strips\ \cite{FN71}, {\sc hacker} \cite{Sus75},
  {\sc noah} \cite{Sac77} and {\sc molgen} \cite{Ste81a,Ste81b}.
  Recent classical planners include \tweak\ \cite{Cha87}, \snlp\ 
  \cite{McAR91} and \ucpop\ \cite{PW92}. The term is due to Wilkins
  \citeyear{Wil88}.} cannot construct plans of this sort, due
primarily to their reliance on three {\em perfect knowledge\/}
assumptions:
\begin{enumerate}
\item The planner has full knowledge of the initial conditions in 
which the plan will be executed, \eg, whether Western Avenue will be 
blocked;
\item All actions have fully predictable outcomes, \eg, cranking the 
lawnmower will definitely  either work or not work;
\item All change in the world occurs through actions performed by the 
planner, \eg, nobody else will use the car and empty its gas tank.
\end{enumerate}
Under these assumptions the world is totally {\em predictable\/}; there 
is no need for contingency plans. 
 
The perfect knowledge assumptions are an idealization of the planning
context that is intended to simplify the planning process.  They allow
the development of planning algorithms that have provable properties
such as completeness and correctness.  Unfortunately, there are few
domains in which they are realistic: mostly, the world is to some
extent unpredictable.  Relying on the perfect knowledge assumptions in
an unpredictable world may prove cost-effective if the planner's
uncertainty about the domain is small, or if the cost of recovering
from a failure is low.  In general, however, they may lead the planner
to forgo options that would have been available had potential problems
been anticipated in advance.  For example, on the assumption that the
weather will be sunny, as forecast, you may neglect to take along an
umbrella; if the forecast later turns out to be erroneous, it is then
impossible to use the umbrella to stay dry.  When the cost of
recovering from failure is high, failing to prepare for possible
problems in advance can be an expensive mistake.  In order to avoid
mistakes of this sort, an autonomous agent in a complex domain must be
able to make and execute contingency plans.

Recently, we and a number of other researchers have begun
investigating the possibility of relaxing the perfect knowledge
assumptions while staying close to the framework of classical planning
\cite{EHW92,PS92,PC93,DHW94b,GB94a}.  Our work is embodied in
\cass,\footnote{Cassandra was a Trojan prophet who was fated not to be
  believed when she accurately predicted future disasters. An earlier
  version of \cass\ was described in \cite{PC93}.} a contingency
planner whose plans have the following features:
\begin{itemize} 
\item They include specific decision steps to determine which of the
  possible courses of action to pursue;
\item Information gathering steps are distinct from decision-steps;
\item The circumstances in which it is {\em possible\/} to perform an
  action are distinguished from those in which it is {\em necessary\/}
  to perform it.
\end{itemize}

\subsection{Issues for a Contingency Planner}
\label{sect:issues-for-cont-planner}

A contingency planner must be able to construct plans that can be
expected to succeed despite unknown initial conditions and uncertain
outcomes of nondeterministic actions.  An effective contingency
planner must possess the following capabilities:
\begin{itemize}
\item It must be able to anticipate outcomes of nondeterministic
  actions;
\item It must be able to recognize when an uncertain outcome threatens
  the achievement of a goal;
\item It must be able to make contingency plans for all possible
  outcomes of the various sources of uncertainty that affect a given
  plan;
\item It must be able to schedule sensing actions that detect the
  occurrence of a particular contingency;
\item It must produce plans that can be executed correctly regardless
  of which contingency arises.
\end{itemize}

The design of \cass\ addresses these issues. However, there are
several issues that have not been addressed:
\begin{itemize}
\item We have not considered the problem of determining whether it is
  worth planning for a particular outcome;
\item \Cass\ is not a probabilistic planner: it cannot make use of any
  information about the likelihood or otherwise of any events;
\item We have ignored the possibility of interleaving planning and
  execution (but see Section~\ref{sect:interleave});
\item \Cass\ does not handle exogenous events;
\item The version of \Cass\ described here cannot solve Moore's bomb in
  the toilet problem \cite{McD87}: it can only find plans that involve
  deciding between courses of action that will succeed in different
  contingencies (but see Section~\ref{sect:fail-safe}).
\end{itemize}
\Cass\ assumes that all sources of uncertainty and all their possible
outcomes are known, and plans for all those that affect the
achievement of its goals. It is firmly in the classical planning mold:
its job is to construct plans that are guaranteed to achieve its
goals. It does not decide when to plan, or what to plan for.
Moreover, although we believe that \cass\ is sound and complete, it is
not systematic.  In addition, the current implementation is too slow
to be of practical use.

\subsection{A Note on Terminology}
\label{sect:terminology}

The word {\em conditional\/} is used in a variety of senses in the
literature.  We avoid its use altogether, except when describing the
work of other authors who use it in specialized senses: for example,
the {\em conditional actions\/} and {\em conditioning\/} of Peot and
Smith \citeyear{PS92}.  We use the term {\em contingency plan\/} to
refer to a plan that contains actions that may or may not actually be
executed, depending on the circumstances that hold at the time.  We
use the term {\em context-dependent\/} to refer to action effects that
depend on the context in which the action is performed.

\subsection{Outline}
\label{sect:outline}

In this paper we present \cass, describe its algorithm in some detail,
discuss the approach it takes to some important issues in contingency
planning, and show how it handles a variety of example problems.

We start by describing the structure of \cass's plans.
Section~\ref{sect:cass-plan-rep} describes how \cass\ represents
actions, including those with uncertain outcomes; explains the system
of labels that allows the determination of which of the alternative
courses of action in a contingency plan should be pursued; and
introduces the notion of explicit decision steps.

Section~\ref{sect:normplan} briefly describes the basic planning
algorithm in the absence of uncertainty.
Section~\ref{sect:contingplan} explains how the algorithm is extended
to handle uncertain outcomes of actions. In particular, the structure
of \cass's decisions is considered, as are the problems of ensuring
the soundness of the plan that is constructed.  The resulting
algorithm is described in detail and its properties are discussed in
Section~\ref{sect:alg}.

In Section~\ref{sect:uncertplanissues} we consider some issues that
arise in contingency planning. Section~\ref{sect:relwork} describes
related work on planning under uncertainty. Finally,
Section~\ref{sect:end} summarizes the contributions of this work and
discusses its limitations.


\section{\Cass's Plan Representation}
\label{sect:cass-plan-rep}

\Cass's representation of contingency plans has three major
components:
\begin{itemize}
\item An action representation that supports uncertain outcomes;
\item A plan schema;
\item A system of labels for keeping track of which elements of the
  plan are relevant in which contingencies.
\end{itemize}
These components are described in the remainder of this section.

\subsection{Action Representation}
\label{sect:action-rep}
\label{sect:strips-op}

\Cass's action representation is a modified form of the \strips\ 
operator \cite{FN71}. It consists of the {\em preconditions\/} for
executing an action and the {\em effects\/} that may become true as a
result of executing it, as in the standard \strips\ operator. The
syntax is the same as that used in \ucpop\ \cite{PW92}. As in \ucpop,
action effects are more complex than standard \strips\ effects: they
may have an associated set of {\em secondary preconditions\/}, which
govern the occurrence of that effect \cite{Ped88a,Ped91}.  Secondary
preconditions allow the representation of {\em context-dependent\/}
effects of actions, \ie, effects that depend upon the context in which
the action is executed.  The use of secondary preconditions is
critical to \cass's ability to represent uncertain effects, and hence
nondeterministic actions, as we discuss in
Section~\ref{sect:rep-uncert-eff}.

\begin{figure}
\begin{footnotesize}
\begindisplay
Action:        &|(make-selection ?machine ?selection)|\cr
\cr
Preconditions: &|(:and (money-entered ?machine)|\cr
               &|      (plugged-in ?machine))|\cr
               \cr
Effects:       &|(:when   (available ?machine ?selection)|&{\em secondary 
precondition}\cr
               &| :effect (:and (dispensed ?selection)  |\cr
               &|               (:not (money-entered ?machine))))|\cr
               &|(:when   (:not (available ?machine ?selection))|&{\em 
               secondary precondition}\cr
               &| :effect (another-selection-indicator-on ?machine))|\cr
\enddisplay
\end{footnotesize}
\caption{Simplified representation of operating a vending machine}
\label{fig:vending}     
\end{figure}
        
Figure~\ref{fig:vending} shows a simplified operator schema for the
action of making a selection from a soft-drink machine (the effects
describing how the ``make another selection'' indicator light is
turned off are omitted). The operator describes two possible effects
of carrying out the action: the effect of acquiring a soda, which
depends on the secondary precondition that a soda of the selected type
is available; and the effect of having the ``make another selection''
indicator light come on, which depends on the secondary precondition
that a soda of the selected type is {\em not\/} available.  Both
effects depend upon the preconditions that money has been entered into
the machine and that the machine is plugged in.

\subsubsection{Representing Uncertain Effects}
\label{sect:rep-uncert-eff}

An {\em uncertain effect\/} in \cass\ is a context-dependent effect
with an {\em unknown precondition\/}, \ie, a precondition the planner
can neither knowingly perceive nor deliberately affect.  For example,
a malfunctioning soft-drink machine may operate intermittently; if the
planner is aware of the intermittent functioning, but unaware of the
conditions that govern this behavior, then the correct functioning of
the device depends upon an unknown precondition. From the point of
view of the planner, the uncertain effect is nondeterministic; the
planner cannot tell in advance whether it will occur. Clearly, this
definition is fundamentally subjective: another planner with better
information might be able to specify precisely the conditions under
which the device functions properly, for example if it knew how the
internal mechanism of the machine worked. As another example, consider
what happens when a coin is tossed: in principle, given perfect
knowledge of all the forces and distances involved, it would be
possible to predict the outcome. In practice, such knowledge is
unavailable and the effect of the action is uncertain. In principle,
it would be possible to specify the conditions that would lead to the
coin landing tails up; in practice, these conditions are unknown.

It is interesting to note here that in some circumstances it might be
possible for a planner to learn to predict outcomes that it had
hitherto regarded as uncertain: for example, if it learned how the
soda machine worked. ``Unknown'' refers only to the current situation.
Our representation would facilitate such learning, which would simply
involve learning new secondary preconditions rather than a whole new
action representation.

Unknown preconditions play the same syntactic role as normal
preconditions within the operator schema; they are represented by
expressions formed using the pseudo-predicate \verb+:unknown+. An
effect that has a secondary precondition of this type will occur only
in certain contexts which cannot be distinguished by the planner from
the contexts in which it will not occur. 

Figure~\ref{fig:dodgysoda} depicts a simplified example of an operator
with an uncertain effect---it represents the action of operating a
soft-drink machine that intermittently fails to dispense a soda
despite being operated correctly.  This operator has two uncertain
effects, one in which the soda is dispensed, the other in which the
soda is not dispensed.

\begin{figure}
\begin{footnotesize}
\begindisplay
Action:        &|(enter-selection ?machine)|\cr
\cr
Preconditions: &|(:and (money-entered ?machine)|\cr
               &|      (plugged-in ?machine))|\cr
               \cr
Effects:       &|(:when (:and (available ?machine ?selection)|\cr
               &|             (:unknown ?ok T))|&\cr
               &| :effect (dispensed ?selection))|&{\em uncertain effect}\cr
               &|(:when (:and (available ?machine ?selection)|\cr
               &|             (:unknown ?ok F))|&\cr
               &| :effect (:not (dispensed ?selection)))|&{\em uncertain 
               effect}\cr
               &|(:when (available ?machine ?selection)|&\cr
               &| :effect (:not (money-entered ?machine)))|&\cr
               &|(:when (:not (available ?machine ?selection))|&\cr
               &| :effect (another-selection-indicator-on ?machine))|&\cr
\enddisplay
\end{footnotesize}                
\caption{Operating a faulty soft-drink machine}
\label{fig:dodgysoda}
\end{figure}

Clearly, the uncertainty with respect to both these effects stems from
a single underlying source, namely uncertainty about whether or not
the machine will malfunction.  In effect, the two unknown
preconditions in the operator represent alternative results of this
underlying source of uncertainty.  This relationship is reflected in
the two arguments to the \verb+:unknown+ pseudo-predicate, the first
of which designates the source of uncertainty with which it is
associated, and the second of which designates the particular outcome
of the uncertainty that it represents.  The possible contexts are
effectively partitioned into a set of equivalence classes, with each
context in the same class producing the same outcome of the
uncertainty. The outcome is then used to label the equivalence class.
A condition of the form \verb+(:unknown ?class outcome)+ will be true
if the actual context is in the class designated by \verb+outcome+.

Notice that each instantiation of the operator will introduce a new
source of uncertainty, which means that the first argument to the
unknown precondition must be represented as a variable in the operator
schema.  \Cass\ binds this variable to a unique identifier (\ie, a
skolem constant) when the operator is instantiated.

In \cass's representation it is assumed that different sources of
uncertainty are independent of each other.  No source of uncertainty
can be linked to uncertain outcomes in more than one operator, but a
single operator may introduce any number of sources of uncertainty,
each of which may have any number of outcomes. Each source of
uncertainty has an exhaustive set of mutually exclusive outcomes, each
with a unique name.

\subsubsection{Representing Other Sources of Uncertainty}
\label{sect:rep-src-uncert}

A key element of \cass's design is the use of a single format to
represent all sources of uncertainty that affect planning.  In
particular, all uncertainty is assumed to be manifest in uncertain
effects of planning operators, as outlined above.  Uncertainty about
initial conditions can be handled within this format by treating
initial conditions as though they were the effects of a phantom
``start step'' action. This treatment of initial conditions, which was
initially developed for reasons unrelated to the problem of
representing uncertain outcomes, is common to the \snlp\ family of
planners to which Cassandra belongs. 

\Cass's formulation ignores uncertainty that might stem from outside
interference during the execution of the agent's plans, except
inasmuch as it can be represented as incomplete knowledge of initial
conditions. This is, of course, a limitation of classical planners in
general; all change in the world is assumed to be caused directly by
the actions of the agent.

\subsection{Basic Plan Representation}
\label{sect:rep-plan}

\Cass's plan representation is an extension of that used in \ucpop\ 
\cite{PW92} and \snlp\ \cite{McAR91,BSW91}, which is in turn derived
from the representation used in \nonlin\ \cite{Tat77}. A plan is
represented as a schema with the following components:
\begin{itemize}
\item A set of {\em steps\/}; 
\item A set of anticipated {\em effects\/} of those steps;
\item A set of {\em links\/} relating effects to the steps that
  produce and consume them (a step consumes an effect when it requires
  that effect to achieve one of its preconditions).  Note that links
  in effect denote {\em protection intervals\/}, \ie, intervals over
  which particular conditions must remain true in order for the plan
  to work properly.
\item A set of {\em variable bindings\/} instantiating the operator
  schema;
\item A {\em partial ordering\/} on the steps;
\item A set of {\em open conditions\/}, \ie, unestablished goals;
\item A set of {\em unsafe links\/}, \ie, links the conditions of
  which could be falsified by other effects in the plan.
\end{itemize}
A plan is {\em complete\/} when it contains no open conditions and no
unsafe links.

\subsection{Representing Contingencies}
\label{sect:rep-conting}

A contingency plan is intended to achieve its goal regardless of which
of the foreseeable contingencies associated with it actually arise
during execution.  To construct a valid contingency plan, the planner
must be able to enumerate these contingencies.  The set of foreseeable
contingencies can be computed from the sources of uncertainty that are
associated with the plan.  In effect, a contingency is one possible
set of outcomes for all relevant sources of uncertainty.

\subsubsection{Contingency Labels}
\label{sect:conting-labels}

Keeping track of whether a plan achieves its goal in every contingency
is a somewhat complex process.  \Cass, like \cnlp, uses a system of
labels to accomplish the necessary bookkeeping \cite{PS92}.  Each
goal, step, and effect in \cass's plan is labeled to indicate the
contingencies in which that element participates:
\begin{itemize}
\item Goals are labeled to indicate the contingencies in which they
  must be achieved;
\item Effects are labeled to indicate the contingencies in which they
  are expected to occur, \ie, the contingencies in which the
  goals they satisfy arise;
\item Steps are labeled to indicate the contingencies in which they
  must be performed, \ie, the union of the contingencies in which
  any of their effects are expected to occur.
\end{itemize}
The preconditions of each effect become new goals, the labels of which
correspond to the labels on the effect that give rise to them.

In general, it is assumed that a particular step could be executed in
any contingency, albeit possibly to no purpose.  However, it is
sometimes necessary to rule a particular step out of a particular
contingency as a means of preventing its interference with the plan
for that contingency.  For example, consider a plan to achieve the
goal of having a coin heads up, the first action of which is to toss
the coin (see Section~\ref{sect:cassrule} for a detailed discussion of
this plan). In one contingency the coin lands heads up, and no further
actions are required. In another contingency, the coin lands tails up
and must be turned over in order for the goal to be achieved. It is
clear, however, that the turning over action must not be performed in
the first contingency: doing so would mean that the goal of having the
coin heads up is not achieved.  In \cass, ruling steps out is
accomplished by associating negative labels with plan steps to
indicate those contingencies in which the steps are not to be
executed. Peot and Smith \citeyear{PS92} call this process {\em
  conditioning\/}.

In addition, every step that depends, directly or indirectly, on a
particular outcome of a given source of uncertainty is ruled out of
every contingency that involves an alternative outcome of that source
of uncertainty.  We discuss the reason for this restriction in more
detail below.

\Cass's labeling system thus provides very clear guidance to the agent
executing the plan, which simply performs those steps whose positive
labels reflect the actual circumstances that hold  at execution.
Steps with neither positive nor negative labels involving the current
contingency will not affect the goals, but are not guaranteed to be
executable. In contrast, the agent executing a plan produced by \cnlp\ 
is guided by the reason labels attached to steps.  In \cnlp's plans,
an action need only be executed if at least one of the goals
represented in its reason labels is feasible.  The agent must
therefore have some method of deciding which of the top-level goals
are feasible.  We assume this can be done by comparing the context
labels of each top-level goal (which are labeled because they are
represented as dummy actions) with the circumstances that actually
hold.  \Cass's method is thus simpler: the agent simply uses the
positive labels of the plan steps instead of using the labels
attached to a step to indicate those goals whose context labels must
be analyzed.

The general principles of label propagation in \cass\ are:
\begin{itemize}
\item Positive labels, which denote that the plan element concerned
  contributes to goal achievement in that contingency, propagate along
  causal links from subgoals to the plan elements that establish them;
\item Negative labels, which denote that the plan element concerned
  would prevent goal achievement in that contingency, propagate along
  causal links from effects to the plan elements that they establish.
\end{itemize}

The details are given in Section~\ref{sect:labels}.

\subsubsection{Representing Decisions}
\label{sect:rep-decs}

Planning can be seen as the process of deciding what to do in advance
of when it is done \cite{Col87}.  The need for contingency plans
arises when the necessary decisions cannot be made in advance because
of missing information (see Section~\ref{sect:kgoals}).  If the
decisions cannot be made in advance, they must be made when the plan
is executed. The agent executing a contingency plan must at some point
decide which of the possible courses of action to pursue, in other
words which branch to take.

Previous work has in effect assumed that the agent will execute those
steps that are consistent with the contingency that actually holds
\cite{War76,PS92}.  However, the determination of which steps are
consistent cannot (by definition) be made in advance; in order to know
which contingency holds during execution, the agent executing the plan
must in general gather information on which the decision can be based.
To ensure a viable plan, the planner must be able to guarantee that
the steps required to gather information do not conflict with those
required to carry out the rest of the plan.  Therefore, the planner
must in general be able to include information gathering steps, as
well as any other steps that support decision making, in the plan it
is constructing.  \Cass\ achieves this by representing decisions
explicitly as plan steps.  The preconditions of these decision-steps
include goals to be in possession of information relevant to making
the decision; the scheduling of actions to obtain information is thus
handled by the normal planning process.

For instance, consider the contingency plan alluded to above: ``{\em
  try taking Western Avenue, but if it's blocked use Ashland\/}.''
During the execution of such a plan, the agent must at some point
decide which branch of the plan to execute.  The decision-step in this
case would have the precondition of knowing whether Western Avenue is
blocked or not, which would cause the planner to schedule an
information-gathering action to check the traffic status on Western.
This operation might in turn have the precondition of being on
Western, which can be achieved by traveling to the junction of Western
and Belmont. After the decision is taken, the agent can either take
Western up to Evanston or continue along Belmont to Ashland.

\begin{figure}
\begin{center}
\leavevmode
\epsfxsize=6in\epsfbox{decstep.ps}
\end{center}
        \caption{A plan that includes a decision-step}
        \protect\label{fig:decstep}
\end{figure}                                                        

Assuming the goal of the plan is to be in Evanston, the final plan
might be as depicted in Figure~\ref{fig:decstep}.  Note that control
flow after a decision is represented by heavy lines. Solid lines in
the diagram represent links, with the action at the tail of the link
achieving a precondition of the action at the head of the link.  In
this plan, the agent will take Western to Evanston in one contingency,
and will take Belmont to Ashland and then Ashland to Evanston in the
other.\footnote{Appendix~\ref{cass-plans} shows the plans that \cass\ 
  constructs for all the examples described in this paper.  This plan
  is in Section~\ref{plan:evanston}.}

Notice that in order to determine the appropriate precondition for a
given decision-step, the planner must have some way of determining
exactly what it will need to know in order to make the decision at
execution time.  This somewhat complex determination depends in part
on how the decision-making process is to be carried out.  In \cass,
decisions are modeled as the evaluation of a set of
condition-action rules of the form:
\begin{center}
\begin{tabular}{llll}
if & {\em condition\/}$_1$ & then & {\em contingency\/}$_1$  \\
if & {\em condition\/}$_2$ & then & {\em contingency\/}$_2$  \\
   & \ldots & &  \\
if & {\em condition\/}$_n$ & then & {\em contingency\/}$_n$  \\
\end{tabular}
\end{center}

Each possible outcome of a given uncertainty gives rise to a decision
rule; the condition of this decision-rule specifies a set of effects
that the agent should test in order to determine whether to execute
the contingency plan for that outcome.  For example, the
decision-rules for the driving plan example would look like this:
\begin{center}
\begin{tabular}{llll}
if & {\em Western Avenue is blocked\/} & then & {\em execute 
contingency using Ashland\/}\\
 if & {\em Western Avenue is not blocked\/} & then & {\em execute 
contingency using Western\/} \\
\end{tabular}
\end{center}

\noindent
\Cass's derivation of inference rules in decisions is explained in 
detail in Section~\ref{sect:contingplan}.
 
The preconditions for a decision-step are goals to know the truth
values of the conditions in the decision-rules: they are thus {\em
  knowledge goals\/} \cite{McCH69,Pry95} (see
Section~\ref{sect:kgoals}). These goals are treated in the same way as
are the preconditions of any other step.  \Cass\ thus requires no
other special provisions to allow the construction of
information-gathering plans.

The explicit representation of decision-steps provides a basis for
supporting alternative decision procedures.  While \cass's basic model
of the decision procedure is quite simple, more complex decision
procedures can be supported within the same framework (one such
procedure is described in Section~\ref{sect:fail-safe}). For example,
the model could be changed to a differential-diagnosis procedure.  The
representation of decision procedures as templates in the same way
that actions are represented as templates would allow the planner to
choose between alternative methods of making a decision in the same
way as it can choose between alternative methods of achieving a
subgoal.  An even better approach might be to formulate an explicit
goal to make a correct decision, and allow the system to construct a
plan to achieve that goal using inferential operators.  However, this
would in effect require that the goals for these operators be stated
in a meta-language describing the preconditions and results of
operators.  We have not yet addressed this possibility in any detail.

\Cass's separation of the gathering of information from the making of
decisions allows one information-gathering step to serve several
decisions.  This allows the flexible use of information-gathering
actions; there is no effective difference between such actions and any
other action that may appear in a plan.


\section{Planning Without Contingencies}
\label{sect:normplan}

In this section we briefly review the basic planning algorithm on
which \cass\ is based.  It follows closely that used in \ucpop\ 
\cite{PW92}, which is in turn based on \snlp\ \cite{McAR91}. The
principal difference between \ucpop\ and \snlp\ is the use of
secondary preconditions \cite<see>{CP92a}.  

\Cass\ does not attempt to construct a contingency plan until it
encounters an uncertainty.  Up until this point, it constructs a plan
in much the same manner as other planners in the \snlp\ family.  In
fact, if no uncertainty is ever introduced into the plan, \cass\ will
effectively function just as  \ucpop\  would under the same
circumstances.  Planning proceeds through the alternation of two
processes: {\em resolving open conditions\/} and {\em protecting
  unsafe links\/}.  Each of these processes involves a choice of
methods, and may therefore give rise to several alternative ways to
extend the current plan.  All possible extensions are constructed, and
a best-first search algorithm guides the planner's exploration of the
space of partial plans.

The initial plan consists of two steps: the {\em start\/} step, with
no preconditions and with the initial conditions as effects, and the
{\em goal\/} step, with the goal conditions as preconditions and with
no effects.  The planner attempts to modify its initial plan until it
is {\em complete\/}: \ie, until there are no open conditions and no
unsafe links.
 
\subsection{Resolving Open Conditions}
\label{sect:normopen}

The planning process is driven by the need to satisfy open conditions,
which are initially simply the input goals.  In the course of planning
to satisfy an open condition, new subgoals may be generated; these are
then added to the set of open conditions.  The planner can establish
an open condition in one of two ways: by introducing a new step into
the plan, or by reusing an existing step by making use of one of its
effects (see Figure~\ref{fig:open}).  The secondary preconditions of
the effect that establishes the condition become open conditions.  If
a new step is added, the preconditions of the step become open
conditions as well.  Finally, each time an open condition is
established, a link is added to the plan to protect the newly
established condition.

\begin{figure}
{\footnotesize \sf
  \begin{description}
  \item[New step] Add to the plan a new step that has an effect that
    will establish the open condition.  Add the step preconditions and
    the secondary preconditions of the effect as open conditions.  The
    open condition becomes a completed link.
  \item[Reuse step] Make the open condition into a complete link from
    an effect of an existing plan step.  Add the secondary
    preconditions of the effect as open conditions.
  \end{description}
}
\caption{Resolving open conditions}
\protect\label{fig:open}        
\end{figure}

One way of establishing a condition is simply to notice that the
condition is true in the initial state.  Because the initial
conditions are treated as the results of the {\em start\/} operator,
which is always a part of the plan, this method can be treated as
establishment by reusing an existing step; indeed, this simplification
is the motivation for representing the initial conditions in this way.

\subsection{Protecting Unsafe Links}
\label{sect:normunsafe}

Whenever an open condition is established, links in the plan may be
jeopardized either because a new step threatens an existing link, or
because a new link is threatened by an existing step.  The situations
in which a link is unsafe are shown in Figure~\ref{fig:unsafe}.  In
general, a link is considered unsafe if there is an effect in the plan
that could possibly interfere with the condition established by that
link.
\begin{figure}
  {\footnotesize \sf A link establishing the condition {\tt Cond} is
    {\em unsafe\/} if there is an effect {\tt Eff} in the plan (other
    than the effect {\tt SourceEff} that establishes {\tt Cond} and
    the (possible) effect {\tt GoalEff} that is either established or
    disabled by the link) with the following properties:
    \begin{description}   \setlength\itemindent{-2em}  
    \item[Unification] One of the postconditions in {\tt Eff} can
      possibly unify with either {\tt Cond} or its negation;
    \item[Ordering] The step that produces {\tt Eff} can, according to
      the partial order, occur both before the step that produces {\tt
        GoalEff} and after the step that produces {\tt SourceEff}.
    \end{description}
    An unsafe link may be resolved in one of three ways:
    \begin{description}     \setlength\itemindent{-2em}   
    \item[Ordering] Modify the ordering of the steps in the plan to
      ensure that the step producing {\tt Eff} occurs either before
      the step that produces {\tt SourceEff} or after the step that
      produces {\tt GoalEff};
    \item[Separation] Modify the variable bindings of the plan to
      ensure that the threatening effect {\tt Eff} cannot in fact
      unify with the threatened condition {\tt Cond};
    \item[Preservation] Introduce a new open condition in the plan to
      disable {\tt Eff}.  This new open condition is the negation of
      one of {\tt Eff}'s secondary preconditions.
  \end{description}
  }
\caption{Unsafe links}\label{fig:unsafe}
\end{figure}
        
There are three general methods of protecting a threatened link (see
Figure~\ref{fig:unsafe}).  First, {\em ordering\/} can be used to
constrain the threatening action to occur either before the beginning
or after the end of the threatened link.  Second, the threatening
effect and the threatened link can be {\em separated\/} by imposing
constraints on the variables involved so that the effect cannot be
unified with the established condition.  Third, the link can be {\em
  preserved\/} by generating a new subgoal to disable the effect that
threatens the link.


\section{Contingency Planning}
\label{sect:contingplan}

\Cass\ proceeds as described in the previous section until either the
plan is completed or an uncertainty is introduced.  This section
describes how uncertainties are introduced and how they are handled.

As an example of a plan involving an uncertainty, let us consider a
version of Moore's classic ``bomb in the toilet'' problem
\cite{McD87}, in which the goal is {\em bomb is disarmed\/}, and the
initial conditions are {\em bomb in package1\/} or {\em bomb in
  package2\/}.  The uncertainty in this case lies in the initial
conditions: depending on the outcome of the uncertainty, the {\em
  start\/} operator can either have the effect that the bomb is in
{\em package1\/} or the effect that the bomb is in {\em package2\/}.
 
\subsection{Contingencies}
\label{sect:contings}
\label{sect:uncertintro}

Uncertainty is introduced into a plan when an open condition in the
plan is achieved by an uncertain effect, \ie, an effect with an
unknown precondition.  In the bomb-in-the-toilet example, for
instance, \cass\ may achieve the condition {\em bomb is disarmed\/} by
selecting the \verb+dunk+ operator, which has the preconditions {\em
  the package is at the toilet\/}, and {\em the bomb is in the
  package\/}.  The condition {\em the bomb is in the package\/} can be
established by identifying it with {\em the bomb is in package1\/},
which is an effect of the {\em start\/} operator.  However, this
condition is uncertain, as can be determined by noting that it has an
unknown precondition.  \Cass\ will attempt to deal with this
uncertainty by introducing a new contingency (or new contingencies)
into the plan.  The state of the plan just after the introduction of
the uncertainty is illustrated in Figure~\ref{fig:uncertintro}.

\begin{figure}
\begin{center}
\leavevmode
\epsfbox{uncertintro.ps}
\end{center}
\caption{The introduction of uncertainty into a plan}
\label{fig:uncertintro}
\end{figure}

\subsubsection{Introducing Contingencies}
\label{sect:contingintro}

\Cass\ notices an uncertainty when its current plan becomes dependent
upon a particular outcome of that uncertainty through the use of an
uncertain effect, \ie, an effect with an unknown precondition that
specifies an outcome of that uncertainty.  The plan that \cass\ has
built up to that point is in effect a plan branch for that outcome.
Since branches must also be constructed for all other possible
outcomes of the uncertainty, \cass\ makes a copy of its overall goal
for each possible outcome of the uncertainty, each copy carrying a
label indicating the outcome of the uncertainty in which it must be
achieved. It thus effectively splits the plan into a set of branches,
one for each possible outcome of the uncertainty.\footnote{An
  alternative method would be to split the plan into two branches,
  regardless of the number of outcomes.  In this case, one branch
  would be associated with a given outcome of the uncertainty, while
  the other would be associated with all other possible outcomes of
  that uncertainty. This is effectively how \sensp\ operates
  \cite{EHW92}.}

In planning for these otherwise identical goals, \cass\ must make
certain that no element of the branch for the goal for one outcome
relies on a different outcome of the same uncertainty.  In other
words, no goal, nor any of its subgoals, may be achieved by any effect
that depends, directly or indirectly, on any outcome of the
uncertainty other than the one in the goal's label.  As described
above, \cass\ achieves this by using a system of {\em negative
  labels\/} indicating contingencies from which particular plan
elements must be excluded.
 
In the bomb-in-the-toilet example, when the plan is made dependent
upon the uncertain outcome {\em bomb in package1\/}, a new copy of the
top level goal {\em bomb is disarmed\/} is added to the set of open
conditions. The new copy is given a label indicating that it belongs
to contingency in which the bomb is in {\em package2\/}.\footnote{Note
  that we are describing the contingency in this way for clarity of
  exposition.  The actual label is constructed as described in
  Section~\ref{sect:conting-labels}.} The existing top level goal and
all its subgoals are labeled to indicate that they belong to the
contingency in which the bomb is in {\em package1\/}.  The effect {\em
  bomb in package1\/}, the action {\em dunk package1\/}, and all
effects of the action {\em dunk package1\/} are be labeled to indicate
that they cannot play a role in the contingency in which the bomb is
in {\em package2\/}.

Notice that the action {\em move package1\/}, although it plays a role
in the plan in the contingency in which the bomb is in {\em
  package1\/}, does not in fact depend upon the bomb being in {\em
  package1\/}.  It could in principle be made part of the plan for
disarming the bomb in the contingency in which the bomb is in {\em
  package2\/}, were it to prove useful for anything. This is indicated
by the fact that it has no negative label for for the {\em
  package2\/} contingency.

\begin{figure}\begin{center}
\leavevmode
\epsfxsize=6in\epsfbox{bomb.ps}
\end{center}
\caption{A contingency plan to disarm a bomb}\label{fig:dunkplan}
\end{figure}

When \cass\ attempts to achieve the new open condition {\em bomb
  is disarmed\/}, it may choose the \verb+dunk+ operator once again
(notice that it is prohibited from using any effects of the existing
\verb+dunk+ operator).  This new instance of the \verb+dunk+ operator
in turn gives rise to a subgoal to have the bomb be in the package
that is dunked.  This can only be achieved by identification with the
effect {\em bomb in package2\/}.  The plan thus constructed is
depicted in Figure~\ref{fig:dunkplan} (the decision-step has been
omitted for clarity) and is listed in Section~\ref{plan:bomb}.

\subsubsection{Uncertainties with Multiple Outcomes}
\label{sect:multoutcomes}

Although the algorithm we have described can deal with uncertainties
having any number of possible outcomes, we have so far discussed only
examples with two possible outcomes.  In fact, two-outcome
uncertainties suffice to describe the majority of problems that we
have considered.  Indeed, technically, any situation could be
described in terms of some number of two-outcome uncertainties.
However, it is not hard to think of situations that might naturally be
represented in terms of a source of uncertainty with more than two
outcomes.  For example, suppose the planner were interested in getting
hold of a particular object in a situation in which the object were
known to be in one of three places.  In such a case, the {\em start\/}
pseudo-operator would naturally be represented as having three
uncertain effects (one for each possible location of the object) all
associated with alternative outcomes of a single source of
uncertainty.  \Cass's plan for acquiring the object would then involve
three contingencies, one for each possible location.

\subsubsection{Multiple Sources of Uncertainty}
\label{sect:multsources}

\begin{figure}[tb]
\begin{center}
\leavevmode
\epsfxsize=6in\epsfbox{package.ps}
\end{center}
\caption{A partial plan to pick up a package}
\label{fig:packplan}
\end{figure}

\noindent A plan may involve two or more sources of uncertainty, in
which case the plan will have more than one set of branches.  For
example, suppose \cass\ is given the goal of picking up a package that
is at one of two locations, and that one of two cars will be available
for it to use.  If the uncertainty regarding the location of the
package is encountered first during the construction of the plan,
\cass\ will respond by building a plan involving two contingencies,
one for each location.  Call these contingencies $A$ and $B$ (see
Figure~\ref{fig:packplan} and Section~\ref{plan:fetch}).

At some point during the construction of the plan for contingency $A$,
\cass\ will encounter the uncertainty concerning which car will be
available and will make the current plan dependent upon one particular
outcome of that uncertainty.  Since this new source of uncertainty
arises in the context of planning for contingency $A$, contingency $A$
is in effect bifurcated into two contingencies: $A_1$, in which the
package is at location 1 and car 1 is available; and $A_2$, in which
the package is at location 1 and car 2 is available).  \Cass\ must
replace all existing contingency $A$ labels with contingency $A_1$
labels.  It must then introduce a new copy of the top-level goal
labeled with contingency $A_2$.

\begin{figure}[tb]
\begin{center}
\leavevmode
\epsfxsize=6in\epsfbox{package2.ps}
\end{center}
\caption{A plan with two sources of uncertainty}\label{fig:2uncert}
\end{figure}

Note that \cass\ must plan from scratch to achieve the top-level goal
in contingency $A_2$, in spite of the fact that it already has a
viable plan for the goal in contingency $A_1$. This is necessary
because situations may be encountered in which the only successful
plans involve using different methods to achieve the goal in the two
contingencies.  For example, extreme differences between the two cars
might necessitate different plans for driving them (\eg, in a more
detailed representation of the situation than we have presented here,
such differences might affect the routes on which the cars could be
driven or the places in which they could be parked).  \Cass\ must
therefore consider all possible ways to achieve the goal in
contingency $A_2$ in the search for a completion of the plan.  If the
particular car used does not in fact affect the driving plan, then one
path through the search space will result in isomorphic contingency
plans for $A_1$ and $A_2$ (see Figure~\ref{fig:2uncert} and
Section~\ref{plan:fetch2}).

The same reasoning applies to the extension of the plan to deal with
contingency $B$.  It cannot be assumed {\em a priori\/} that the plan
for contingency $B$ will in any way resemble the plan constructed for
contingency $A$.  An interesting consequence of this is that the
uncertainty concerning the availability of the cars does not
necessarily arise in a given plan for contingency $B$.  For example,
if the location of the package in contingency $B$ were close enough
that the agent could get there without using a car, the final plan
might have only three contingencies: $A_1$ (location 1 with car 1),
$A_2$ (location 1 with car 2), and $B$ (location 2, on foot).

\Cass\ may, of course, produce an extension of the plan in which a car
is to be used in contingency $B$ as well, in which case it will again
encounter the uncertainty associated with the location of the car, and
will proceed to bifurcate contingency $B$ just as was done previously
for contingency $A$.  In the limit, the plan will involve one
contingency for every member of the cross product of the possible
outcomes of the relevant uncertainties.  However, it is important to
note that not every member of the cross-product set must appear as a
contingency, since, as we have shown, some uncertainties may arise
only given particular outcomes of other uncertainties.

\subsection{Decision-steps}
\label{sect:decsteps}
\label{sect:adddec}

When \cass\ encounters a new source of uncertainty it adds a {\em
  decision-step\/} to the plan to represent the act of determining
which path through the plan should be followed during execution.  The
following ordering constraints are added to the plan at the same time:
\begin{itemize}
\item The decision-step must occur after the step with which the
  uncertainty is associated;
\item The decision-step must occur before any step with a precondition
  whose achievement depends on a particular outcome of the
  uncertainty.
\end{itemize}

\subsubsection{Formulating Decision-rules}
\label{sect:formrules}

For a decision-step to be operational, there must be an effective
procedure by which the agent executing the plan can determine which
decision to make.  In \cass, the action of deciding which contingency
to execute is modeled as the evaluation of a set of condition-action
rules of the form:
\begin{center}
\begin{tabular}{llll}
If & {\em condition\/}$_1$ & then & {\em contingency\/}$_1$  \\
If & {\em condition\/}$_2$ & then & {\em contingency\/}$_2$  \\
If & {\em condition\/}$_3$ & then & {\em contingency\/}$_3$  \\
   & \ldots && \\
\end{tabular}
\end{center}

\Cass\ annotates each decision-step in a plan with the set of rules
that will be used to make that decision.  The executing agent can then
make the decision by evaluating these rules when it comes to the
decision-step in the course of executing the plan.  In order to
evaluate a decision-rule, the executing agent must be able to
determine whether the rule's antecedent holds.  The preconditions for
the decision-step must thus include goals to know the current status
of each condition that appears as an antecedent of a rule in this
condition.  The preconditions of a decision-step become open
conditions in the plan in the same way as do the preconditions of any
other step.

As the intended effect of evaluating the decision-rules is to choose
the appropriate contingency given the outcome of a particular
uncertainty, the conditions should be diagnostic of particular
outcomes of the uncertainty.  The executing agent cannot, of course,
directly determine the outcome of an uncertainty, so it must infer it
from the presence or absence of effects that depend upon that outcome.

The most straightforward approach to constructing the antecedent
conditions of a decision-rule would be to analyze the plan operators
to identify all the effects that could be expected to result from a
given outcome of the uncertainty, and make the condition be the
conjunction of these effects.  However, this turns out to be overkill.
In fact, it is only necessary to check for those effects of a given
outcome of an uncertainty {\em that are actually used to establish
  preconditions in the contingency associated with that outcome\/}. In
other words, it is necessary only to verify that the contingency plan
can, in fact, succeed. This has the interesting consequence that the
executing agent might, in principle, end up selecting a contingency
plan even though the outcome of the uncertainty were not the one with
which that plan was associated.  Notice that this would not cause a
problem in the execution of the plan, since it would only occur if all
the conditions for the plan's success were met.  In fact, as we shall
see, \cass\ depends on this effect in certain circumstances.

The antecedent condition of the decision-rule is thus a conjunction of
all the direct effects of a particular outcome that are used to
establish preconditions in the contingency plan for that outcome.
Decision-rules are constructed incrementally as the plan is
elaborated.  We discuss \cass's construction of these rules in more
detail in Section~\ref{sect:cassrule} below.  The approach we have
used in formulating \cass's decision-rules is consistent with
Morgenstern's observation that an agent can execute a plan if it can
``make sure'' that all the events in the plan are executable
\cite{Mor87}.

\subsubsection{Adding a Decision-rule in our Example}
\label{sect:addrule}

In the bomb-in-the-toilet example, \cass\ will introduce a
decision-step to determine whether or not the bomb is in {\em
  package1\/}.  As the uncertainty is in the initial conditions, the
decision will be constrained to occur after the {\em start\/} step.
It must also occur before either of the \verb+dunk+ actions, since
these depend upon particular outcomes of the uncertainty.  The
\verb+decide+ step will have a precondition to know whether the bomb
is in {\em package1\/}.  If there are actions available that would
allow it to determine this---X-raying the box, for example---\cass\ 
will achieve this precondition with one of those actions, and decide
on that basis which branch of the plan to execute.

\subsubsection{How \Cass\ Constructs Decision-rules}
\label{sect:cassrule}

At the point in the planning process at which \cass\ constructs a
decision-rule, only one precondition in the plan is known to depend
upon a particular outcome of the uncertainty that gave rise to the
decision: namely, the one that led to \cass\ discovering the
uncertainty in the first place.  The decision-rule set that \cass\ 
initially builds thus looks like this:
\begin{center}
\begin{tabular}{llll}
If & {\em effect\/}$_1$ & then & {\em contingency\/}$_1$ \\
If & T & then & {\em contingency\/}$_2$ \\
If & T & then & {\em contingency\/}$_3$ \\
\ldots & & & \\
\end{tabular}
\end{center}
During the construction of the plan, \cass\ must modify this initial
rule set each time an effect depending directly on the source of
uncertainty is used to establish an open condition in the plan.  In
particular, \cass\ must determine the contingency in which that open
condition resides, and conjoin the effect with the existing antecedent
of the decision-rule for that contingency.

\begin{figure}
\begin{footnotesize}
\begindisplay
Action:        &|(toss-coin ?coin)| & \cr
\cr
Preconditions: &|(holding ?agent ?coin)| & \cr
\cr
Effects:       &|(:when (:unknown ?U H)| &\cr
               &| :effect (:and (flat ?coin)|&{\em uncertain effect} \cr
               &|               (heads ?coin)))|& \cr
               &|(:when (:unknown ?U T)|&\cr
               &| :effect (:and (flat ?coin)|&  {\em uncertain effect}\cr
               &|               (tails ?coin)))|& \cr
               &|(:when (:unknown ?U E) |&\cr
               &| :effect (on-edge ?coin)))|&  {\em uncertain effect} \cr
\enddisplay                
\end{footnotesize}
\caption{Representing the action of tossing a coin}\label{fig:cointoss}
\end{figure}

Consider, for example, what happens when a coin is tossed.  We might
say that in theory there are three possible outcomes of this action:
the coin can land flat with heads up; flat with tails up; or on its
edge (Figure~\ref{fig:cointoss}).  Suppose \cass\ is given a goal to
have the coin be flat.  This can be established by using the {\em
  flat-heads\/} effect of tossing it.  Since this is an uncertain
effect, \cass\ introduces two new contingencies into the plan, one for
the outcome in which the coin lands tails up, and another for the
outcome in which it lands on its edge.

The introduction of these contingencies mandates the introduction of a
decision-step whose initial rule set looks like
this:\footnote{Assuming that {\tt ?U}, the variable representing the
  source of uncertainty, is instantiated to {\tt U1}.}
\begin{center}
\begin{tabular}{llllll}
If & \verb+(flat coin)+ & then & \verb+[U1: H]+ & {\em rule for heads up} 
\\
If & \verb+T+ & then & \verb+[U1: T]+ & {\em rule for tails up} \\
If & \verb+T+ & then & \verb+[U1: E]+ & {\em rule for edge} \\
\end{tabular}
\end{center}
At the same time, a new open condition \verb+(know-if (flat coin))+ is
introduced as a precondition of the decision-step, and new goal
conditions are introduced that must be achieved in contingencies
\verb+[U1: T]+ and \verb+[U1: E]+.  Cassandra next establishes the
goal condition in contingency \verb+[U1: T]+ using the {\em
  flat-tails\/} effect of the \verb+toss+ step. The decision-rules
associated with the {\em tails up\/} contingency are thus modified as
follows:
\begin{center}
\begin{tabular}{llllll}
If & \verb+(flat coin)+ & then & \verb+[U1: H]+ & {\em rule for heads up} 
\\
If & \verb+(flat coin)+ & then & \verb+[U1: T]+ & {\em rule for tails up} \\
If & \verb+T+ & then & \verb+[U1: E]+ & {\em rule for edge} \\
\end{tabular}
\end{center}

Finally, the goal condition is established in contingency 
\verb+[U1:E]+ by introducing a new step, \verb+tip+, into the plan.  A
precondition of the \verb+tip+ step is that the coin be on its edge,
which is established by the {\em on-edge\/} effect of the \verb+toss+
action.  Since this effect depends directly upon the uncertainty
\verb+U1+, the decision-rule for the {\em edge\/} contingency is
modified to include this condition:
\begin{center}
\begin{tabular}{llllll}
If & \verb+(flat coin)+ & then & \verb+[U1: H]+ & {\em rule for heads up} 
\\
If & \verb+(flat coin)+ & then & \verb+[U1: T]+ & {\em rule for tails up} \\
If & \verb+(on-edge coin)+ & then & \verb+[U1: E]+ & {\em rule for edge} \\
\end{tabular}
\end{center}

Since the plan is complete, this is the final set of decision-rules
(see Section~\ref{plan:cointoss}).  Notice that these rules do not
discriminate the \verb+heads-up+ outcome from the \verb+tails-up+
outcome.  In fact, either outcome will do, so there is no reason to
make this discrimination.  Which plan is executed in either of these
conditions depends solely upon the order in which the agent that is
executing the plan chooses to evaluate the decision-rules.\footnote{An
  obvious extension to \cass\ would be the construction of a
  post-processor that spots decision-rules that do not discriminate
  between particular sets of outcomes, and prunes the plan to remove
  superfluous contingencies.  Note that it cannot be determined until
  the plan is complete whether such a condition pertains.}

A somewhat more complex problem arises if we give \cass\ the goal of
having the coin be \verb+flat+ and \verb+heads-up+.  In this case both
effects can be established using the \verb+toss+ action.  This will
again lead to the introduction of two new contingencies into the plan,
one for when the coin lands tails up, and one for when it lands on
edge.  Although \cass\ could establish \verb+(flat coin)+ in the
\verb+tails-up+ case, it would fail to complete the plan, because the
coin would not be \verb+heads-up+.  However, the \verb+turn-over+
action can be used, leaving the coin \verb+flat+ and \verb+heads-up+
given that it was \verb+flat+ and \verb+tails-up+ to begin with.  At
this point the decision-rules are as follows:
\begin{center}
\begin{tabular}{llllll}
If & \verb+(and (flat coin) (heads-up coin))+ & then & \verb+[U1: H]+ & 
{\em rule for heads up}\\
If & \verb+(and (flat coin) (tails-up coin))+ & then & \verb+[U1: T]+ & 
{\em rule for tails up} \\
If & \verb+T+ & then & \verb+[U1: E]+ & {\em rule for edge} \\
\end{tabular}
\end{center}

\Cass\ must then plan for the goal in the outcome in which the coin
lands on its edge.  Both these effects can be established as a result
of the \verb+tip+ action.  However, the result \verb+heads-up+ is an
uncertain effect of the \verb+tip+ action, since the coin might just
as easily land tails up.  \Cass\ must therefore add another new
contingency for when the coin lands tails up after being tipped.  In
this instance, the goal can be established by using the
\verb+turn-over+ action, and the \verb+tails-up+ precondition of this
action can be established by the uncertain result of the \verb+tip+
action.  The final decision-rule set for the first decision is as
follows:
\begin{center}
\begin{tabular}{llllll}
If & \verb+(and (flat coin) (heads-up coin))+ & then & \verb+[U1: H]+ & 
{\em rule for heads up} \\
If & \verb+(and (flat coin) (tails-up coin))+ & then & \verb+[U1: T]+ & 
{\em rule for tails up} \\
If & \verb+(on-edge coin)+ & then & \verb+[U1: E]+ & {\em rule for edge} \\
\end{tabular}
\end{center}

If the \verb+on-edge+ contingency is pursued, another decision,
stemming from the uncertain result of \verb+tip+, must be added to the
plan.  If we name the second source of uncertainty \verb+U2+, the
rules for this decision are:
\begin{center}
\begin{tabular}{llll}
If & \verb+(heads-up coin)+ & then & \verb+[U2: H]+ \\
If & \verb+(tails-up coin)+ & then & \verb+[U2: T]+ \\
\end{tabular}
\end{center}

\begin{figure}
\begin{center}
\leavevmode
\epsfysize=3in\epsfbox{cointoss.ps}
\end{center}
\caption{A plan with two decisions}\label{fig:2decplan}
\end{figure}

The plan is depicted in Figure~\ref{fig:2decplan} and shown in 
Section~\ref{plan:cointoss2}.

\subsubsection{Decision-rules and Unsafe Links}
\label{sect:unsaferules}

The fact that \cass\ allows decision-rules that do not fully
differentiate between outcomes of an uncertainty raises a somewhat
subtle issue.  Consider the partial plan for opening a locked door
shown in Figure~\ref{fig:doorplan}.  The action of kicking a door has,
let us say, two possible outcomes, one in which the lock is broken and
one in which the agent's foot is broken.  A plan for the contingency
in which the lock is broken is simply to open the door.  A plan for
the alternative contingency is to pick the lock and then open the
door.

\begin{figure}
\begin{center}
\leavevmode
\epsfxsize=6in\epsfbox{door.ps}
\end{center}
\caption{Opening a door}\label{fig:doorplan}
\end{figure}

Since the second plan does not depend causally on any outcome of the
uncertainty (the agent's foot does not have to be broken in order for
it to pick the lock and open the door), the decision-rules based on
the above discussion would be:
\begin{center}
\begin{tabular}{lllll}
If & \verb+(lock-broken)+ & then & \verb+[O: L]+ & {\em rule for lock broken}\\
If & \verb+T+ & then & \verb+[O: F]+ & {\em rule for foot broken}\\
\end{tabular}
\end{center}

Notice that in this case the \verb+pick+ action depends on the lock
being intact, while the \verb+kick+ action may have the effect that
the lock is no longer intact.  In other words, the \verb+kick+ action
potentially clobbers the precondition of \verb+pick+.  However, the
planner can arguably ignore this clobbering, because the two actions
belong to different contingencies.  This is valid, though, only if the
structure of the decision-rules guarantees that the agent will not
choose to execute the contingency involving \verb+pick+ when the
outcome of \verb+kick+ is that the lock is broken.  The decision-rules
above clearly do not enforce this.  The solution in such a case is to
augment the decision-rule for the contingency in which the lock is not
broken to test whether the lock is in fact intact.  This results in
the following decision-rules (the plan is shown in
Section~\ref{plan:door}):
\begin{center}
\begin{tabular}{lllll}
If & \verb+(lock-broken)+ & then & \verb+[O: L]+ & {\em rule for lock broken}\\
If & \verb+(not (lock-broken))+ & then & \verb+[O: F]+ & {\em rule for foot broken}\\
\end{tabular}
\end{center}

\Cass\ augments decision-rules in this way whenever a direct effect of
an uncertainty could clobber a link in a different contingency.


\section{A Contingency Planning Algorithm}
\label{sect:alg}

In this section we give the details of \cass's algorithm. Its
properties are considered in Section~\ref{sect:uncertplanissues}.

\subsection{Plan Elements}
\label{sect:planelts}

A plan consists of steps, effects, links (some of which may be
unsafe), open conditions, variable bindings, a partial ordering, and
contingency labels.  A plan is {\em complete\/} when there are no open
conditions and no unsafe links.

\subsubsection{Steps and Effects}
\label{sect:steps}

A plan {\em step\/} {\tt Step} represents an action.  It may have
enabling {\em preconditions}.  It has at least one {\em effect\/} {\tt
  Eff}.  It is the instantiation of an operator.
        
A plan step may be a {\em decision-step\/} {\tt Decide}.  A
decision-step has enabling preconditions of the form {\tt (know-if
  Cond)} for a condition {\tt Cond}.  {\tt Decide} also has a set of
{\em decision-rules}.

An {\em effect\/} {\tt Eff} represents some results of an action.  It
is attached to a step {\tt Step}, representing that action.  It may
have secondary preconditions.  It has at least one postcondition {\tt
  Cond}, a condition that becomes true as the result of executing {\tt
  Step} when the secondary preconditions hold.

\subsubsection{Links and Open Conditions}
\label{sect:links}

A {\em link\/} represents a causal dependency in the plan, specifying
how a condition {\tt Cond} is established by an effect {\tt Eff},
which has {\tt Cond} as a postcondition.  {\tt Eff} has secondary
preconditions {\tt SecPre} and is a result of step {\tt Step}.  The
link supports the step {\tt SupStep} or effect {\tt SupEff} through
the condition {\tt Cond} which is one of:
\begin{itemize}
\item An enabling precondition of {\tt SupStep};
\item A secondary precondition of an effect {\tt SupEff} that is a
  result of {\tt SupStep};
\item The negation of a secondary precondition of an effect that is a
  result of {\tt SupStep}, thus preserving a link.
\end{itemize}

A link is {\em unsafe\/} in a contingency {\tt Conting} in which it is
required if there is an effect {\tt ClobberEff} with postcondition
{\tt ClobberCond} (the clobbering condition) resulting from step {\tt
  ClobberStep} such that:
\begin{itemize}
\item {\em Either\/}  {\tt ClobberCond} can unify with
  {\tt Cond}; \\ {\em Or\/}  {\tt Cond} is of the form
  {\tt (know-if KnowCond)} and {\tt ClobberCond} can unify with {\tt
    KnowCond};
\item Step {\tt ClobberStep} can occur between steps {\tt Step} and
  {\tt SupStep};
\item Effect {\tt ClobberEff} can occur in contingency {\tt Conting}.
\end{itemize}
        
An {\em open condition\/} (an unachieved subgoal) is represented in
\cass\ as an incomplete link, \ie, a link missing the information
about the effect that establishes it.

\subsubsection{Bindings and Orderings}
\label{sect:binds}

Plan {\em bindings\/} (codesignation constraints) specify the
relationships between variables and constants. The following
relationships are possible:
\begin{itemize}
\item Two variables may codesignate;
\item A variable may designate a constant;
\item A variable may be constrained not to designate a constant;
\item Two variables may constrained not to codesignate.
\end{itemize}

An {\em ordering\/} constrains the order of two steps with respect to
each other, so that step $S_1$ must precede step $S_2$ ($S_1 < S_2$).

\subsubsection{Contingency Labels}
\label{sect:labels}

Every step, effect and open condition in a partial plan has two sets
of {\em contingency labels\/} attached to it.  In the interests of
brevity, we also refer to the labels of a link; in this case, we mean
the labels of the step or effect that the link establishes.

Each contingency label has two parts: a symbol representing the source
of uncertainty, and a symbol representing a possible outcome of that
source of uncertainty.  {\em Positive contingency labels\/} denote the
circumstances in which a plan element must or will necessarily occur;
{\em negative contingency labels\/} denote the circumstances in which
a plan element cannot or must not occur.

Contingency labels must be propagated through the plan.  In general,
positive contingency labels are propagated from goals to the effects
that establish them, while negative contingency labels are propagated
from steps to the effects that result from them.  The details are as
follows:
\begin{itemize}
\item A step inherits the positive labels of the effects that result
  from it;
\item A step inherits the negative labels of the effects that
  establish its enabling preconditions;
\item An effect inherits the positive labels of the steps whose
  enabling preconditions it establishes;
\item An effect inherits the positive labels of the effects whose
  secondary preconditions it establishes;
\item An effect inherits the negative labels of the step from which it
  results;
\item An effect inherits the negative labels of the effects that
  establish its secondary preconditions;
\item An open condition inherits the positive labels of the step or
  effect that it is required to establish.
\end{itemize}
\Cass's system of label propagation is based on that of \cnlp\ but is
more complex. Indeed, it is rather more complex than we would like.
This complexity is mandated by the need to deal with operators that
involve multiple context-dependent effects, which has the result that
a step and its effects do not necessarily share the same labels.

\subsection{Algorithm}
\label{sect:algdetail}

\begin{figure}[tb]
{\footnotesize \sf
  {\em Plan\/}({\tt PartList})
  \begin{enumerate}
    \setlength\itemsep{0pt}
    \setlength\parsep{0pt}
  \item Choose a partial plan {\tt Plan} from {\tt PartList};
  \item If {\tt Plan} is complete, then finish;
  \item If there is an unsafe link {\tt Unsafe}:
    \begin{itemize}
      \setlength\itemsep{0pt}
      \setlength\parsep{0pt}
    \item[] Do {\em resolve\/}({\tt Plan}, {\tt Unsafe}) and add the
      resulting plans to {\tt PartList};
    \item[] Return to step 1;
    \end{itemize}
  \item If there is an open condition {\tt Open}:
    \begin{itemize}
      \setlength\itemsep{0pt}
      \setlength\parsep{0pt}
    \item[] Do {\em establish\/}({\tt Plan}, {\tt Open}) and add the
      resulting plans to {\tt PartList};
    \item[] Return to step 1.
    \end{itemize}
  \end{enumerate}
  }
\caption{Top level planning algorithm}\label{fig:planalg}
\end{figure}

\noindent The planning process starts by constructing a partial plan
consisting of two steps:
\begin{itemize} 
\item An initial step with no preconditions and with the initial
  conditions as its effects;
\item A goal step with no effects and with the goal conditions as its
  enabling preconditions.
\end{itemize}
This plan is added to the (initially empty) list of partial plans {\tt
  PartList}.  Planning then proceeds as shown in
Figure~\ref{fig:planalg}.

It now remains to describe how threats to unsafe links are resolved
and how open conditions are established.

\begin{figure}[tb]
  {\footnotesize \sf
    {\em Resolve\/}({\tt Plan}, {\tt Unsafe})
    \begin{enumerate}
      \setlength\itemsep{0pt}
      \setlength\parsep{0pt}
    \item Initialize a list {\tt NewPlans};
    \item If the unification of the clobbering condition {\tt
        ClobberCond} with the condition {\tt Cond} established by the
      link {\tt Unsafe} involves adding codesignation constraints to
      the bindings of {\tt Plan}:
      \begin{itemize}
        \setlength\itemsep{0pt}
        \setlength\parsep{0pt}
      \item[] Make each possible modification to the bindings of {\tt
          Plan} that ensures that {\tt ClobberCond} cannot unify with
        {\tt Cond};
      \item[] Add each resulting partial plan to {\tt NewPlans};
      \end{itemize}
    \item If the clobbering step {\tt ClobberStep} can precede the
      step {\tt Step} that establishes {\tt Unsafe}:
      \begin{itemize}
        \setlength\itemsep{0pt}
        \setlength\parsep{0pt}
      \item[] Add an ordering to ensure that {\tt ClobberStep}
        precedes {\tt Step};
      \item[] Add the resulting partial plan to {\tt NewPlans};
      \end{itemize}
    \item If the step {\tt SupStep} supported by {\tt Unsafe} can
      precede {\tt ClobberStep}:
      \begin{itemize}
        \setlength\itemsep{0pt}
        \setlength\parsep{0pt}
      \item[] Add an ordering to ensure that {\tt SupStep} precedes
        {\tt ClobberStep};
      \item[] Add the resulting partial plan to {\tt NewPlans};
      \end{itemize}
    \item Prevent the clobbering effect {\tt ClobberEff} from
      occurring in each contingency {\tt Conting} in which the link
      {\tt Unsafe} is unsafe:
      \begin{itemize}
        \setlength\itemsep{0pt}
        \setlength\parsep{0pt}
        \item[] Do one of:
          \begin{enumerate}
            \setlength\itemsep{0pt}
            \setlength\parsep{0pt}
          \item Add the negation of the secondary preconditions of
            {\tt ClobberEff} as an open condition with positive
            contingency label {\tt Conting};
          \item Add {\tt Conting} to the negative contingency labels
            of {\tt ClobberStep};
          \item Add {\tt Conting} to the negative contingency labels
            of the effect {\tt SupEff} or step {\tt SupStep} that {\tt
              Unsafe} supports;
          \end{enumerate}
        \item[] If appropriate modify the relevant decision-rule as
          discussed in Section~\ref{sect:unsaferules};
        \item[] Add orderings to ensure that step {\tt ClobberStep}
          occurs between steps {\tt Step} and {\tt SupStep};
        \item[] Propagate labels as appropriate;
        \item[] Add each resulting partial plan to {\tt NewPlans};
        \end{itemize}
      \item Return {\tt NewPlans}.
      \end{enumerate}
    }
\caption{Resolving threats}\label{fig:threats}
\end{figure}

\subsubsection{Resolving Threats to Unsafe Links}
\label{sect:algunsafe}

Figure~\ref{fig:threats} shows how threats are resolved.  The methods
shown in steps 2, 3, and 4 are standard methods found in \snlp\ and
\ucpop; they are often termed {\em separation}, {\em demotion}, and
{\em promotion\/} respectively.  We say that the methods in step 5
{\em disable\/} the threat.  The methods in steps 5a and 5b ensure that
the threatening effect does not occur in a given contingency.  The
method in step 5a is a modification of a standard method found in
\ucpop\ and other planners that use secondary preconditions.
Essentially, the idea is to prevent an effect from occurring by
ensuring that the context in which it occurs cannot hold.  The method
in 5b prevents an effect from occurring in a contingency by forbidding
the execution of the step that produces it.  The method in step 5c
notes that the established step or effect cannot occur in a given
contingency.  If any of these techniques result in inconsistent
labeling of any plan element (so that, for example, it cannot occur in
every contingency in which it is required) the resulting partial plan
is abandoned, as it represents a dead end in the search space.

\subsubsection{Establishing Open Conditions}
\label{sect:estopens}

Figure~\ref{fig:estopen} shows the procedure used.  Procedure {\em
      EstablishPre\/} shows the methods of adding a new step and reusing
an existing step; they are essentially the methods used in \ucpop\ 
extended to reflect the need to check and propagate contingency
labels.

Procedure {\em EstablishUnk\/} shows methods of adding a new decision
and reusing an existing decision that are specific to \cass.  The
issues involved were discussed in Section~\ref{sect:decsteps}.

\begin{figure}
{\footnotesize \sf 
  {\em Establish\/}({\tt Plan}, {\tt Open})
  \begin{enumerate}
    \setlength\itemsep{0pt}
    \setlength\parsep{0pt}
  \item If the open condition is not of type \verb+:unknown+ do {\em
      EstablishPre\/}({\tt Plan}, {\tt Open}) and return the resulting
    list of plans;
  \item If the open condition is of type \verb+:unknown+ with source
    of uncertainty {\tt Uncertainty} and outcome {\tt Outcome} do {\em
      EstablishUnk\/}({\tt Plan}, {\tt Open}, {\tt Uncertainty}, {\tt
      Outcome}) and return the resulting list of plans.
  \end{enumerate}

  \vspace{3ex}
  {\em EstablishPre\/}({\tt Plan}, {\tt Open})
  \begin{enumerate} 
    \setlength\itemsep{0pt}
    \setlength\parsep{0pt}
  \item Initialize list {\tt NewPlans};
  \item For each effect {\tt Eff} resulting from a step {\tt Step} in
    {\tt Plan} \\ If {\tt Eff} can occur in every contingency in which
    {\tt Open} must be established \\ and if {\tt Eff} can precede the
    step {\tt SupStep} that {\tt Open} is required to support \\ and
    if there is a postcondition {\tt EffCond} of {\tt Eff} that can
    unify with condition {\tt Cond} that {\tt Open} is required to
    establish:
    \begin{itemize}
      \setlength\itemsep{0pt}
      \setlength\parsep{0pt}
      \vspace{-1ex}  % \topsep appears to have no effect
     \item[] Complete the link {\tt Open} by using {\tt Eff} as the
      establishing effect;
    \item[] Add the resulting partial plan to {\tt NewPlans};
    \end{itemize}
  \item For each operator with an effect {\tt Eff} with a
    postcondition {\tt EffCond} that can unify with {\tt Cond}:
    \begin{itemize}
      \setlength\itemsep{0pt} 
      \setlength\parsep{0pt}
      \vspace{-1ex}  % \topsep appears to have no effect
     \item[] Instantiate a new step {\tt Step};
    \item[] Complete the link {\tt Open} by using {\tt Eff} as the
      establishing effect;
    \item[] Add the enabling preconditions of {\tt Step} as open
      conditions;
    \item[] Add the resulting partial plan to {\tt NewPlans};
    \end{itemize}
  \item For each plan in {\tt NewPlans}:
    \begin{itemize}
      \setlength\itemsep{0pt} 
      \setlength\parsep{0pt}
      \vspace{-1ex}  % \topsep appears to have no effect
     \item[] Add an ordering to ensure that {\tt Step} precedes {\tt
        SupStep};
    \item[] Add the bindings necessary to ensure that {\tt EffCond}
      unifies with {\tt Cond};
    \item[] Add the secondary preconditions {\tt SecPre} of {\tt Eff}
      as open conditions;
    \item[] Propagate labels as appropriate;
    \end{itemize}
    \item Return {\tt NewPlans}.
  \end{enumerate}

  \vspace{3ex}
  {\em EstablishUnk\/}({\tt Plan}, {\tt Open}, {\tt Uncertainty}, {\tt
    Outcome})
  \begin{enumerate} 
  \item Initialize list {\tt NewCPlans};
  \item If {\tt Uncertainty} is a new source of uncertainty in the
    plan:
    \begin{itemize}
      \setlength\itemsep{0pt}
      \setlength\parsep{0pt}
      \vspace{-1ex}  % \topsep appears to have no effect
     \item[] Add a new decision-step {\tt DecStep} for uncertainty {\tt
        Uncertainty};
    \item[] Add new top-level goals as open conditions with the
      appropriate labels;
    \item[] Add the resulting partial plan to {\tt NewCPlans};
    \end{itemize}
  \item If {\tt Uncertainty} is an existing source of uncertainty
    in the plan:
    \begin{itemize}
      \setlength\itemsep{0pt}
      \setlength\parsep{0pt}
      \vspace{-1ex}  % \topsep appears to have no effect
     \item[] Find an existing decision-step {\tt DecStep} for
      uncertainty {\tt Uncertainty};
    \item[] Add the resulting partial plan to {\tt NewCPlans};
    \end{itemize}
  \item For each plan in {\tt NewCPlans}:    
    \begin{itemize}
      \setlength\itemsep{0pt} \setlength\parsep{0pt}
      \vspace{-1ex}  % \topsep appears to have no effect
    \item[] Modify the decision-rule in {\tt DecStep} for {\tt
        Outcome} to include {\tt Cond} as an antecedent;
    \item[] Add \verb+(know-if Cond)+ as an open condition required to
      establish {\tt DecStep};
    \item[] Add orderings to ensure that {\tt DecStep} precedes {\tt
        SupStep};
    \item[] Propagate labels as appropriate;
    \end{itemize}
  \item   Return {\tt NewCPlans}.
  \end{enumerate}

  }
\caption{Establishing open conditions}\label{fig:estopen}
\end{figure}



 
\section{Issues in Contingency Planning}
\label{sect:uncertplanissues}

\Cass\ is a partial order planner directly descended from \ucpop,
which is sound, complete, and systematic---all plans produced by
\ucpop\ are guaranteed to achieve their goals, if there is a plan then
\ucpop\ will find it, and \ucpop\ never revisits a partial plan. In
this section we discuss these properties and related issues in the
context of contingency planning.

\subsection{Soundness}
\label{sect:sound}

\Ucpop's soundness depends on the perfect knowledge assumptions 
discussed in Section~\ref{sect:intro}. In particular, \ucpop's plans
are sound if the initial conditions are fully specified, and if all
possible effects of actions are specified in the operators that
represent them. If no uncertainties are involved in the plan, \cass\ 
is equivalent to \ucpop\ and therefore constructs sound plans.

If uncertainties are involved in the plan, it can no longer be assumed
that the initial conditions and effects of actions are fully
specified.  Indeed, the uncertainties arise {\em because\/} these
assumptions are violated.  However, the assumptions can be adapted to
account for the presence of uncertainty: it would be possible, for
example, to insist that all possible initial conditions and action
effects are specified.  In \cass's representation, this means that
every source of uncertainty must be specified through the use of
unknown secondary preconditions, and every possible outcome of each
source of uncertainty must be specified.

We conjecture that \cass\ is sound under these conditions. The proof
would follow because the procedure for adding in new goals whenever a
new source of uncertainty is encountered ensures that every goal is
achieved in every possible outcome of the uncertainty.

\subsection{Completeness}
\label{sect:complete}

We conjecture that \cass\ is complete in the limited sense that, if
there is a sound plan of the form that it can construct, then \cass\ 
will find it. We believe that this is a simple extension of \ucpop's
completeness.  If there are no uncertainties involved, \cass\ will
always find a plan in the same way as \ucpop.  The introduction of a
source of uncertainty into a plan leads to the addition of new
contingent goals.  \Cass\ will find a plan for each of these new goals
in the appropriate contingency.  Thus, if the goal can indeed be
achieved in every contingency, \cass\ will find a plan that achieves
it, as long as there is a way of determining which contingency
holds.

For example, the plan to disarm a bomb that we described in
Section~\ref{sect:contings} relies on there being a method of
determining which package the bomb is in.  In McDermott's presentation
of this example, the two packages are indistinguishable, and the point
of the example is to illustrate that there is nonetheless a plan that
will succeed in disarming the bomb, namely, dunking both packages
\cite{McD87}.  The algorithm described in the previous section cannot
find a plan in this situation because it is impossible to achieve the
preconditions of the decision-step that determines which package to
dunk.  In Section~\ref{sect:fail-safe} we discuss this example in more
detail and describe a simple extension to \cass\ that allows the
correct plan (to dunk both packages) to be found.

\Ucpop's completeness, like its soundness, depends on the perfect
knowledge assumptions we discussed in Section~\ref{sect:intro}.
\Cass's completeness depends on three extensions to these assumptions:
\begin{itemize}
\item All sources of uncertainty are specified;
\item The specified outcomes are exhaustive;
\item There are actions available that allow the determination of the
  outcome of any uncertainty, even if only indirectly.
\end{itemize}

Unfortunately, these conditions are necessary but not sufficient.
\Cass\ can only find plans if the actions that it uses to determine
the contingency do not interfere with the achievement of the goal. For
instance, there might be a dropping action available that would
detonate any bomb inside the package that was dropped. This is
certainly an action that allows the determination of the outcome of
the uncertainty, but there is no sound plan that makes use of it.

In order to have a useful notion of \cass's completeness, we must
therefore specify the form of the plans that it can construct. This
problem is common to proving the completeness of any planner: for
example, we do not claim that \snlp, say, is incomplete because it
cannot find a plan for the bomb-in-the-toilet problem. We say instead
that there is no valid plan of the form that it can construct. It is
fairly simple to specify the form of the plans that \snlp\ can
construct: they consist of partially ordered sequences of steps, all
of which are to be executed.  The introduction of contingencies makes
the description of \cass's plans rather more complex; we have yet to
formalize a description, but are actively working in that direction.
Informally, \cass\ can only construct plans that for every source of
uncertainty include a step to decide on one of the relevant plan
branches.  The extension of \cass\ that solves the bomb-in-the-toilet
problem can do so because it can construct plans that do not meet this
criterion.

\subsection{Systematicity}
\label{sect:system}

\Ucpop\ is systematic: it will never visit the same partial plan twice
while searching.  \Cass, as described in this paper, is not
systematic; it may visit some partial plans in the search space more
than once.  Consider again the plan to disarm a bomb that we discussed
in Section~\ref{sect:contings}.  In this plan, there are two different
ways of establishing the goal to disarm the bomb: by dunking {\em
  package1\/}, and by dunking {\em package2\/}.  \Cass\ can initially
choose either way of establishing the goal, leading in each case to
the introduction of a contingency and the necessity of replanning to
achieve the goal in the other contingency.  Both search paths arrive
at the same final plan, so the search is not systematic.

\Cass\ could be made systematic by insisting on handling the
contingencies only in a certain order, the search path that uses the
other order being treated as a dead end.  However, this extension has
not been added as there is currently some debate as to the
desirability of systematicity.  For example, Langley \citeyear{Lan92}
argues that a non-systematic search method, iterative sampling, is
often better than a systematic method, depth-first search, for
problems which have multiple solutions and deep solution paths.  Peot
and Smith \citeyear{PS92} observe that the performance of a
non-systematic version of \snlp\ was better than that of the original
systematic version. They ascribed this behavior to the fact that
exploring duplicate plans consumed less overhead than did ensuring
systematicity.


\subsection{Knowledge Goals}\label{sect:kgoals}

An agent executing contingency plans must be able to acquire
information about the actual state of the world so that it can
determine which of the possible courses of action to pursue.  A system
that constructs contingency plans must be able to plan for this
information acquisition: in general, the acquisition process may be
arbitrarily complex \cite{PC91}.

An early and influential discussion of goals to possess knowledge
about the world was that by McCarthy and Hayes \citeyear{McCH69}.
Since then, various theories have been developed to account for them
\cite<\eg,>{Moo85a,Haa86,Mor87,Ste95}. The common thread in all this
work is that knowledge goals arise from the need to specify the
actions that are to be performed; in other words, from the need to
make actions {\em operational\/}.  Work in this area has on the whole
concentrated on being able to describe and represent knowledge goals,
and has largely ignored the issues involved in building planners that
construct plans containing them.

The structure of \cass\ is based on the notion that knowledge goals
arise out of the need to make decisions as to the actions to be
performed \cite{Pry95}. In our view, planning is the process of
deciding what to do in advance of when it is done \cite{Col87}.  In a
world conforming to the perfect knowledge assumptions of classical
planning this is always possible because the world is totally
predictable, and plans therefore need contain no knowledge goals.
However, when those assumptions are relaxed it may not be possible to
make all decisions in advance if the information necessary to make
them is not available to the planner.  The information may be
unavailable either because of the planner's limited knowledge of the
world or because the events that will nondeterministically cause the
conditions that affect the decisions have not yet occurred.  In both
cases it may be possible for the planner to determine that a decision
must be made even though it cannot at that time actually make it.  In
this case the planner can {\em defer\/} the decision: plan to make it
in the future, when the necessary information will be available.  Part
of the plan is then to acquire the information; the plan thus contains
knowledge goals.

\Cass's use of ``unknown'' preconditions to indicate nondeterminism is
thus a crucial part of its mechanism. In \cass, knowledge goals arise
as the result of deferring decisions. These deferred decisions are
represented explicitly in its plans, and themselves arise directly
from the incompleteness of \cass's knowledge of the world, whether
through the effects of nondeterministic actions or through
incompletely specified initial conditions. Both these forms of
uncertainty are handled in the same way: once \cass\ has recognized
the need to defer a decision, the {\em reason\/} for its deferral is
not important except inasmuch as it results from incomplete knowledge
of the world.

The view of knowledge goals as arising from deferred decisions is
basically consistent with the view that they are needed in order to
make actions operational, but differs from the traditional view in
that knowledge goals are not directly preconditions of physical
actions, but are instead preconditions of actions that make decisions.
For example, McCarthy and Hayes consider the problem of a combination
safe: it is commonly held that the action of opening the safe has a
precondition to know the combination.  In \cass, however, the goal of
knowing the combination would arise as a subgoal of deciding which
plan branch to follow, where there would be a branch for each possible
combination.\footnote{This raises the obvious question as to whether
  planning in advance for every possibility is a sensible thing to do.
  See Section~\ref{sect:interleave} for a discussion of this issue.}
The branches would arise because of \cass's incomplete knowledge of
the world: the initial conditions in which the plan will be executed
are not fully specified.

\Cass\ uses a variant of the syntactic approach proposed by Haas
\citeyear{Haa86} to represent knowledge goals, limiting knowledge
goals to the form {\em know-if(fact)\/}. This turns out to be adequate
if, as we assume, all possible outcomes of any given uncertainty are
known.  In general, the representation used by \cass, based on the
\strips\ representation of add and delete lists, is less powerful than
the logics proposed by either Morgenstern or Haas.

\subsection{Miscellaneous Issues in Contingency Planning}
\label{sect:contplanissues}

\Cass's approach raises a number of questions concerning the desired
behavior of a contingency planner, many of which do not have obvious
answers.  In this section we briefly consider a few of the issues
raised.

\subsubsection{Dependence on Outcomes and Superfluous Contingencies}

The fact that a contingency plan assumes a particular outcome of an
uncertainty means only that it cannot depend upon a different outcome
of that uncertainty.  \Cass\ does not enforce any constraint that the
plan must causally depend upon the outcome that it assumes.  For
instance, in the example described in Section~\ref{sect:rep-decs}, the
plan to take Ashland does not actually depend on Western being
blocked; it could be executed successfully regardless of the level of
traffic on Western.

This observation raises an interesting question: If a plan for a
contingency turns out not to depend on any outcome of the uncertainty
that gave rise to it, would this not obviate the need for plans for
alternative contingencies? For instance, in our example, it might seem
sensible to execute the plan to use Ashland regardless of whether
Western is blocked.  It might thus seem that the planner should edit
the plan in some way so as to eliminate apparently superfluous
contingencies.  However, it can easily be shown that a version of the
plan that does not involve dependence on any outcome of the
uncertainty will be generated elsewhere in the search space.  In the
example, this would mean that the planner would in fact consider a
plan that simply involved taking Ashland.  If the search heuristics
penalize plans involving contingencies appropriately this other plan
should be preferred to the contingency plan, all other things being
equal.

\subsubsection{One-sided Contingencies}

The preceding discussion notwithstanding, a plan involving no
contingencies is not always superior to a plan involving a
contingency.  This is why a planner might in fact construct a plan
like the Western/Ashland one.  To take a more clear-cut example,
suppose Pat needs \$50 to bet on a horse.  She might try to borrow the
\$50 from Chris, but the outcome of this action is uncertain---Chris
might refuse.  Alternatively, she could rob a convenience store.
While the robbery plan would (we shall stipulate) involve no
uncertainties, it is a bad plan for other reasons.  It would be better
to first try to borrow \$50 from Chris, and then, if that fails, rob
the convenience store.  \Cass\ could generate this plan.  In order to
make it prefer the plan to the contingency-free alternative, however,
its search metric would have to take into account the estimated costs
of various actions, and to perform something akin to an expected value
computation.  \cite<See, for example,>[for discussions of
decision-theoretic measures applied to planning.]{FS77,HH92} In order
to execute the plan properly, it would also be necessary for it to
have some way of knowing that the borrowing plan should be preferred
to the robbery plan if it were possible to execute either of them.

\subsubsection{Identical Branches}

It is possible that a single plan could work just as well for several
different outcomes of an uncertainty.  For instance, suppose the
action of asking Chris for \$50 has three possible outcomes: either
Pat gets the money and Chris is happy (at having had the opportunity
to do a favor); or Pat gets the money and Chris is unhappy (at having
been obliged to do a favor); or Pat does not get the money at all.  If
Pat constructs a plan in which she tries to borrow \$50 from Chris to
bet on a horse, then, assuming that this plan does not depend upon
Chris's happiness (which it might, for example, if Pat needed to get a
ride to the track from Chris), the plan will work for either the ``get
money + Chris happy'' outcome or the ``get money + Chris unhappy''
outcome.

\Cass\ could find such a plan, but  would in effect have to find it
twice---once for each outcome of the uncertainty---and it would still
require a decision-step to discriminate between those outcomes.  This
is inefficient in two ways: the extra search time required to find
what is essentially the same plan twice is wasted, and effort is put
into making an unnecessary decision.  We are looking into ways to
avoid the former problem.  The latter could be solved by a
post-processor that would ``merge'' identical contingency plans, but
we have not implemented this technique.

\subsubsection{Branch Merging}\label{sect:merging}

It is possible to construct a plan in which branches split and then
reunite.  For instance, consider the Western/Ashland plan once again.
The context in which the goal to get to Evanston arises might be an
obligation to deliver a toast at a dinner to be held in an Evanston
restaurant.  The contingency due to uncertainty about traffic on
Western Avenue would in this case seem to affect only the portion of
the plan concerned with getting to Evanston; it probably has little
bearing on the wording of the toast, the choice of wine, and so on.
The most natural way to frame this plan might thus be to assume that
regardless of which contingency is carried out, the planner will
eventually arrive at a certain location in Evanston, and from that
point a single plan will be developed to achieve the final goal.

Constructing the plan in this way would result in a more compact plan
description, and might thus reduce the effort needed to construct the
plan by avoiding, for example, the construction of multiple copies of
the same subplan.  We are considering methods by which branch
re-merging might be achieved, but all the methods we have considered
so far seem to complicate the planning process considerably.

\subsubsection{Fail-safe Planning}\label{sect:fail-safe}

As we discussed in Section~\ref{sect:complete}, \cass's operation
relies on being able to determine, even if only indirectly, the
outcome of any uncertainty.  However, this may not always be possible,
and it is not a necessary precondition for the existence of a viable
plan.  In the bomb-in-the-toilet problem, for example, there is a
valid plan that \cass\ cannot find: to dunk both packages.

This suggests a method for constructing plans in the face of
uncertainty when the outcome of the uncertainty cannot be
determined---what one might call {\em fail-safe\/} plans.  Whenever
uncertainty arises it is in principle possible that there might be a
non-contingent plan that would achieve the goal whatever the outcome
of the uncertainty.  To find such a plan, the planner must construct a
version of the contingency plan in which all actions in the
contingency branches arising from the uncertainty will be executed
unconditionally.  \Cass\ has been extended in just such a way, by
adding a new type of decision, one to execute all branches in parallel
\cite{CP95}.  A plan containing such a decision is only sound if none
of the actions that must be performed to achieve the goal in one
contingency interfere with any of the actions that must be performed
in any other contingency, and the ability to perform the actions is
independent of the outcome of the uncertainty. These conditions
clearly hold for the bomb-in-the-toilet problem.

\Cass\ can reason about this possibility because its labeling scheme
distinguishes those actions that must not be performed in a given
contingency from those that need not be performed. It is possible to
execute all branches only if the actions in each branch may be
performed (but need not) in all the other branches.

When a parallel decision is added to the plan in the extended version
of \cass, new goals are added in the usual way but the labeling is
handled differently. The branches are not separated, so that \cass\ 
can no longer reason that the causal links in one branch will not be
affected by actions in another branch.

\subsubsection{Contingent Failure}

\Cass\ can produce a plan only if it is possible to achieve the goal
of the plan in all possible contingencies.  Often, however, the goal
cannot in fact be achieved in some outcome of the underlying
uncertainty.  Consider, for instance, Peot and Smith's example of
trying to get to a ski resort by car, when the only road leading to
the resort is either clear or blocked by snowdrifts \cite{PS92}.  If
the road is clear, then the goal can be achieved, but if it is
blocked, all plans are doomed to failure.

No planner can be expected to recognize the impossibility of achieving
a goal in the general case \cite{Cha87}.  However,  a possible
approach is suggested by Peot and Smith.  We could introduce an
alternative method of resolving open goal conditions: simply assume
that the goal in question fails.

This is an undesirable method of resolving open goal conditions if the
subgoal is in fact achievable, so in theory plans involving contingent
failure should be considered only after the planner has failed to find
a plan in which all goals are achieved. This is sometimes possible,
but in general the problem of determining whether there is a
successful plan is undecidable. There may always be partial plans that
do not involve goal failure but that cannot be completed. For example,
as a partial plan is modified it may become more and more complex, the
resolution of each open condition involving the introduction of more
unachieved subgoals. In this case, plans involving contingent failure
will never be considered unless they are ranked above some plans that
do not involve contingent failure. In order to be generally useful,
the approach must be weakened: instead of considering goal failure
only after all other avenues of attack have failed, apply a high fixed
penalty to plans involving failed goals. The aim would be to fix the
penalty high enough that contingent failure would only apply in
genuine cases of goals being unachievable.  However, this would of
necessity be a heuristic approach and completeness would be lost.


\section{Related Work}
\label{sect:relwork}

\Cass\ is constructed using \ucpop\ \cite{PW92} as a platform.
\Ucpop\ is a partial order planner that handles actions with
context-dependent effects and universally quantified preconditions and
effects.  \Ucpop\ is an extension of \snlp\ \cite{BSW91,McAR91} that
uses a subset of Pednault's {\sc adl} representation
\cite{Ped89}.

An early contingency planner was Warren's {\sc warplan-c}
\citeyear{War76}.  Contingency planning was more or less abandoned
between the mid seventies and the early nineties,\footnote{Neither
  \noah\ \cite{Sac77} nor Interplan \cite{Tat75} explicitly addressed
  issues of uncertainty, although both tackled problems involving it
  \cite{CP95}.} until \sensp\ \cite{EHW92} and \cnlp\ \cite{PS92}.
Both \sensp\ and \cnlp\ are members of the \snlp\ family: \sensp\ is,
like \cass, based on \ucpop, and \cnlp\ is based directly on \snlp.
\Cburidan\ \cite{DHW94b,DHW94a}, a probabilistic contingency planner,
is based on the probabilistic planner \buridan\ \cite{KHW95} (which is
itself based on \snlp) and on \cnlp.  \Plinth\ \cite{GB94a,GB94b} is a
total-order planner based on McDermott's \pedestal\ \citeyear{McD91c},
and is strongly influenced by \cnlp\ in its treatment of contingency
plans.

{\sc Warplan-c}, unlike the other planners considered here, did not
use a \strips-based action representation, but was based on predicate
calculus.  It could handle actions that had just two possible
outcomes, and did not merge the resulting plan branches.

\Sensp\ also differs from the other planners considered here. It
represents uncertainty through the use of {\em run-time\/} variables,
distinguished from ordinary variables by being treated as constants
whose values are not yet known.  In \sensp\ plan branches arise from
the introduction of information-gathering steps that bind the run-time
variables.  \Sensp\ handles plan branching by constructing separate
plans that each achieve the goal in a particular contingency.  It then
combines the separate plans at a later stage, keeping the branches
totally separate.  \Sensp\ thus considers contingency branches
separately, rather than in parallel.  Actions that achieve knowledge
goals may not have preconditions in \sensp: this restriction is
required in order to maintain completeness.

Not surprisingly, \cass, \cnlp, and \cburidan, and to a lesser extent
\plinth, are in many respects very similar.  All except \plinth\ use
the basic \snlp\ algorithm, and all use extended \strips\ 
representations. \Cass\ differs from \cnlp\ and \plinth\ principally
in the way that uncertainty is represented
(Section~\ref{sect:uncert-rep}); this difference has important
implications for the handling of knowledge goals
(Section~\ref{sect:other-kgoals}).  The principal difference between
\cass\ and \cburidan\ lies in the latter's use of probabilities
(Section~\ref{sect:probplan}).

Contingency planning is only one approach to the problem of planning
under uncertainty. The aim of contingency planning is to construct a
single plan that will succeed in all circumstances: it is essentially
an extension of classical planning.  There are other approaches to
planning under uncertainty that do not share this aim: probabilistic
planners aim to construct plans that have a high probability of
succeeding (Section~\ref{sect:probplan}); systems that interleave
planning and execution do not attempt to plan fully in advance
(Section~\ref{sect:interleave}). In both these approaches it is
possible to address the problem of determining which contingencies
should be planned for, which is not currently possible in \cass. A
third approach is that of reactive planning, in which behavior is
controlled by a set of reaction rules (Section~\ref{sect:react}).

\subsection{The Representation of Uncertainty}\label{sect:uncert-rep}

In \cnlp\ and \plinth, uncertainty is represented through a
combination of uncertain outcomes of nondeterministic actions and the
effects of observing those outcomes.  A three-valued logic is used: a
postcondition of an action may be {\em true\/}, {\em false\/}, or {\em
  unknown\/}.  For example, the action of tossing a coin might have
the postcondition \verb+unk(side-up ?x)+.  Special {\em conditional
  actions\/}, each of which has an unknown precondition and several
mutually exclusive sets of postconditions, are then used to observe
the results of the nondeterministic actions.  In the example, the
operator to observe the results of tossing a coin might have the
precondition \verb+unk(side-up ?x)+ with three possible outcomes:
\verb+(side-up heads)+, \verb+(side-up tails)+, and 
\verb+(side-up edge)+.

\Cnlp\  thus spreads the representation of uncertainty over
both the action whose execution produces the uncertainty and the
action that observes the result.  A consequence of this is that \cnlp\ 
cannot use the same observation action to observe the results of
different actions.  For example, it would require different
actions to observe the results of tossing a coin (which has three
possible outcomes) and tipping a coin that had landed on its edge
(which has two possible outcomes). 

In \plinth, the notion of a conditional action is extended to cover
any action (not only observation actions) that has nondeterministic
effects {\em on the planner's world model\/}. For example, in an
image-processing domain an operator to remove noise from an image may
or may not succeed. However, its outcome is evident as soon as it has
been applied, and no special observation action is required.
 
In \cnlp\ and \plinth, information-gathering actions are included in a
plan whenever an action with uncertain effects occurs.  This is
necessary because the uncertainty is actually represented in the
information-gathering action rather than in the action that actually
produces the uncertainty. Knowledge goals are thus not represented
explicitly in these two systems.

The representation used in \cnlp\ and \plinth\ arises out of the
desire to use a ``single model of the world, representing the
planner's state of knowledge, rather than a more complex formalization
including both epistemic and ground formulas'' \cite{GB94b}.  An
operator therefore represents only the effects that the execution of
the underlying action has on the planner's knowledge of the world, and
not the effects that it has on the actual state of the world.  It is,
of course, important to represent how actions affect the planner's
world model, but we believe that it is also important to represent how
they affect the world.  After all, the purpose of reasoning about
actions is to achieve goals in the world, not just in the planner's
world model.  In particular, after the execution of a nondeterministic
action its actual effects, although they may indeed be unknown to the
planner, have occurred and cannot now be altered.  \Cass's
representation reflects this: indeed, \cass\ can reason about the
possible effects without scheduling observation actions.  This means
that an extension of \cass\ can, for example, solve the original
bomb-in-the-toilet problem, in which there are no possible actions
that will resolve the uncertainty as to which package contains the
bomb: the bomb's state is not represented in the planner's world model
at any stage between the beginning, when it is known to be armed, and
the end, when both packages have been dunked and it is known to be
safe.

A further implication of this method of representing uncertainty is
the difficulty of representing actions whose uncertain effects cannot
be determined through the execution of a single action. Consider, for
example, a malfunctioning soda machine that has one indicator that
lights when it cannot make change, and another that lights when it has
run out of the product requested. Suppoe that, when it is functioning
correctly, these two indicators will not light simultaneously. If it
malfunctions, it must be kicked to make it work. Observing either
light on its own is not enough to determine which uncertain effect
(working properly or malfunctioning) has occurred.


\subsection{Knowledge Goals}\label{sect:other-kgoals}

The method of representing uncertainty in \cnlp\ and \plinth\ has
important implications for how knowledge goals are handled in their
plans.  

The acquisition of information is a planning task like any other
\cite{PC91,PC92a,Pry94}.  In general, the sequence of actions required
to achieve a given knowledge goal may be arbitrarily complex.  For
example, an action to observe a tossed coin might require that the
observer is in the appropriate location; in other cases, there might
be several different possible methods of information gathering, some
involving perception, some involving reasoning, and some a
combination.  A contingency planner, some of whose plans will
necessarily involve the achievement of knowledge goals, must therefore
be able to plan fully generally for information gathering.

The confusion between the source of uncertainty and the observation of
uncertain results limits the ways in which knowledge goals can be
achieved in \cnlp\ and \plinth: they must be achieved through the
special observation actions that specify the uncertain outcomes.  This
is a result of their representation in terms of the planner's world
model, which means that they do not represent the effects of actions
(except to flag them as unknown) until the planner has observed them
(or otherwise incorporated them into its world model).  In their
discussion of this issue Goldman and Boddy \citeyear{GB94b} explicitly
exclude knowledge goals from consideration. As they point out,
planning under uncertainty requires that a distinction be made between
the actual state of the world and the planner's knowledge of it.  In
order to plan effectively for knowledge goals, both must be
represented.  This is done in \cass\ by separating the representation
of uncertainty from the representation of information-gathering. If an
effect results deterministically from an action, \cass\ reasons that
there is no need to observe it, and it forms part of the world model.
An uncertain effect, on the other hand, is not incorporated
unconditionally into \cass's world model; it is noted as being
possibly true, and (if necessary) \cass\ sets up a subgoal to
determine whether it is indeed true.

\Sensp, which uses the \uwl\ representation for goals and actions, has
three different kinds of precondition that can be used to represent
information goals either alone or in combination \cite{EHW92}. As well as
\verb+satisfy+ preconditions, which may be achieved through actions or
through observation, \uwl\ has \verb+hands-off+ preconditions
indicating that the value of propositions must not be changed in order
to achieve the subgoal, and \verb+find-out+ preconditions. The latter
are in some ways similar to preconditions for \verb+know-if+
propositions in Cassandra. A precondition such as 
\verb+(find-out (P . v))+ tells the planner to ascertain whether or not
\verb+P+ has truth value \verb+v+. Under certain circumstances this
type of precondition may be achieved by an action that changes the
value of \verb+P+. Knowledge goals may thus be represented by
\verb+find-out+ preconditions or \verb+satisfy+ preconditions (often
used in conjunction with  \verb+hands-off+ preconditions). Etzioni et
al.  argue that knowledge goals should only be  achieved through
actions that change the value of the proposition in question when that
change is required for another purpose in the plan. We believe that
this is an unnecessary limitation, and that in some circumstances
enforcement actions may be the best way of achieving knowledge
goals. 

\subsection{Probabilistic and Decision-theoretic Planning}
\label{sect:probplan}

When constructing plans, \cass\ recognizes the presence of uncertainty
but not its extent. Other planners specifically address issues of
probability: for example, \buridan\ constructs plans whose probability
of achieving the goal is above a given threshold \cite{KHW95}; and 
\Drips\ uses the utility of the different possible outcome of various
plans to choose the one with the highest expected utility \cite{HS94}.
Neither \buridan\ nor \drips\ constructs contingency plans, \ie, plans
that involve alternative courses of action to be performed in
different circumstances.  \Cburidan, which is based on \buridan,
constructs contingency plans that are likely to succeed
\cite{DHW94a,DHW94b}. It represents an extension of \cnlp\ in the
direction of decision-theoretic planning.

Probabilistic planners use information about the probabilities of the
possible uncertain outcomes to construct plans that are likely to
succeed.  \Cass, on the other hand, cannot use such information and
constructs plans that are guaranteed to succeed. Probabilistic
planning, because it relies on explicit probabilities, is both more
and less powerful than the deterministic contingency planning
performed by \cass.  \Cass\ cannot use information about probabilities
but it can construct plans in circumstances in which no such
information is available.  For example, in order to solve the
bomb-in-the-toilet problem, \cburidan\ would have to have some
information, or at least make an assumption, about the probabilities
of the bomb being in each package.  Whatever assumptions are made
might turn out to be wrong, thus invalidating the basis of the plan.

We believe that it would be possible to build a probabilistic planner
using ideas from both \cburidan\ and \cass.  Because of the explicit
representation of decisions in \cass, such a planner would provide an
excellent opportunity for investigating the use of different decision
procedures.  \Cburidan\ relies on having full knowledge of all the
probabilities at the time that it constructs its plans.  This
knowledge, like any other, may not be available until the plan is
executed.  It would be relatively simple to add decision procedures to
\cass's decision representation that depend on information about
probabilities, \eg, to follow a particular course of action if the
probability of a given outcome exceeds a certain value. The
introduction of such decision procedures might, of course, result in
the introduction of knowledge goals to determine probabilities,
possibly leading eventually to a system that would construct plans to
perform empirical studies to determine probabilities.

A problem associated with contingency planning is that of branch
merging, \ie, the determination of whether two steps in separate
branches can be treated as the same step.  \Cburidan\ performs full
merging: this is an effect of the probabilistic algorithm on which it
is based.  Adding this capability to \cass\ is an area of future work.
A major problem encountered when considering branch merging is how to
identify the variables in the different branches with each other:
\cburidan's representations do not include variables, so the problem
does not arise.  This may cause difficulties in the adaptation of
\cburidan's merging mechanism for \cass's use.

An advantage of combining probabilistic planning and contingency
planning is the resulting ability to judge whether it is worth
planning for a given contingency. One of the limitations of \cass\ in
its present form is the requirement that every possible contingency be
planned for. In complex situations this makes the resulting plans
cumbersome. Moreover, \cass's performance deteriorates with the number
of distinct branches in the plan. The cost of determining that the
presence of a particular branch would not significantly change the
probability of the plan's success might well be much less than the
cost of constructing that branch. This is an interesting issue to be
considered in the future.

\subsection{Interleaving Planning and Execution}
\label{sect:interleave}

Although \cass's plans may include sensing actions, with the course of
action that will actually be executed depending on the results of
those actions, \cass\ does not interleave planning with execution.
Plans are fully specified before they are executed. In some
circumstances this is clearly very inefficient. Consider, for example,
how \cass\ constructs a plan to open a combination safe (see
Section~\ref{sect:kgoals}). It requires prior knowledge of all
possible combinations, and then constructs a plan with a branch for
each combination.

An obvious alternative would be to construct a plan that was fully
specified up to the information-gathering step, execute the plan to
that stage and, once the information has been gathered, construct the
rest of the plan.\footnote{See Section \ref{sect:limitations} for
  further discussion of this issue and an alternative approach.} This
could be done in \cass\ by introducing another type of decision
procedure, that of planning to achieve the goal, and assuming that it
would always be possible to find a plan to achieve the goal. This is a
strong assumption, but would certainly be valid in cases such as the
problem of opening a safe. This is an area of future work.
Interleaving planning and execution in this way would have the
advantage that it would not be necessary to plan for contingencies
that do not actually arise. It would however lose some of the
advantages of planning in advance. For example, possible interference
between actions performed before and after the information gathering
might be missed, leading the planner to find suboptimal plans. Indeed,
as sensing actions may in general change the world, executing them
before full construction of a viable plan might have the unfortunate
result of making the achievement of the goal impossible.

Planners that interleave planning and execution include \ipem\ 
\cite{A-IS88}, \xii\ \cite{GEW94} and \sage\ \cite{Kno95}. All three
use the same basic interleaving technique: only when no further
planning is possible are steps executed.  They thus do not set out to
decide in advance exactly when further planning will be necessary, and
their plans do not include explicit provision for further planning.
The effects of different interleaving strategies were investigated in
the design of \bump\ \cite{OG90}. In the Continue Elsewhere strategy
as much preplanning as possible was performed; in the Stop and Execute
strategy, goals defined in terms of sensor readings were executed as
soon as they were encountered. It was found that neither strategy had
a clear advantage over the other, in that both strategies sometimes
produced plans that were suboptimal or that might fail.

\subsection{Reactive Planning} \label{sect:react}

A different approach to the problem of planning under uncertainty is
taken in the {\em reactive planning\/} paradigm. In this approach, no
specific sequence of actions is planned in advance. Just as for
contingency planning, the planner is given a set of initial conditions
and a goal.  However, instead of producing a plan with branches, it
produces a set of condition-action rules: for example, {\em universal
  plans\/} \cite{Scho87} or Situated Control Rules (SCRs)
\cite{Dru89}. 

In theory, a reactive planning system can handle exogenous events as
well as uncertain effects and unknown initial conditions: it is
possible to provide a reaction rule for every possible situation that
may be encountered, whether or not the circumstances that would lead
to it can be envisaged. In contrast, a contingency planner such as
\cass\ cannot handle exogenous events as it cannot predict them.
\Cass\ and other contingency planners focus their planning effort on
circumstances that are predicted to be possible (or likely, in the
case of a probabilistic contingency planner such as \cburidan).

It would be possible to represent \cass's contingency plans as sets of
condition-action rules, by using the causal links and preconditions to
specify the conditions in which each action should be performed.
However, more reasoning is required at execution time to use reaction
rules than is required to execute a contingency plan.  Instead of
simply executing the next step in the plan, reasoning only at branch
points, the use of reaction rules requires the evaluation of
conditions on every cycle in order to select the relevant rule.


\section{Discussion}
\label{sect:end}

We have described \cass, a partial-order contingency planner that can
represent uncertain outcomes and construct contingency plans for those
outcomes.  The design of \cass\ is based on a coherent view of the
issues arising in planning under uncertainty.  It recognizes that, in
an uncertain world, a distinction must be drawn between the actual
state of the world and the planner's model of it; it instantiates an
intuitively natural account of why knowledge goals exist and how they
arise; and it bases its treatment of plan branching on the
requirements of the agent that will execute the plan.  As a result,
\cass\ explicitly plans to gather information and allows
information-gathering actions to be fully general.  The coherence of
its design provides a solid base for more advanced capabilities such
as the use of varying decision-making procedures.

\subsection{Contributions}
\label{sect:contribs}

The principal contribution of this work lies in the explicit
representation of decision steps and the implications this has for the
handling of knowledge goals. \Cass\ is, we believe, the first planner
in which decisions are represented as explicit actions in the plans
that it constructs.  \Cass's knowledge goals arise specifically from
the need to decide between alternative courses of action, as
preconditions of the decision actions. \Cass\ is thus consistent with
the view that planning is the process of making decisions in advance.
In this view, contingency plans are plans that defer some decisions
until the information on which they are based will be available
\cite{Pry95}. Different plan branches correspond to different decision
outcomes.

Through its use of explicit decision steps, \cass\ distinguishes
between sensing or information-gathering actions on the one hand, and
decision making on the other.  One important reason for making this
distinction is that a decision may depend on more than one piece of
information, each available through performing different actions.  In
addition, separating information-gathering from decision-making
provides a basis for introducing alternative methods for making
decisions.  For example, the extension to \cass\ described in
Section~\ref{sect:fail-safe} introduces a type of decision that
directs the executing agent to perform all branches resulting from a
given source of uncertainty, which allows the construction of plans
that can succeed in situations in which there is no way of telling
what the actual outcome is (\eg, the bomb-in-the-toilet problem).  We
believe that the explicit representation of different methods for
making decisions is an important direction for future research.

Because knowledge goals arise as preconditions of decisions in \cass,
the need to know whether a particular plan branch will work is
distinguished from the need to know the actual outcome of an
uncertainty. \Cass\ does not plan to determine outcomes unless they
are relevant to the achievement or otherwise of its goals. Moreover,
\cass\ does not treat knowledge goals as special cases: plans to
achieve them may be as complex as plans to achieve any other goals.
As well as planning to achieve knowledge goals that arise as
preconditions of decisions, \cass\ can also produce plans for
top-level knowledge goals.

Two other features of \cass\ are worth noting: the flexibility
afforded by its labeling scheme; and the potential for learning and
adaptation afforded by its representation of uncertainty.

\Cass's labeling scheme, although complex, allows the agent executing
the plan to distinguish between three classes of action: those that
must be executed in a given contingency; those that must not; and
those whose execution will not affect the achievement of the goal in
that contingency.\footnote{Not all agents can make use of this
  information, as there is no guarantee that the third type of step
  will actually be executable.} This feature paves the way for the
extension described above that allows \cass\ to build plans requiring
the execution of all branches resulting from a source of uncertainty.

\Cass's representation makes no assumptions as to the intrinsic nature
of uncertainty. An unknown precondition simply denotes that the
information as to what context will produce a particular effect from
an action is not available to the planner. It may be that this
information is in principle unknowable (in domains involving quantum
effects, for example); it is much more likely that the uncertainty
results from the limitations of the planner or of the information
available to it. In general, an agent operating in a real-world domain
will be much more effective if it can learn to improve its performance
and adapt to changing conditions. The use of unknown preconditions to
represent uncertainty means that in some circumstances it would be
relatively simple to incorporate the results of such learning and
adaptation into the planner's domain knowledge.  For example, the
planner might discover how to predict certain outcomes: it could then
change the unknown preconditions into ones reflecting the new
knowledge. If, on the other hand, it discovered that predicted effects
were consistently failing to occur, it could change the relevant
preconditions into unknown ones.

\subsection{Limitations}
\label{sect:limitations}

\Cass\ is one of an increasing number of planners that aim to extend
the techniques of classical planning to more realistic domains. \Cass\ 
is designed to operate in domains in which two of the three principal
constraints observed by classical planners are relaxed: namely, we
allow non-deterministic actions and incomplete knowledge of the
initial conditions. \Cass\ is, however, subject to the third
constraint, that changes do not take place except as a result of
actions specified in the plan. This clearly limits its effectiveness
in many real-world domains.  Moreover, there are limits on the extent
of the nondeterminism and incompleteness of knowledge that are
handled. \Cass's plans will not necessarily achieve their goals if
sources of uncertainty are ignored, or if all possible outcomes are
not specified.

\Cass\ cannot make use of information about how likely particular
outcomes are, unlike probabilistic or decision-theoretic planners; it
cannot plan to interleave planning and execution; and it does not
provide reaction rules for all possible circumstances. It can only
solve problems for which there are valid plans involving ways of
discriminating between possible outcomes; the algorithm given here
cannot solve the original version of the bomb-in-the-toilet problem,
although the extension described in Section~\ref{sect:fail-safe} can
do so \cite{CP95}.

The algorithm described in this paper has two major practical
limitations: first, the plans it produces are often more complex than
necessary; and second, the time taken to produce plans precludes its
use on all except simple problems.

The complexity of \cass's plans results from the necessity of planning
for every contingency and from the lack of branch merging. For
example, suppose you had to open a combination safe so that you
could obtain the money to pay for an evening out. \Cass's plan for the
goal of enjoying an evening out would have one branch for each
possible safe combination. Each branch would start off with the
actions to open the safe, which are different for each combination,
and would continue with the actions of going to a restaurant and then
to the movies, say, which would be identical in each branch. A simpler
plan would merge the separate branches after the safe had been
opened. The consideration of methods for branch merging is an area of
future work (see Sections \ref{sect:merging} and
\ref{sect:probplan}). 

In some circumstances, such as in this example, plan complexity could
be reduced through the use of run-time variables, which were
introduced in \ipem\ \cite{A-IS88} and used in \sensp\ \cite{EHW92}
(see Section~\ref{sect:relwork}). When the only uncertainty is in the
value that an action parameter takes (which is the case when opening a
combination safe) it would be possible to use a run-time variable to
represent that parameter, obviating the need for separate plan
branches. Implementing this strategy would require effective methods
for determining when the effects of uncertainty are limited to
parameter values. In general, this notion indicates a possible
approach to the problem of branch merging: that of taking a least
commitment approach to variable binding, in the same way that a least
commitment approach is taken to step ordering in a partial order
planner. This would then allow the concept of ``conditional'' variable
binding: a variable binding could be labeled as being required or
forbidden in a given contingency.

We have not analyzed the complexity of \cass's algorithm, but we
believe it to be exponential. This is because of the effect of
multiple plan branches, whose presence not only increases the number
of steps in a plan but also increases the number of potential
interactions and the number of ways of resolving them. Certainly, our
subjective impression is that \cass\ runs even more slowly than other
planners in the \snlp\ family. Effective domain-independent search
control heuristics are difficult to find, and in many of the (toy)
domains in which we have used \cass\ even problem-specific heuristics
are hard to come by.

\subsection{Conclusion}

\Cass\ is a planning system based firmly in the classical planning
paradigm. Many of its strengths and weaknesses are those of other
classical planning systems. For example, we believe that under certain
circumstances its plans will be valid and that it is guaranteed to
find a valid plan if one exists. However, the techniques it uses are
valid only in limited circumstances, and its computational complexity
is such as to make direct scaling up unlikely to be feasible.

In our view, the principal strengths of \cass\ arise from the explicit
representation of decisions in its plans. We have shown how this use
of decisions provides a natural account of how knowledge goals arise
during the planning process. We have also sketched how decisions can
be used as the basis of extensions that provide added functionality. A
new type of decision allows fail-safe plans, which can provide a
method of solving problems such as the bomb-in-the-toilet problem
(Section~\ref{sect:fail-safe}); and another type of decision may
provide an effective method of interleaving planning and execution
(Section~\ref{sect:interleave}).

We believe that the use of explicit decision procedures will enable
the extension of the range of applicability of techniques of classical
planning. In general, the idea of constructing a single plan that will
succeed in all circumstances is, we feel, unlikely to be productive:
the real world is complex and uncertain enough that trying to predict
its behavior in detail is simply impossible. However, the use of
decision procedures that, for example, involve probabilistic
techniques or interleave planning and execution, appears likely to
provide a flexible framework that, although inevitably sacrificing
completeness and correctness, will provide a basis for effective,
practical planning in the real world.




\appendix


\section{\Cass's Plans}
\label{cass-plans}

This appendix shows the plans constructed by \cass\ for the examples
in the body of the paper.  Each plan consists of initial conditions,
plan steps and goals.  The initial conditions are shown at the top of
the plan.  Those that are unknown are shown as depending on a
particular contingency.  The plan steps are shown next.  Each is shown
with a number denoting its order in the plan.  The numbers in
parentheses show the order in which the steps were added to the plan.
To the right of each step are its contingency labels.  For brevity,
the individual effects of each step are always omitted and the links
that establish the step's enabling and secondary preconditions are
often omitted.

Finally, at the bottom of the plan come the goal conditions. 
The goal is stated first, then each contingency goal is shown with the links
that establish it.  As usual, contingency labels are to the right.

\subsection{A Plan to Get to Evanston}
\label{plan:evanston}

This is the plan shown in Figure~\ref{fig:decstep} and discussed in
Section~\ref{sect:rep-decs}.  Note the decision-step with a single
active decision-rule.  This is the situation discussed in the comments
on one-sided contingencies in Section~\ref{sect:contplanissues}: the
route using Western is quicker when it is clear, while the Ashland
route is slower but always possible.

\begin{footnotesize}
\listing{trace-evanston}
\end{footnotesize}

\subsection{Disarming a Bomb}
\label{plan:bomb}

This is the plan shown in Figures~\ref{fig:uncertintro} and
\ref{fig:dunkplan} and discussed in Section~\ref{sect:contingintro}.
Note that both moving steps and both dunking steps are always
possible, but each is only necessary in one outcome of the
uncertainty.  A fail-safe plan (see Section~\ref{sect:complete}) is
therefore possible.

\begin{footnotesize}
\listing{trace-bomb}
\end{footnotesize}

\subsection{Fetching a Package}
\label{plan:fetch}

The plan in Figure~\ref{fig:packplan}, discussed in
Section~\ref{sect:multsources}, involves just one source of
uncertainty and hence contains just one decision-step.  There are two
possible ways of achieving the goal, one for each outcome of the
uncertainty.

\begin{footnotesize}
\listing{trace-package1}
\end{footnotesize}

\subsection{Fetching Another Package}
\label{plan:fetch2}

The plan in Figure~\ref{fig:2uncert}, discussed in
Section~\ref{sect:multsources}, has two sources of uncertainty and two
decision-steps.  There are four possible ways of achieving the goal,
one for each combination of the outcomes of the two sources of
uncertainty.

\begin{footnotesize}
\listing{trace-package2}
\end{footnotesize}

\subsection{Tossing a Coin}
\label{plan:cointoss}

In Section~\ref{sect:cassrule} we described a plan for ending up with
a flat coin.  The decision in this plan does not distinguish between
the coin landing heads-up and tails-up---the decision rules are
ambiguous.

\begin{footnotesize}
\listing{trace-coin1}
\end{footnotesize}

\subsection{Tossing Another Coin}
\label{plan:cointoss2}

The plan in Figure~\ref{fig:2decplan} has two decisions with
unambiguous decision-rules.  There are four ways of achieving the goal
in this plan, because there are two sources of uncertainty.

\begin{footnotesize}
\listing{trace-coin2}
\end{footnotesize}

\subsection{Opening a Door}
\label{plan:door}

In Section~\ref{sect:unsaferules} we described a plan for opening a
locked door without a key; it is depicted in
Figure~\ref{fig:doorplan}.  The plan that \cass\ produces for this
situation is shown here.  Even though no preconditions of the {\tt
  pick} step depend on any effect of the {\tt kick} step, the former
cannot be performed if the lock is broken as a result of kicking the
door.  The decision-rules reflect this dependence.

\begin{footnotesize}
\listing{trace-door}
\end{footnotesize}



\acks{Thanks to Dan Weld and Tony Barrett for supplying the \ucpop\ 
  code, Mark Peot and Robert Goldman for their comments on earlier
  drafts, Will Fitzgerald for many useful discussions, and the
  anonymous reviewers for their constructive and helpful criticism.
  Much of this work was performed while the first author was a student
  at the Institute for the Learning Sciences, Northwestern University.
  This work was supported in part by the AFOSR under grant number
  AFOSR-91-0341-DEF.  The Institute for the Learning Sciences was
  established in 1989 with the support of Andersen Consulting, part of
  The Arthur Andersen Worldwide Organization.  The Institute receives
  additional support from Ameritech and North West Water, Institute
  Partners, and from IBM.}

\vskip 0.2in

\bibliography{planning}

\bibliographystyle{theapa}

\end{document}



