Just-In-Case Scheduling

Mark Drummond, John L. Bresina, Keith SwansonAAAI 1994

Abstract

Just-In-Case (JIC) scheduling is an iterative algorithm designed to enhance the robustness of autonomous plans by proactively addressing the most probable execution failures. In real-world environments, such as autonomous telescope scheduling, action durations are inherently uncertain. JIC transforms an intractable stochastic reasoning problem into a practical tool by focusing on the most likely "breaks" in a schedule. This paper details the JIC methodology, which iteratively splits probability distributions at failure points to generate contingent plans, resulting in significant reliability gains with linear growth in schedule size.

Introduction: The Challenge of Real-World Uncertainty

In classical planning, actions are often assumed to have fixed durations. However, real-world applications—exemplified by NASA’s autonomous telescope scheduling—face significant temporal uncertainty. Telescopes operate within "enablement intervals," which are specific time windows where an observation is valid. If a preceding action takes longer than expected, the system may miss the start of the next window, causing the entire schedule to fail and halt execution.

Figure 1: Illustration of enablement intervals and temporal uncertainty in a schedule.

As shown in Figure 1, the cumulative effect of small delays can lead to a situation where the estimated finish time of an action falls outside the enablement interval of the subsequent task. While one could theoretically plan for every possible duration, the exponential growth of potential error cases makes complete contingency planning computationally intractable for complex schedules.

Methodology: The Just-In-Case Algorithm

The Just-In-Case (JIC) algorithm addresses this by acting as an iterative wrapper around an existing scheduler. Instead of solving for all contingencies simultaneously, it prioritizes the most likely failure points:

  1. Uncertainty Propagation: Using historical mean and standard deviation data, the algorithm estimates temporal uncertainty at each step.
  2. Weakest Link Identification: It identifies the action with the highest probability of finishing outside the next action's enablement window.
  3. Split and Conquer: The probability distribution at that "break point" is split into success and failure cases.
  4. Contingent Planning: The scheduler is re-invoked to create an alternative plan specifically for the failure case.
  5. Integration: This new plan is stitched into the original, creating a multiply contingent schedule.
Figure 2: The SPLIT operation in JIC, creating a new case to be covered by the scheduler.

Figure 2 illustrates the core SPLIT mechanism. By dividing the uncertainty interval for the finish time of an action ($A_{\beta(i)}$) at the boundary of the next action's ($A_i$) enablement interval, the algorithm creates a discrete new scenario for the scheduler to address.

Experimental Setup and Results

The algorithm was evaluated using real-world telescope scheduling data from the Fairborn Observatory. A simulator used Gaussian distributions based on these statistics to test the JIC-enhanced schedules.

Figure 6: Mean performance and schedule size as a function of the number of contingent cases covered.

As demonstrated in Figure 6, JIC provides rapid improvements in reliability. For a nominal schedule of 116 actions, covering just 10 contingent cases allowed the schedule to execute through 96% of the night on average. Crucially, the "size" of the schedule (the total number of stored actions) grew linearly with the number of cases covered, maintaining computational efficiency while dramatically increasing robustness.

Conclusion

Just-In-Case scheduling demonstrates that massive gains in reliability can be achieved by focusing on a small number of high-probability failure points—an application of the 80/20 rule to robustness. Future work may extend this philosophy to other domains, such as hardware failures or human absenteeism, where statistical models of "breaks" are available.

Summary updated

BibTeX
@inproceedings{drummond1994just,
  author = {Mark Drummond and John L. Bresina and Keith Swanson},
  title = {{Just-In-Case Scheduling}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure