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.
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.
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