** Next:** 5 Hierarchical Planning and
** Up:** 4 Identifying Abstract Solutions
** Previous:** 4.1 Threats on Summary

##

4.2 Summary Resource Usage Threats

Planners detect threats on resource constraints in different ways.
If the
planner reasons about partially ordered actions, it must consider
which combinations of actions can overlap and together exceed (or fall below)
the resource's maximum value (or minimum value). A polynomial
algorithm does this for the IxTeT planner [Laborie Ghallab, 1995].
Other planners that consider total order plans
can more simply project the levels of the resource from the initial
state through the plan, summing overlapping usages, to see if there are conflicts []<e.g.,>rabideau:00.

Finding conflicts involving summarized resource usages can work in the
same way. For the partial order planner, the resultant usage of
clusters of actions are tested using the PARALLEL-AND algorithm in
Section 3.5. For the total order planner, the level of
the resource is represented as a summarized usage, initially
[, ], [, ], [, ] for a consumable
resource with an initial level and [, ], [,
], [0, 0] for a non-consumable resource. Then, for each
subinterval between start and end times of the schedule of tasks, the
summary usage for each is computed using the PARALLEL-AND algorithm.
Then the level of the resource is computed for each subinterval while
propagating persistent usages using the SERIAL-AND algorithm.

We can decide and as defined in Section
4.1, in terms of the summary usage values resulting
from invocations of PARALLEL-AND and SERIAL-AND in the propagation algorithm at the end of Section 3.5.2. is true if and only if there are no potential threats. These algorithms discover a threat if they ever compute an interval such that

is true if and only if there is a possible run with potentially no threats. SERIAL-AND discovers such a run if it returns a summary usage where

Now that we have mechanisms for deriving summary information and evaluating plans based on their summarizations, we will discuss how to exploit them in a planning/coordination algorithm.

** Next:** 5 Hierarchical Planning and
** Up:** 4 Identifying Abstract Solutions
** Previous:** 4.1 Threats on Summary
Bradley Clement
2006-12-29