### Topics

### features

### Publications

### Issue Archive

# Computing Bounds on Resource Levels for Flexible Plans

- Friday, 04 September 2009

### New algorithm entails less computation than previous algorithms.

A new algorithm efficiently computes the tightest exact bound on the levels of resources induced by a flexible activity plan (see figure). Tightness of bounds is extremely important for computations involved in planning because tight bounds can save potentially exponential amounts of search (through early backtracking and detection of solutions), relative to looser bounds.

The bound computed by the new algorithm, denoted the resource-level envelope, constitutes the measure of maximum and minimum consumption of resources at any time for all fixed-time schedules in the flexible plan. At each time, the envelope guarantees that there are two fixed-time instantiations — one that produces the minimum level and one that produces the maximum level. Therefore, the resource-level envelope is the tightest possible resource-level bound for a flexible plan because any tighter bound would exclude the contribution of at least one fixed-time schedule. If the resource-level envelope can be computed efficiently, one could substitute looser bounds that are currently used in the inner cores of constraint-posting scheduling algorithms, with the potential for great improvements in performance.

What is needed to reduce the cost of
computation is an algorithm, the measure
of complexity of which is no greater than a
low-degree polynomial in *N* (where *N* is
the number of activities). The new algorithm
satisfies this need. In this algorithm,
the computation of resource-level
envelopes is based on a novel combination
of (1) the theory of shortest paths in the
temporal-constraint network for the flexible
plan and (2) the theory of maximum
flows for a flow network derived from the
temporal and resource constraints. The
measure of asymptotic complexity of the
algorithm is O(*N*·O(maxflow(*N*)), where
O(*x*) denotes an amount of computing
time or a number of arithmetic operations
proportional to a number of the order of
*x* and O(maxflow(*N*)) is the measure of
complexity (and thus of cost) of a maximum-flow algorithm applied to an auxiliary
flow network of 2*N* nodes. The algorithm
is believed to be efficient in practice;
experimental analysis shows the practical
cost of maxflow to be as low as O(*N*^{1.5}).

The algorithm could be enhanced following at least two approaches. In the first approach, incremental subalgorithms for the computation of the envelope could be developed. By use of temporal scanning of the events in the temporal network, it may be possible to significantly reduce the size of the networks on which it is necessary to run the maximum-flow subalgorithm, thereby significantly reducing the time required for envelope calculation. In the second approach, the practical effectiveness of resource envelopes in the inner loops of search algorithms could be tested for multi-capacity resource scheduling. This testing would include inner-loop backtracking and termination tests and variable and value-ordering heuristics that exploit the properties of resource envelopes more directly.

*This work was done by Nicola Muscettola
of Ames Research Center and David Rijsman
of Mission Critical Technologies Inc. For further
information contact the Technology
Partnerships Division, Ames Research Center,
(650) 604-2954. ARC-14948-1*

### White Papers

| ||||||