Time-Critical Scheduling in Stochastic Domains

Lloyd G. Greenwald, Thomas DeanAAAI 1994

Abstract

This paper addresses the challenges of scheduling in high-stakes, stochastic environments where traditional Markov Decision Process (MDP) solvers fail due to combinatorial action spaces and divergent state trajectories. We present a framework that integrates AI planning with Operations Research (OR) heuristics, utilizing time-window partitioning and dispatch rules to create an anytime algorithm suitable for time-critical decision-making. By focusing on bottleneck detection and deliberation scheduling, the proposed method provides a scalable approach to managing uncertainty in complex domains like airport gate assignment.

Introduction

In classical stochastic planning, researchers often employ Markov Decision Processes (MDPs) to determine an optimal policy—a comprehensive mapping of actions to every possible state. While effective for problems like robot navigation, this approach falters in scheduling domains. In environments such as airport management, the sheer volume of possible actions and the unpredictable nature of events (e.g., weather delays or mechanical failures) create a state space that is too vast for exhaustive search. This paper explores a hybrid methodology that combines the robust uncertainty modeling of AI with the efficient search heuristics of Operations Research.

The Challenges of Stochastic Scheduling

Scheduling problems present two primary hurdles that distinguish them from typical navigation tasks:

  1. Combinatorial Action Spaces: In a busy airport, assigning $N$ planes to $M$ gates at any given moment creates a staggering number of possible actions. Iterating through every permutation to find the optimal assignment is computationally infeasible under real-time constraints.
  2. Divergent Trajectories: In navigation, different paths often converge (e.g., multiple routes leading to the same hallway). In scheduling, decisions tend to diverge. A minor delay at a gate early in the morning creates a "ripple effect," leading to a future state that is fundamentally different from one where no delay occurred. This lack of state "merging" makes traditional state-space pruning techniques, such as envelopes, less effective.

Proposed Methodology

The authors propose a two-phase iterative procedure designed to prune the search space without sacrificing the ability to handle uncertainty.

Time-Window Partitioning

Rather than clustering related states based on physical proximity, the algorithm partitions the problem along the time dimension. This approach captures the temporal context of the schedule more effectively, allowing the system to focus on immediate decisions while maintaining a window into future implications.

Selective Exploration via Dispatch Rules

To mitigate the "action explosion," the system avoids evaluating every possible assignment. Instead, it utilizes greedy dispatch rules—common in Operations Research—such as "Earliest Deadline First." These rules suggest a limited set of promising actions, significantly narrowing the branching factor of the search tree.

Monte Carlo Simulation and Refinement

The algorithm uses these dispatch rules to conduct Monte Carlo simulations on a stochastic model, identifying the most probable reachable states. Following this, a bottleneck-centered refinement phase identifies points where the schedule is likely to fail or cause significant tardiness. The system then adds constraints to subsequent iterations to proactively avoid these pitfalls.

Deliberation Scheduling

Recognizing that time is a finite resource, the framework employs an "anytime" approach. Through deliberation scheduling, the system manages its own computational effort, balancing the time spent simulating future scenarios against the time spent refining the current plan. This ensures that a valid, high-quality schedule is always available, regardless of when the deadline occurs.

Key Insights

  • Navigation vs. Scheduling: A crucial contribution of this work is the distinction between physical state-space navigation and temporal scheduling. In scheduling, states are neighbors in time, and actions lead to disjoint futures, necessitating a shift in how we approach state-space exploration.
  • AI and OR Synergy: The paper bridges the gap between AI’s strength in stochastic modeling and OR’s strength in handling massive search spaces via heuristics. This hybrid approach allows for "reflexes"—default actions for low-probability states that were not explicitly covered during the simulation phase.

Conclusion and Future Work

The framework provides a robust architecture for handling the combinatorial explosion of action spaces in stochastic domains. While the effectiveness of the approach is dependent on the quality of the chosen dispatch rules, it offers a scalable path forward for time-critical scheduling. Future research will focus on refining the quality-time tradeoffs to better allocate processing power between simulation and refinement phases, further enhancing the system's responsiveness in dynamic environments.

Summary updated

BibTeX
@inproceedings{greenwald1994time,
  author = {Lloyd G. Greenwald and Thomas Dean},
  title = {{Time-Critical Scheduling in Stochastic Domains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure