3.1 Overview

The summary information of plan $p$ consists of summary pre-, in-, and postconditions ($pre_{sum}(p)$, $in_{sum}(p)$, $post_{sum}(p)$), summary resource usage ($usage_{sum}(p,res)$) for each resource $res$, and whether the plan can be executed in any way successfully ($consistent$).

A summary condition (whether pre, post, or in) specifies not only a positive or negated literal, but additional modal information. Each summary condition has an associated $existence$, whose value is either $must$ or $may$ depending on whether it must hold for all possible decompositions of the abstract operator or just may hold depending on which decomposition is chosen. The $timing$ of a summary condition is either $first$, $last$, $always$, or $sometimes$, specifying when the condition must hold in the plan's interval of execution. A plan $p_1$ must [achieve, clobber] summary precondition $c_2$ of $p_2$ if the execution of $p_1$ (or that of any plan with the same summary information) would [achieve, clobber] a condition summarized by $c_2$ (or any plan with the same summary information as $p_2$).

The algorithm for deriving summary conditions for plan $p$ takes as input the summary conditions of the immediate subplans of $p$ and the conditions defined for the CHiP $p$. The pre-, in-, and postconditions of $p$ become must first, must always, and must last summary conditions, respectively. The algorithm retains the existence and timing of subplan summary conditions in the parent depending on whether the conditions are achieved, clobbered, or undone by siblings, whether the decomposition is $and$ or $or$, whether the subplan is ordered first or last, and whether all subplans share the same condition. Subplan first, always, and last conditions can become sometimes conditions in the parent. The parent is computed as $consistent$ as long as all subplans are $consistent$, no subplan may clobber a summary condition of another, and summarized resources do not violate limits.

We represent summary resource usage as three value ranges, $\langle local\_min$, $local\_max$, $persist \rangle$, where the resource's local usage occurs within the task's execution, and the persistent usage represents the usage that lasts after the task terminates for depletable resources. The summarization algorithm for an abstract task takes the summary resource usages of its subtasks, considers all legal orderings of the subtasks, and all possible usages for all subintervals within the interval of the abstract task, to build multiple usage profiles. These profiles are combined with algorithms for computing parallel, sequential, and disjunctive usages to give the summary usage of the parent task.