Risk-Aware Scheduling throughout Planning and Execution

Andrew J. WangAAAI 2015 · DOI

Abstract

Autonomous systems operating in complex environments face significant temporal uncertainty. Traditional scheduling methods often fail to account for these probabilistic disturbances, leading to brittle plans. This paper presents a framework for integrating chance-constrained scheduling across the planning and execution lifecycle. By employing an iterative, conflict-directed risk allocation approach, the proposed system achieves an order-of-magnitude speedup in generating robust scheduling policies with formal probabilistic guarantees.

Introduction

In large-scale logistics and manufacturing, such as airliner assembly or fleet management, temporal uncertainty is a fundamental challenge. Actions rarely take exactly the expected amount of time. When schedulers ignore this uncertainty, the resulting plans are often "brittle," requiring frequent and costly replanning when real-world disturbances occur.

To address this, risk must be managed throughout the entire system stack:

  1. Planning: Generating plans that are inherently schedulable under uncertainty.
  2. Scheduling: Creating policies that respect specific risk bounds (e.g., a 95% success probability).
  3. Dispatching: Monitoring real-time execution and triggering repairs when risk thresholds are breached.

Methodology: Conflict-Directed Risk Allocation

The core of the proposed approach is a "conflict-directed risk allocation" algorithm. Unlike global optimization methods that are computationally prohibitive, this framework treats risk as a resource to be allocated across sub-plans.

Chance-Constrained Formulation

The system utilizes chance constraints to satisfy specific bounds on the probability of constraint violation. This allows for a more nuanced approach than simple risk minimization, which often results in overly conservative behavior.

Iterative Master/Subproblem Structure

The algorithm decomposes the problem into a Master problem and a Subproblem:

  • Master Problem: Proposes candidate risk allocations (budgets) for different plan segments.
  • Subproblem: Validates these allocations using Simple Temporal Network with Uncertainty (STNU) controllability algorithms.

Conflict Discovery

When a risk allocation is found to be infeasible, the subproblem identifies the specific temporal conflicts responsible. These conflicts are fed back to the master problem to prune the search space in subsequent iterations, ensuring the problem remains manageable.

Architectural Integration

A key contribution of this work is the formal integration of risk awareness across the planning and execution layers.

The proposed architecture integrating risk-aware planning, scheduling, and dispatching.

As shown in Figure 1, the Planner receives high-level goals and produces a plan. The Scheduler then generates a policy based on this plan, which is passed to the Dispatcher. The Dispatcher executes specific actions while monitoring real-time risk, providing a feedback loop for repairs if necessary.

Experimental Results

The framework was evaluated using synthetic benchmarks common in temporal reasoning research, focusing on runtime performance as a function of problem complexity.

Performance comparison showing runtime scalability against the number of uncontrollable durations.

Speedup and Scalability

The conflict-directed approach demonstrates an order-of-magnitude speedup (approximately 10x) compared to traditional "min-risk" optimization methods. As illustrated in Figure 2, the runtime for the conflict-directed method remains relatively stable even as the number of uncontrollable durations—the primary source of uncertainty—increases. In contrast, traditional methods exhibit much sharper performance degradation.

Conclusion and Future Work

This research provides a scalable path toward robust, risk-aware autonomous systems. By treating risk as an allocatable resource and utilizing conflict-directed search, the system can generate reliable scheduling policies efficiently. Future work will focus on tighter integration with generative planners, developing incremental rescheduling techniques for on-the-fly policy updates, and fully implementing real-time dispatching with automated plan repair.

Summary updated

BibTeX
@inproceedings{wang2015risk,
  author = {Andrew J. Wang},
  title = {{Risk-Aware Scheduling throughout Planning and Execution}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9258},
}
Figure