3.5.2 Resource Summarization Algorithm

The state summarization algorithm in Section 3.4 recursively propagates summary conditions upwards from an / hierarchy's leaves, and the algorithm for resource summarization takes the same approach. Starting at the leaves, the algorithm finds primitive tasks that use constant amounts of a resource. The resource summary of a task using units of a resource is ,,,,, or ,,,,, over the task's duration for non-consumable or consumable resources respectively.

Moving up the / tree, the summarization algorithm either comes to an or an branch. For an branch the combined summary usage comes from the computation where and extract the lower bound and upper bound of a range respectively. The denote the branch's children with their durations extended to the length of the longest child. This duration extension alters a child's resource summary information because the child's usage profile has a zero resource usage during the extension. For instance, in determining the resource usage for (A,B), the algorithm combines two 40 minute tasks with a 50 minute task. The resulting summary information describes a 50 minute abstract task whose profile might have a zero watt power usage for 10 minutes. This extension is why (A,B) has a [0,4] for a instead of [3,4]. Planners that reason about variable durations could use [3,4] for a duration ranging from 40 to 50.

Computing an branch's summary information is a bit more
complicated due to timing choices among loosely constrained subtasks.
The *take path* examples illustrate the simplest sub-case,
where subtasks are tightly constrained to execute serially. Here
profiles are appended together, and the resulting summary usage
information comes from the SERIAL-AND computation
where and are the
respective lower and upper bounds on the cumulative persistent usages
of children that execute before . These computations have the same
form as the computations for the final .

The case where all subtasks execute in parallel and have identical durations is slightly simpler. Here the usage profiles add together, and the branch's resultant summary usage comes from the PARALLEL-AND computation where and are the respective sums of the upper bounds and the lower bounds for all children except .

To handle tasks with loose temporal constraints, we consider all
legal orderings of child task endpoints. For example, in the rover's
early morning tasks, there are three serial solar energy collection
subtasks running in parallel with a subtask to drive to location .
Figure 12 shows one possible ordering of the subtask
endpoints, which breaks (A,B) into three pieces, and two of
the *soak rays* children in half. Given an ordering, the
summarization algorithm can (1) use the endpoints of the children to
determine subintervals, (2) compute summary information for each child
task/subinterval combination, (3) combine the parallel subinterval
summaries using the PARALLEL-AND computation, and then (4) chain the
subintervals together using the SERIAL-AND computation. Finally, the
task's summary is computed by combining the summaries for all
possible orderings using an computation.

Here we describe how step (2) generates different summary resource
usages for the subintervals of a child task.
A child task with summary resource usage
,,,,, contributes one of two summary
resource usages to each intersecting subinterval^{4}:
While the first usage has the tighter [,],[,] local ranges, the
second has looser [,],[,] local ranges. Since the and
bounds only apply to the subintervals containing the subtask's minimum
and maximum usages, the tighter ranges apply to one of a subtask's
intersecting subintervals. While the minimum and maximum usages may
not occur in the same subinterval, symmetry arguments let us connect
them in the computation. Thus one subinterval has tighter local
ranges and all other intersecting subintervals get the looser local
ranges, and the extra complexity comes from having to investigate all
subtask/subinterval assignment options. For instance, there are three
subintervals intersecting (A,B) in Figure 12,
and three different assignments of summary resource usages to the
subintervals: placing [0,4],[4,6] in one subinterval with
[0,6],[0,6] in the other two. These placement options result in a
subtask with subintervals having possible subinterval
assignments. So if there are child tasks each with alternate
assignments, then there are combinations of potential
subtask/subinterval summary resource usage assignments. Thus
propagating summary information through an branch is exponential
in the number of subtasks with multiple internal subintervals.
However since the number of subtasks is controlled by the domain
modeler and is usually bounded by a constant, this computation is
tractable. In addition, summary information can often be derived
offline for a domain. The propagation algorithm takes on the form:

- For each consistent ordering of endpoints:
- For each consistent subtask/subinterval summary usage assignment:
- Use PARALLEL-AND computations to combine subtask/subinterval summary usages by subinterval.
- Use a SERIAL-AND computation on the subintervals' combined summary usages to get a consistent summary usage.

- For each consistent subtask/subinterval summary usage assignment:
- Use computation to combine all consistent summary usages to get task's summary usage.

Now that we have described how to derive summary information, we can discuss how to use it.