A Probabilistic Framework for Resource-Constrained Multi-Agent Planning

1. Both PREC(op) and FOIL(op) not empty.

ASTI(op) is therefore determined by the start times generated for opt, the operation with maximum index in PREC(op) and op,, the operation with minimum index in FOIL(op). If these are respectively t 1 and t 2 , the left and right limit of ASTI(op) are given respectively by:

where MPn,. = I_':, 1 D.opk. We indicate with P.,(opt,tl'op,,t 2 ) the conjunct density of probability of the start times of opt and op, to be respectively t 1 and t2" We have:

2. Only one of PREC(op) or FOIL(op) empty.

Suppose PREC(op) is empty. Then ASTI(op) is always limited to the left by est(op). We have:

A similar expression holds if FOIL(op) is empty.

3. Both PREC(op) and FOIL(op) empty.

Notable special cases follow from assumptions concerning the allocation strategy that are typical in scheduling/planning work. Assume that the first and last operations in a given plan are indexed m and n respectively. If allocation decisions for the operations in the plan are generated sequentially starting from the first operation and moving forward, we have:

. ...,

Similar expressions hold if allocation decisions ..are made sequentially starting from the last operation and moving backward. Moreover, these forward and backward formulas can be directly extended to strategies in which the operations in a plan are scheduled outward from some initial anchor (e.g. a bottleneck operation).

III PROBABILISTIC REPRESENTATION OF CAPACITY REQUESTS

We can now represent the consequences of RSTG­ allocations with respect to a resource's available capacity. From the resource's point of view, the capacity requested by an RSTG-allocation IS a discrete stochastic process, R(opi,t). At any instant of time t the process can assume a value n, the units of capacity needed for the execution of opi, or a value 0, if the operation is not allocated over t. The instantaneous probabilities of these values are respectively:

The total request for capacity on a resource resk at time t, R(res*,t), is a discrete stochastic process with value

where n is the set of operations allocated on the resource.

From the description of RSTG in Section II, we see that distinct RSTG-allocations on the same resource are statistically independent. RSTG can indeed consider the effects of prior RSTG-allocations in generating a particular allocation, but only indirectly through the currently posted RSTG-constraints. Given this statistical independence, it follows that if the number of allocations that overlap at time t is sufficiently high, we can approximate the first order distribution of R(resk,t) with a Gaussian random variable, with mean and variance given by:

We now need a way to compare the requests of capacity with that actually available, to detect or avoid possible situations of overflow. Notice that if we wanted to prohibit RSTG from generating overflow situations, we should post RSTG constraints that would imply, once implemented, a very low load on the resources. However, since RSTG is not intended to generate actual executable allocations but rather to evaluate constraints, we will adopt a less strict criterion that generalizes from deterministic methods for detecting capacity violations. We say that a resource is congested at time t if the probability of a high instantaneous request of capacity in t is greater than a fixed threshold. If C(resk) is the actual capacity of resk and Tis the congestion threshold, we can express the congestion constraint with:

where Cl>(.) denotes the cumulative distribution for a standard normal random variable.

We note in passing that in addition to detecting overflow situations, we can use this constraint to deduce the maximum instantaneous probability of a given request for capacity that does not induce an overflow, assuming constraints over the allocation of other operations have been fixed. This is discussed further in [6].

IV APPLYING TilE PROBABILISTIC FRAMEWORK

Depending on what kind of RSTG-constraints are specified and liow they are posted, the probabilistic framework can have different uses. We describe two applications below.

A. Bottleneck Detection

The OJ?POrtunistic job-shop scheduling methodology described m [9, 7] obtains notaole advantages by first making allocation decisions at critical (i.e. bottleneck) resources. Since bottlenecks can vary depending on the characteristics of the scheduling problem, this methodology requires a focusing mechanism that identifies potential bottlenecks from a specification of the current problem.

Conceptually, we can define a probabilistic bottleneck detection mechanism as operating in two steps:

1. Assuming no interactions among agents (i.e. infinite resource capacity), RSTG is used to produce a schedule for each agent in accordance with its personal constraints (e.g. due date).
2. The consequences of these uncoordinated decisions are assessed with respect to available resource capacity. A resource will be considered a bottleneck during time intervals in which the congestion constraint of Section m is violated.

Correspondent to this definition, the RSTG-constraints posted for bottleneck detection will satisfy the following conditions:

• Since the goal is to analyze the effect of the initial temporal constraints of the problem, STI(op) for a given opi will be the largest interval compatible with the release and due dates of the plan containing OP;·
• Independence among agents implies that the allocation strategy will not impose ordering relations between operations belonging to different plans. Operations belonging to the same plan might be ordered according to some internal strategy (e.g. forward scheduling).
• For analogous reasons, only preference constraints related to temporal aspects of plans (e.g. work-in­ process time) will be posted.

To see the advantage of this probabilistic mechanism, consider a deterministic counterpart. In this case, bottleneck analysis must be based on one potential shop schedule (e.g. the best possible schedule for each agent), and, consequently, the analysis is subject to idiosyncratic results (e.g. detected resource congestion might, in fact, disappear if one or more agent schedules where slightly altered). The probabilistic mechanism avoids this P.roblem by considering the consequences of a set of poss1ble solutions.

B. Time Bound Scheduling

Another application is time bound scheduling, the establishment of temporal constraints on each operation that refine initial problem constraints (i.e. release and due dates) without committing to specific allocation times to identify a solution sub-space from which the final executable schedule will be generated. In this case, we assume a scheduling mechanism that iteratively adds (posts) RSTG-constraints (e.g. fixes an SI'l) for a previously unconsidered operation on each iteration. RSTG 1s used at each step to estimate the consequences of the constraints posted tlius far, enabling the scheduler to avoid situations of resource congestion in its future decisions.

There are two ways in which knowledge of resource congestion can be included in the RSTG-constraints:

• In establishing a new STI(opi), time intervals in which resource congestion is already over the congestion threshold can be excluded. This consistency constraint is the analog of a resource unavailability constraint in deterministic representations of available capacity (e.g. [5]).
• Preference constraints can be introduced to weigh alternative allocations in ASTI(op), using a utility function inversely proportional to the level of congestion of the resource.

V FINAL REMARKS

We have presented a framework for evaluation and generation of abstract plans in resource-constrained problem domains. Our current research centers on the development of a computationally inexpensive implementation in the context of bottleneck detection. ln particular, we feel that both P .... and P, can be reasonably approximated with piece-wise constant functions over time.