The summary information for a plan , , is a tuple , , , , , whose members are sets of summary conditions, summarized resource usage, and a flag indicating whether the plan will execute consistently internally. and are summary pre- and postconditions, which are the external pre- and postconditions of , respectively. The summary inconditions of , , contain all conditions that must hold within some execution of for it to be successful. A condition in one of these sets is a tuple . is the literal of . The of can be or . If , then is called a condition because must hold for every successful plan execution. For convenience we usually write . is a condition ( is ) if must hold for some successful execution.
The of a summary condition can either be , , , or . is for if is an incondition that must hold throughout all potential executions of ( holds always); otherwise, meaning holds at one point, at least, within an execution of . So, an condition is , and we do not define inconditions because whether it is because of existence or timing, it is not significantly different from in how a planner reasons about it. Whether a condition is (however defined) or , another plan can only have a relationship with the condition (as defined in Section 3.3). Note also that the incondition of a CHiP has the restricted meaning of a summary incondition. The is for if holds at the beginning of an execution of ; otherwise, . Similarly, is for if is asserted at the end of a successful execution of ; otherwise, it is . Although and syntactically only take one value, semantically , and .
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 and 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 , whose subplans have the same summary information as those of the plan 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 or . We will discuss an example of this at the end of this subsection.
Definition 7 states that a precondition of is an external precondition that is always required at the beginning of the execution of any that has the same conditions as and the same summary information and ordering for its subplans as . A last postcondition is always asserted at the end of the execution (substitute ``pre'' with ``post'' and with in the last two lines of Definition 7). A [must,may] sometimes precondition is a [must,may] external precondition that is not a precondition. A sometimes postcondition is defined similarly. Definition 8 states that a literal is a , incondition of a plan if at any time during any isolated execution of any with the same summary information as , some executing plan has incondition . Definition 9 states that a [must, may] sometimes incondition of plan is a condition that is required during [any, some] execution of [any, some] plan that has the same summary information and ordering for its subplans as .
The 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 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.
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 and information. ``Mu'' is ; ``Ma'' is ; ``F'' is ; ``L'' is ; ``S'' is ; and ``A'' is .
Production manager's plan:
The summary precondition is a condition because the production manager may end up not using M1 if it chooses to use M2 instead to produce G. is a 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, is a summary incondition of . Having both and as inconditions is consistent because they are conditions, implying that they hold at different times during the plan's execution. In contrast, these conditions would conflict if they were both and (meaning that they must always hold throughout every possible execution of the plan).
The summary condition is a postcondition of the top-level plan because A will definitely be consumed by and is not produced by some other plan in the decomposition of . Even though is an effect of , it is not an external postcondition of because it is undone by , which consumes G to make H. is a summary postcondition because the production manager releases H at the very end of execution. is not because the manager finishes using M2 before moving H into storage.
Notice that is a summary precondition. However, no matter how the hierarchy is decomposed, M2 must be used to produce H, so 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 , we only see that has an precondition and an postcondition that would achieve the precondition of . This summary information does not tell us that the precondition of exists only when the postcondition exists, a necessary condition to determine that the derived precondition of is a condition. Thus, it is . 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.