Contingency Analysis in the Design-to-Criteria Scheduler

Introduction

We extend the Design-to-Criteria scheduler to more efficiently deal with uncertainty present in a schedule. This is based on an analysis of available schedules that can be used to recover from a situation in which partially executed schedules cannot be completed successfully. In addition to evaluating schedules more effectively from the uncertainty perspective, we also implement method reordering techniques to minimize uncertainty. The Design-to-Criteria scheduler with its present functionality does some reordering of subtasks within a schedule [Wagner97b] but it does not reason about whether there are ways to recover from failure scenarios.

We define schedule robustness as a characteristic of a schedule in which the schedule allows for recovery from execution failure of one of the scheduled actions. In evaluating a schedule, we want to take into account whether there exist alternative ways of completing the schedule, i.e., achieving the high level task, if the schedule should fail during the course of execution. This type of analysis, called contingency planning can be expensive because it could involve an exhaustive search for the appropriate method that would improve schedule robustness without diminishing the criteria requirements [Bresina94]. However, the technique we describe here implements an algorithm which eliminates the need to do an exhaustive search, even though it is more expensive than our non-contingency scheduling approach.

We found that our work done using the Design-to-Criteria framework addresses similar questions namely

How can we effectively predict the performance of a schedule when there is uncertainty in the performance of methods in the schedule?
What are the different approximations to the execution-time performance measure and when is a specific approximation appropriate?

Our work differs from previous work done in contingency planning and scheduling in the following ways:

Construction of contingent schedules in our analysis is done in interactive time even as the problem is being solved and hence we have real duration and cost constraints in evaluating the entire search space.
We constantly evaluate the user specifications with the criteria constraints to get a satisficing yet robust result.
Our algorithm takes advantage of the structural analysis of the problem, namely the TÆMS task structure representation, to reduce the complexity of the search problem.

The Expected Lower Bound and the Approximate Expected Bound

The motivation for evaluating performance measures for contingency planning is the following. ``Different approximations of execution-time performance measures represent different amounts of work in handling contingency scheduling. We want to evaluate these approximations based on the amount of work and the performance trade-offs.''

An Information Gathering example

We describe a simple example which concisely captures the complexity and functionality of contingency analysis.

**Figure:** Gather review information on Adobe Photoshop.
$\begin{figure}\begin{center}\includegraphics [width=0.6\textwidth, height=0.3\textheight]{review.eps} \end{center}\end{figure}$

Expected Lower Bound Rating

In this paper, we will call the objective function based rating returned by the standard Design-to-Criteria scheduler the Expected Lower Bound(ELB) and view it as the statistical measure of the characteristics of a schedule assuming no rescheduling.

For the example described in the earlier section, we will focus on maximizing quality within a hard deadline of 18 minutes. The two possible schedules are {A1,A2,A3} and {B}. The ELB takes into account the various possible permutations of method outcomes along with the quality achieved. Figure 2 describes the computation of the ELB ratings for the schedule {A1,A2,A3}.

**Figure 2:** Each row represents a possible permutation of the quality distributions of methods A1, A2, A3 in schedule {A1,A2,A3}. The first three columns represent the possible ratings(Quality) achieved by each of the methods A1, A2, A3. The fourth column shows the probability of the particular quality distribution combination occurring and the last column shows the final quality of the schedule.
$\begin{figure}\small\begin{center}\begin{tabular}{\vert\vert c\vert c\vert ... ...10\% 0.5 & 1.875\% & 0.5 \ \hline\hline\end{tabular} \end{center}\end{figure}$

Consider the first entry of the table. It handles the case when method A1 achieves a quality of 2, which occurs with a probability of 0.5 as described in the TÆMS task structure. Method A2 achieves a quality of 0 with probability 0.25. The probability of the methods achieving these qualities simultaneously in a single execution is 0.125, given in column 4. The expected quality of the schedule {A1,A2,A3} is 0 in this case, described in column 5. The duration and cost distributions and their expected values are computed in a similar fashion. The ELB ratings for schedules {A1,A2,A3} and {B} are given below.

{A1,A2,A3}: Rating: 0.97 (Expected Quality)

Quality : (25% 0.0) (24% 0.5) (17% 1.0) (34% 2.0)

Duration : (100% 18)

{B}: Rating 0.6 (Expected Quality)

Quality : (20% 1) (80% 0.5)

Duration: (80% 6) (20% 8)

The schedule {A1,A2,A3} is chosen and executed since it has the best expected lower bound rating of 0.97. A1 executes successfully , then A2 executes and suppose A2 fails (i.e. it results in 0 quality), which happens 25% of the time. Then A3 fails to get enabled and the schedule breaks since there is no time left to reschedule {B} as an alternate schedule.

Because of the one-pass low-order polynomial method sequencing approach used by the scheduler to control scheduling combinatorics, the standard Design-to-Criteria scheduler will only produce one permutation of the methods A1, A2, and A3. However, if the scheduler did produce multiple permutations, the schedules {A1,A2,A3} and {A2,A1,A3} would receive the same expected lower bound value. Hence the contention is that there is no difference in performance if either of the two was chosen, or produced by the method ordering heuristics. However on more detailed evaluation of the schedules, we see that {A2,A1,A3} allows for recovery and contingency scheduling which schedule {A1,A2,A3} does not permit (Figure 3) for the given deadline. If {A2,A1,A3} is the schedule being executed and A2 fails, there is time to schedule method {B} and complete task TG1. This clearly implies that schedule {A2,A1,A3} should have a better expected performance rating than {A1,A2,A3} as the schedule {A2,A1,A3} includes the recovery option from failure in its structure.

**Figure:** Schedule options for example one with (schedule rating) values.
$\begin{figure}\begin{center} \includegraphics [width=0.6\textwidth,height=0.3\textheight]{tree1.eps} \end{center}\end{figure}$

Approximate Expected Upper Bound, Approximate Expected Bound, Critical Task Execution Regions

In our example, task A2 has an enables non-local effect [Wagner97a] as well as a 25% chance of failure within its distribution. We hence predict that task A2 could potentially be a critical task execution region(CTER). A CTER is a set of possible outcomes of method execution which if occurred would seriously degrade the performance characteristics of the overall schedule. In order to understand the implications of this potential CTER, let us remove the failure possibility from the performance characterization of A2 and replace method A2's 25% chance of quality 0 by the expected value of the distribution. Method A2 hence is assigned a quality of 3, with a probability of 1 i.e. for method A2, Q (100% 3). The Design-to-Criteria scheduler is reinvoked with the modified task structure and rescheduled. The following are the ratings returned by the scheduler. $\{A1,A2^{success},A3\}$ : Rating 1.29 (Expected Quality)

Quality : (32% 0.5)(23% 1.0)(45% 2.0)
Duration: (100% 18)

{B} : Rating 0.6 (Expected Quality)
Quality: (20% 1) (80% 0.5)

The performance measure for the modified task structure is no longer the expected lower bound, instead it is the approximate upper bound as it describes the expectations if failure is not possible. The schedule {A1,A2,A3} now receives a rating of 1.29. The $\frac{1.29-0.97}{0.97}*100=33$ % improvement in quality with respect to the expected lower bound rating is significant. This 33% improvement in performance measure confirms that the possibility of failure of method A2 significantly decreases the rating of schedule {A1,A2,A3}. So now we consider the optional schedules for the original task structure to neutralize the effect of this CTER.

The tree structure in Figure 3 presents all the options of schedule generation that will meet the criteria of a duration limit of 18 minutes. From this diagram, we see that schedule {A1,A2,A3} does not have an option to reschedule and still meet the deadline, if method A2 produces an undesirable outcome.

So we consider a simple reordering of schedule {A1,A2,A3} which is {A2,A1,A3}. To assess the effects of rescheduling when A2 fails on this schedule {A2,A1,A3}, we combine the ratings for schedules $\{A2^{success},A1,A3\}$ and $\{A2^{failure},B\}$ based on their likelihoods of occurrence. So a schedule starting with A2 gets a rating of $\frac{75}{100}*1.29+\frac{25}{100}*0.60=1.1175.$ We use a similar analysis to get the values of schedules starting with A1 $=\frac{75}{100}*1.29+\frac{25}{100}*0=0.9675$ and B =1*0.60=0.60

This type of evaluation of the schedule is what we call the Approximate Expected Bound(AEB), which will be formally defined in the next section.

So schedule {A2,A1,A3} has a better expected performance than {A1,A2,A3}. The ELB computation of the Design-to-Criteria scheduler evaluates the performance measure of both {A1,A2,A3} and {A2,A1,A3} to be the same as it does not take into account the recovery options present within {A2,A1,A3} while evaluating it. This leads us to believe that the ELB perhaps is not the most appropriate performance measure for all task structures, particularly where hard deadlines or cost limits (in contrast to soft preferences) are important.

**Figure 4:** Statistical Performance of schedules with highest ELB and AEB
$\begin{figure}\begin{center}\begin{tabular}{cc}\epsfxsize=5cm \epsfbox{elb... ... &\epsfxsize=5cm \epsfbox{aeb.eps}\ \end{tabular}\end{center}\end{figure}$

The bar graph on the left of Figure 4 shows the statistical performance of the schedule with the highest ELB for 100 simulation runs, namely {A1,A2,A3}. A simulation run is a simulated execution of the schedule with highest ELB and the actual quality, cost and durations values are averaged over the number of simulations to obtain a statistical rating. We note that the schedule fails to achieve any quality about 20% of the time. The mean quality achieved by using this performance measure is 0.98.

The bar graph on the right Figure 4 describes the statistical performance data for the schedule with the highest AEB over 100 simulation runs, namely {A2,A1,A3}. Here 100 simulated executions of the schedule with the highest AEB rating produce the data. As seen in the histogram, the quality of the schedule with the best AEB rating is always a non-zero value due to the built-in contingency and the mean quality achieved here is 1.96.

Performance Measures

Formal definitions of the performance measures as well as the rescheduling and recovery algoritms can be found in [Raja98] and [Wagner98b].

Conclusions

The addition of uncertainty to the TÆMS modeling framework increases the accuracy of TÆMS models.
The uncertainty enhancement is leveraged ubiquitously by Design-to-Criteria scheduling to better statistically
reason about task interactions, to produce schedules that more fully satisfice to meet client's needs, and to
improve the efficiency of the scheduling process. We have discussed these issues and demonstrated the power
of using uncertainty in Design-to-Criteria scheduling. The issues of modeling improvement, measuring
uncertainty, reasoning about attribute trade-offs with uncertainty, and working to reduce uncertainty are all
applicable to research beyond Design-to-Criteria scheduling.

Currently we are investigating the use of contingency analysis to build better schedules. This work is
complimentary to the work presented here. Consider a situation where a highly uncertain action is embedded in
the middle of a schedule. Because of complex task interactions and the complex semantics of the functions that determine how quality is accumulated by tasks via their subtasks, determining the criticality of this highly
uncertain action is neither trivial nor computationally cheap. In some cases, a failure may negate any useful
work done to that point. In situations where hard deadlines are present, failure at that point may translate into
overall problem solving failure if the problem solver lacks sufficient time remaining to try a different solution
path. In hard deadline situations, it may be worthwhile to understand some of the downstream ramifications of a failure at that point and to attempt resequence the schedule accordingly - perhaps resulting in a lower quality
schedule that has more possible contingent schedules in the case of action failure. Without explicit
representation of uncertainty, this type of analysis would not be possible.

Another area of future uncertainty-related work in Design-to-Criteria scheduling involves leveraging the
uncertainty-chanced TÆMS models in multi-agent scheduling. In multi-agent systems the scheduler is
typically coupled with a multi-agent coordination module that forms commitments to perform work with other
agents; local concerns are thus modulated by non-local problem solving. Uncertainty in this context could be
used to reason about the utility of the commitments made with other agents and to understand how the
uncertainty about commitments made by other agents affects local problem solving.

Other, more general, future efforts in Design-to-Criteria will center around negotiation between the scheduler
and its clients, which may be other AI problem solvers or humans. Negotiation during the scheduling process
can iteratively refine client goal criteria based on what is actually being produced by the scheduler. This is
important because often if the scheduler cannot produce schedules that satisfice well enough with respect to the goal criteria, due to task limitations or resource constraints, the client may prefer to submit a different set of goal criteria and try again, exploring the solution space prior to selecting a course of action.

Related Publications

Mostafa, Hala; Lesser, Victor. Approximately Solving Sequential Games with Incomplete Information. Proceedings of the AAMAS�08 Workshop on Multi-Agent Sequential Decision Making in Uncertain Multi-Agent Domains, Shen, J.; Varakantham, P.; Maheswaran, R., ed., IFAAMAS, pp. 92-106. 2008.

Wagner, Thomas; Raja, Anita; Lesser, Victor. Modeling Uncertainty and its Implications to Sophisticated Control in TAEMS Agents. Autonomous Agents and Multi-Agent Systems, Volume 13, Number 3, Springer: Netherlands, pp. 235-292. 2006. On-line version available April 2006.

Raja, A.; Wagner, T.; Lesser, V. Reasoning about Uncertainty in Agent Control. Proceedings of the 5th International Conference on Information Systems, Analysis, and Synthesis, Computer Science and Engineering: Part 1, Volume VII, pp. 156-161. 2001.

Raja, Anita, Lesser, Victor, and Wagner, Thomas. Toward Robust Agent Control in Open Environments. Proceedings of 5th International Conference of Autonomous Agents(AA 2000). Also Umass CS Technical Report 1999-059, pp. 84-91. 2000.

Raja, Anita, Wagner, Thomas and Lesser, Victor. Reasoning about Uncertainty in Design-to-Criteria Scheduling. Proceedings of AAAI 2000 Spring Symposium on Real-Time Autonomous Systems, AAAI, pp. 76-83. 2000.

Wagner, Thomas; Raja, Anita; and Lesser, Victor. Modeling Uncertainty and its Implications to Design-to-Criteria Scheduling. UMASS Technical Report TR 1998-51, Number TR 1998-51, University of Massachusetts. 1999.

Raja, Anita, Wagner, Thomas, Lesser, Victor. Ensuring Robust Agent Control in Uncertain Environments.. University of Massachusetts Computer Science TR-99-027. 1999.

Xuan, Ping, Lesser, Victor. Incorporating Uncertainty in Agent Commitments. Intelligent Agents VI --- Proceedings of the Sixth International Workshop on Agent Theories, Architectures, and Languages (ATAL-99), Lecture Notes in Artificial Intelligence, N. R. Jennings and Y. Lesperance (eds.), Springer-Verlag, Berlin, pp. 57-70. 1999.