Robust Execution of Probabilistic Temporal Plans

Kyle Lund, Sam Dietrich, Scott Chow, James C. BoerkoelAAAI 2017 · DOI

Abstract

In multi-agent systems such as automated warehouses, coordinating tasks under durational uncertainty is a critical challenge. While Simple Temporal Networks (STNs) provide a framework for scheduling, they often fail to account for the probabilistic nature of real-world task durations. This paper addresses the Robust Execution Problem (REP) by introducing two algorithms: the Static Robust Execution Algorithm (SREA) and the Dynamic Robust Execution Algorithm (DREA). SREA provides a theoretically grounded offline schedule, while DREA leverages real-time feedback to dynamically re-optimize execution. Experimental results demonstrate that DREA significantly improves success rates over traditional methods, achieving up to a fourfold increase in robustness in complex scenarios.

The Challenge of Durational Uncertainty

In automated environments, robots must coordinate tasks where durations are inherently uncertain—for instance, a robot might slip on a warehouse floor or encounter unexpected obstacles. This creates a "Robust Execution Problem" (REP): how can we schedule tasks to maximize the probability of satisfying all temporal constraints?

Consider a scenario where Robot A takes approximately 6 minutes to navigate and Robot B takes 2 minutes, but they must arrive within a 2-minute window of each other. Traditional temporal planning uses Simple Temporal Networks (STNs) to manage these constraints, but these models typically focus on "flexibility" (slack in the schedule) rather than "robustness" (the actual probability of success). Probabilistic STNs (PSTNs) improve upon this by modeling uncertainty using probability density functions (PDFs), as shown in Figure 1.

A Probabilistic Simple Temporal Network (PSTN) representing two robots with uncertain task durations and a synchronization constraint.

Algorithmic Solutions: SREA and DREA

The authors propose two primary strategies to bridge the gap between theoretical plans and successful real-world execution:

1. Static Robust Execution Algorithm (SREA)

SREA is an offline approach that uses a Linear Programming (LP) formulation to find a "strongly controllable" schedule. It performs a binary search to identify the optimal risk level ($\alpha$), representing the probability mass an agent is willing to sacrifice to ensure the remainder of the schedule remains feasible. This provides a guaranteed theoretical lower bound on the probability of success before execution begins.

2. Dynamic Robust Execution Algorithm (DREA)

DREA is the paper's flagship contribution. It is an online algorithm that monitors execution in real-time. Whenever a task finishes or a new timepoint becomes "enabled," DREA re-runs the SREA optimization. This allows the system to be opportunistic: if a robot finishes early, DREA "banks" that extra time to increase the robustness of future tasks. Conversely, if a task runs long, it gracefully adjusts the remaining schedule to minimize the impact. This iterative process is illustrated in Figure 2.

The dynamic execution process of DREA, showing real-time re-optimization as tasks complete and feedback is received.

Experimental Evaluation

The algorithms were evaluated using a random robot navigation problem generator. The test PSTNs typically featured 20 timepoint variables across 2 to 4 agents, with 20 to 35 constraints. Durations were modeled using normal distributions with varying standard deviations to simulate different levels of environmental "noise."

Key Results

  • Success Rates: In a warehouse simulation, a baseline "early execution" strategy (starting tasks as soon as possible) achieved a success rate of only 17.21%. SREA improved this to 24.61%, but DREA achieved a massive jump to 68.04%.
  • Benchmark Performance: Across various levels of agent synchronization and constraint density, DREA consistently maintained the highest success rates, outperforming both standard dynamic controllability and static approaches.
  • Computational Efficiency: Despite its dynamic nature, DREA remains practical for real-time robotics. While SREA takes approximately 872ms to compute initially, individual updates during DREA execution typically occur in under 0.5 seconds.

Discussion and Future Work

A key insight from this research is that robustness is inextricably linked to the dispatch strategy—the logic used to trigger events. DREA succeeds because it combines the proactive hedging of SREA with the reactive agility of real-time execution.

However, limitations remain. The current approach assumes a centralized dispatcher, and the authors suggest that decentralized methods for multi-agent plans are a vital next step. Additionally, while the system handles normal distributions well, future work will explore more complex, multi-modal distributions common in highly unpredictable real-world environments.

Summary updated

BibTeX
@inproceedings{lund2017robust,
  author = {Kyle Lund and Sam Dietrich and Scott Chow and James C. Boerkoel},
  title = {{Robust Execution of Probabilistic Temporal Plans}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11019},
}

Loading related content...

Figure