Planning with Uncontrollable Action Durations

46 concepts35 papers

In classical automated planning, time is a well-behaved, deterministic line. A planner assumes that navigating between two rooms takes exactly 10 seconds, or that a mechanical arm requires precisely 5 seconds to solder a joint.

In the real world, this assumption falls apart. A robot navigating a crowded hallway experiences context-dependent delays due to human congestion, as noted by Street et al.. An autonomous vehicle encounters unpredictable traffic patterns (Osanlou et al.), a live interactive theater production must adapt to the whimsical pacing of human participants (Azad et al.), and physical hardware systems are bound by mandatory, uncontrollable environmental cycles like cooling or charging periods (Wang et al.).

When action durations are unpredictable, rigid schedules break. If a task takes slightly longer than expected, it can miss a critical synchronization window or violate a hard deadline downstream. To build robust systems, we must shift our perspective: planning is not about finding a static sequence of timestamps, but rather about designing a strategy that can withstand an unpredictable environment.

The Core Mechanism: Splitting Agency

The fundamental breakthrough in managing temporal uncertainty is the explicit partitioning of control. As formalized by Vidal et al. and Cimatti et al., a temporal plan is divided into two distinct classes of events:

  1. Controllable Events: Actions whose precise timing is decided entirely by the planner or executor (e.g., deciding exactly when to start a task).
  2. Uncontrollable (or Contingent) Events: Outcomes whose timing is determined by nature or external forces (e.g., when a robot actually finishes traveling through a door). The planner only knows that the duration will fall within a bounded interval or follow a specific probability distribution.

By separating these events, the planning problem transforms into a game against nature. The agent chooses the start times, and the environment chooses the durations. The goal is to prove that the agent can always win this game—meaning all temporal constraints will be satisfied regardless of how nature plays its hand.

The Spectrum of Controllability

To evaluate whether a plan is viable under this game-theoretic framing, researchers use different notions of controllability. These concepts define how much information the agent needs to successfully execute the plan.

Weak Controllability: The Clairvoyant Benchmark

A temporal network is Weakly Controllable if, for every possible combination of uncontrollable durations, there exists a valid schedule of controllable events.

Think of Weak Controllability as a clairvoyant benchmark: if an oracle told you exactly how long every unpredictable action would take before you started executing, could you assemble a valid schedule? Morris et al. settled a long-standing conjecture by proving that determining whether a schedule meets this criteria is NP-hard.

Because real-time execution doesn't afford us an oracle, Weak Controllability is primarily a theoretical baseline. However, the authors of Cimatti et al. demonstrated that Satisfiability Modulo Theory (SMT) solvers can practically verify Weak Controllability and extract piecewise-linear execution strategies, bridging the gap between theory and application.

Strong Controllability: One Size Fits All

On the opposite end of the spectrum lies Strong Controllability. A plan is Strongly Controllable if the agent can assign a single, fixed schedule to all controllable events that will succeed no matter what durations the environment selects (Cimatti et al.).

This approach requires no real-time adaptation. The planner finds an "island of certainty" or a massive buffer that absorbs all possible variance. While computationally appealing, Strong Controllability is highly restrictive; it often fails to find solutions in tightly constrained environments because it forces the agent to plan for the absolute worst-case scenario at every step.

Dynamic and Variable-Delay Controllability: Real-Time Adaptation

The most practical framework for real-world robotics is Dynamic Controllability, where the agent builds a reactive strategy. The timing of future controllable events is decided on the fly, depending entirely on the durations observed so far.

This becomes even more realistic when we acknowledge that information isn't instantaneous. Muise et al. introduced Variable-Delay Controllability, which accounts for the fact that an agent might only learn that an uncontrollable event has finished after an unpredictable, bounded communication delay.

How Planners Absorb the Shock

How do modern algorithms actually solve these problems without collapsing under the computational weight of uncertainty? They generally rely on three core paradigms:

1. Proactive Failure Analysis

Instead of calculating every possible future, some planners focus exclusively on the most fragile points of a schedule. Drummond et al. pioneered Just-In-Case (JIC) scheduling, which mathematically propagates duration statistics through a plan to locate where execution is most likely to fall outside valid windows. The system then proactively injects contingent branches only at these critical "breaks," transforming an intractable stochastic problem into a highly targeted optimization task.

2. Interleaving Deliberation and Execution

Rather than trying to generate a flawless, bulletproof plan offline, systems like IXTET-EXEC (Lemai et al.) interleave partial-order planning with real-time execution. The system continuously monitors contingent durations. If an action runs long and threatens a future constraint, the executive performs localized plan repair on the fly, resorting to expensive replanning from scratch only when a deadline is definitively breached.

3. Compiling Away Uncertainty

Another powerful approach is to translate the temporal uncertainty into structural choices that classical planners already know how to solve. For instance, the authors of Micheli et al. developed methods to "compile away" uncontrollable durations into strong temporal planning frameworks, allowing standard verification tools to synthesize robust control loops. Similarly, Venable et al. merged disjunctive scheduling ("either task A or task B must happen first") with uncontrollable durations, mapping out complex trade-offs mathematically to handle risk explicitly.

Why It Matters

When we stop treating time as a fixed constant and start treating it as a dynamic, bounded space shared between the agent and the environment, our systems become fundamentally more resilient. Whether managing concurrent stochastic tasks (Mausam), synchronizing multiple agents who cannot see each other's clocks (Brenner), or optimizing graph plans with an expected finite horizon (Doyen et al.), understanding temporal controllability allows AI to operate safely and predictably in an inherently unpredictable world.

Key Foundational Work

Just-In-Case Scheduling (1994) — contributed 2 concept elements to this direction.
A Language for Planning with Statistics (1991) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_temporal_uncertainty_d9dcb35a,
  title = {temporal uncertainty},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/temporal-uncertainty/rdr_d9dcb35a8e094af49b343552b95c2e0c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_temporal_uncertainty_d9dcb35a_v1,
  title = {temporal uncertainty},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/temporal-uncertainty/rdr_d9dcb35a8e094af49b343552b95c2e0c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake