next up previous
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 $\langle$[$x$, $x$], [$x$, $x$], [$x$, $x$]$\rangle$ for a consumable resource with an initial level $x$ and $\langle$[$x$, $x$], [$x$, $x$], [0, 0]$\rangle$ 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 $CanAnyWay$ and $MightSomeWay$ 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. $CanAnyWay(order, P_{sum}, res)$ is true if and only if there are no potential threats. These algorithms discover a threat if they ever compute an interval $i$ such that


\begin{displaymath}
\setlength{\arraycolsep}{0in}
\begin{array}[t]{lllll}
lb(lo...
...alue(res)\ \vee \ ub(persist(i)) > max\_value(res).
\end{array}\end{displaymath}


$MightSomeWay(order, P_{sum}, res)$ 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


\begin{displaymath}
\setlength{\arraycolsep}{0in}
\begin{array}[t]{lllll}
ub(lo...
...res)\ \wedge \ ub(persist(i)) \leq max\_value(res).
\end{array}\end{displaymath}


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 up previous
Next: 5 Hierarchical Planning and Up: 4 Identifying Abstract Solutions Previous: 4.1 Threats on Summary
Bradley Clement 2006-12-29