3.2 Summary Conditions

The summary information for a plan $p$, $p_{sum}$, is a tuple $\langle pre_{sum}$, $in_{sum}$, $post_{sum}$, $usage_{sum}$, $consistent\rangle$, whose members are sets of summary conditions, summarized resource usage, and a $consistent$ flag indicating whether the plan will execute consistently internally. $pre_{sum}(p)$ and $post_{sum}(p)$ are summary pre- and postconditions, which are the external pre- and postconditions of $p$, respectively. The summary inconditions of $p$, $in_{sum}(p)$, contain all conditions that must hold within some execution of $p$ for it to be successful. A condition $c$ in one of these sets is a tuple $\langle\ell,existence, timing\rangle$. $\ell(c)$ is the literal of $c$. The $existence$ of $c$ can be $must$ or $may$. If $existence(c)=must$, then $c$ is called a $must$ condition because $\ell$ must hold for every successful plan execution. For convenience we usually write $must(c)$. $c$ is a $may$ condition ($may(c)$ is $true$) if $\ell(c)$ must hold for some successful execution.

The $timing$ of a summary condition $c$ can either be $always$, $sometimes$, $first$, or $last$. $timing(c)$ is $always$ for $c\in in_{sum}$ if $\ell(c)$ is an incondition that must hold throughout all potential executions of $p$ ($\ell$ holds always); otherwise, $timing(c)=sometimes$ meaning $\ell(c)$ holds at one point, at least, within an execution of $p$. So, an $always$ condition is $must$, and we do not define $may$ $always$ inconditions because whether it is $may$ because of existence or timing, it is not significantly different from $may$ $sometimes$ in how a planner reasons about it. Whether a condition is $may$ $always$ (however defined) or $may$ $sometimes$, another plan can only have a $may$ $clobber$ relationship with the condition (as defined in Section 3.3). Note also that the incondition of a CHiP has the restricted meaning of a $must$ $always$ summary incondition. The $timing$ is $first$ for $c\in pre_{sum}$ if $\ell(c)$ holds at the beginning of an execution of $p$; otherwise, $timing=sometimes$. Similarly, $timing$ is $last$ for $c\in post_{sum}$ if $\ell(c)$ is asserted at the end of a successful execution of $p$; otherwise, it is $sometimes$. Although $existence$ and $timing$ syntactically only take one value, semantically $must(c)\Rightarrow may(c)$, and $always(c)\Rightarrow sometimes(c)$.

We considered using modal logic operators to describe these concepts. While a mix of existing temporal logic and dynamic logic [Pratt, 1976] notation could be forced to work, we found that using our own terminology made definitions much simpler. We discuss this more at the end of Section 8.

Definitions 7, 8, and 9 give the formal semantics of $existence$ and $timing$ for a few representative condition types. Summary conditions of a plan are defined recursively in that they depend on the summary conditions of the plan's immediate subplans instead of its complete decomposition. Because a single description of summary information could represent many different plan hierarchies, we quantify over plans $p'$, whose subplans have the same summary information as those of the plan $p$ being summarized. We could have defined the existence and timing properties of conditions based on the entire hierarchy, but in doing so, deriving summary conditions would be as expensive as solving the planning problem, and one of the main purposes of summary information is to reduce the computation of the planning problem. The reason why it would be so expensive is that in the worst case all legal orderings of all plan steps must be explored to determine whether a condition is $must$ or $may$. We will discuss an example of this at the end of this subsection.

Definition 7   $$\begin{array}{@{}l@{}l@{}l} [mu&st,may]\_first\_precondition... ...}) \wedge \ell \in pre(p'') \end{array} \end{array}\end{array}$$

Definition 8   $$\begin{array}{@{}l@{}l@{}l} must&\_always\_incondition(\ell,... ...{p''}) \wedge \ell\in in(p'') \end{array}\end{array}\end{array}$$

Definition 9   $$\begin{array}{@{}l@{}l@{}l} [mus&t,may]\_sometimes\_incondit... ... \ell\in post(p'') \end{array}\end{array}\end{array}\end{array}$$

Definition 7 states that a $first$ precondition of $p$ is an external precondition that is always required at the beginning of the execution of any $p'$ that has the same conditions as $p$ and the same summary information and ordering for its subplans as $p$. A last postcondition is always asserted at the end of the execution (substitute ``pre'' with ``post'' and $t_s$ with $t_f$ in the last two lines of Definition 7). A [must,may] sometimes precondition is a [must,may] external precondition that is not a $first$ precondition. A sometimes postcondition is defined similarly. Definition 8 states that a literal $\ell$ is a $must$, $always$ incondition of a plan $p$ if at any time during any isolated execution of any $p'$ with the same summary information as $p$, some executing plan $p''$ has incondition $\ell$. Definition 9 states that a [must, may] sometimes incondition of plan $p$ is a condition that is required during [any, some] execution of [any, some] plan $p'$ that has the same summary information and ordering for its subplans as $p$.

The $consistent$ flag is a boolean indicating whether the plan (or any plan with the same summary information and ordering for subplans) would execute successfully no matter how it was decomposed and no matter when its subplans were executed. Definition 10 says that all possible executions will succeed for a consistent plan. This is very similar to the $CanAnyWay$ relation that will be defined in Section 4. We do not include whether the plan will definitely not succeed in the summary information because it requires an exponential computation to see whether all conflicts in the subplans can be resolved. This computation can wait to be done during planning after summary information is fully derived.

Definition 10   $$\begin{array}{@{}l@{}l@{}l} cons&istent(p) \equiv \\ &\for... ...p'} \in \mathcal{E}(p'), e_{p'} succeeds \end{array}\end{array}$$

We show a subset of the summary conditions for the production manager's top-level plan (of Figure 2) below. Following each literal are modal tags for $existence$ and $timing$ information. ``Mu'' is $must$; ``Ma'' is $may$; ``F'' is $first$; ``L'' is $last$; ``S'' is $sometimes$; and ``A'' is $always$.

Production manager's $produce\_H$ plan:
Summary preconditions:
available(A)MuF, available(M1)MaS, available(M2)MaS
Summary inconditions:
$\neg$available(A)MuS, available(M1)MaS, available(M2)MuS, available(G)MuS,
available(A)MuS, $\neg$available(M1)MaS, $\neg$available(M2)MuS, $\neg$available(G)MuS,
available(H)MuS, $\neg$available(H)MuS
Summary postconditions:
$\neg$available(A)MuS, available(M1)MaS, available(M2)MuS, $\neg$available(G)MuS,
available(H)MuL

The $available(M1)$ summary precondition is a $may$ condition because the production manager may end up not using M1 if it chooses to use M2 instead to produce G. $available(A)$ is a $first$ summary precondition because part A must be used at the beginning of execution when it is transported to one of the machines. Because the machines are needed sometime after the parts are transported, they are sometimes (and not first) conditions: they are needed at some point in time after the beginning of execution.

Because the production manager may use M1 to produce G, $\neg available(M1)$ is a summary incondition of $produce\_H$. Having both $available(M1)$ and $\neg available(M1)$ as inconditions is consistent because they are $sometimes$ conditions, implying that they hold at different times during the plan's execution. In contrast, these conditions would conflict if they were both $must$ and $always$ (meaning that they must always hold throughout every possible execution of the plan).

The summary condition $\neg available(A)$ is a $must$ postcondition of the top-level plan because A will definitely be consumed by $make\_G$ and is not produced by some other plan in the decomposition of $produce\_H\_from\_G$. Even though $available(G)$ is an effect of $produce\_G$, it is not an external postcondition of $produce\_H$ because it is undone by $produce\_H\_from\_G$, which consumes G to make H. $available(H)$ is a $last$ summary postcondition because the production manager releases H at the very end of execution. $available(M2)$ is not $last$ because the manager finishes using M2 before moving H into storage.

Notice that $available(M2)$ is a $may$ summary precondition. However, no matter how the hierarchy is decomposed, M2 must be used to produce H, so $available(M2)$ must be established externally to the production manager's plan. Because summary information is defined in terms of the summary information of the immediate subplans, in the subplans of $produce\_H$, we only see that $produce\_G$ has an $available(M2)MaS$ precondition and an $available(M2)MaS$ postcondition that would achieve the $available(M2)MuF$ precondition of $produce\_H\_from\_G$. This summary information does not tell us that the precondition of $produce\_G$ exists only when the postcondition exists, a necessary condition to determine that the derived precondition of $produce\_H$ is a $must$ condition. Thus, it is $may$. If we augmented summary information with which subsets of conditions existed together, hunting through combinations and temporal orderings of condition subsets among subplans to derive summary conditions would basically be an adaptation of an HTN planning algorithm, which summary information is intended to improve. Instead, we derive summary information in polynomial time and then use it to improve HTN planning exponentially as we explain in Section 6. This is the tradeoff we made at the beginning of this section in defining summary conditions in terms of just the immediate subplans instead of the entire hierarchy. Abstraction involves loss of information, and this loss enables computational gains.