Compiling Away Uncertainty in Strong Temporal Planning with Uncontrollable Durations

Andrea Micheli, Minh Do, David E. SmithIJCAI 2015

Automated planning in real-world environments must account for inherent temporal uncertainty. Whether it is a Mars rover navigating unpredictable terrain or a satellite coordinating communication windows, action durations are rarely fixed. This paper, originally presented at IJCAI 2015, introduces a novel compilation technique that transforms temporal planning problems with uncertain durations into deterministic ones, allowing researchers to leverage existing, highly optimized planners.

The Challenge of Uncontrollable Durations

In standard temporal planning, actions are often assumed to have fixed durations. However, in practice, an action like "drive to location B" might take anywhere from 10 to 15 minutes depending on wheel slip or obstacles. Standard approaches often fail by being either too risky (planning for the average case) or too conservative (planning only for the worst case).

The authors address Strong Temporal Planning with Uncontrollable Durations (SPPTU). The objective is to find a single sequence of actions and fixed start times—a "strong" plan—that is guaranteed to succeed for every possible duration within a specified range $[d_{min}, d_{max}]$. This is particularly difficult when plans must satisfy both upper-bound constraints (e.g., finishing before an orbiter passes) and lower-bound constraints (e.g., arriving after the sun has set).

Methodology: The Compilation Approach

The core innovation is a sound-and-complete compilation that translates temporal uncertainty into state-space robustness. Instead of developing a custom solver, the authors "compile away" the uncertainty using three key mechanisms:

  1. Shadow Variables: For every state variable $f$ affected by an uncertain action, a corresponding shadow variable $f_\sigma$ is created.
  2. State Divergence: When an action with an uncertain end time begins, the system enters a period of "state divergence." The shadow variable $f_\sigma$ is updated at the earliest possible completion time, while the original variable $f$ is updated at the latest possible time.
  3. Robust Conditions: Any condition relying on variable $f$ is modified to require that both $f$ and $f_\sigma$ satisfy the condition. This ensures the plan remains valid regardless of when the transition actually occurs within the uncertain window.
The compilation process transforms a standard action into a 'shadowed' version to account for state divergence during uncertain intervals.

By stretching action durations to their maximum and requiring conditions to hold across the entire interval of uncertainty, the planner is forced to find a solution that is robust to any timing variance.

Experimental Evaluation and Results

The method was evaluated using 563 PDDL benchmarks and expressive ANuML domains, including rover operations and multi-robot handovers. The researchers compared their compilation approach (using planners like COLIN and POPF) against existing techniques such as Disjunctive Reordering (DR) and Last Achiever Deordering (LAD).

Cumulative time versus the number of solved instances across different planning approaches.

The results demonstrate that the compilation approach is highly effective. While it introduces some overhead by doubling the number of state variables, it remains competitive with specialized solvers. Crucially, the performance was found to be complementary: the compilation method solved many complex instances that deordering-based methods could not, and vice versa. This suggests that compilation is a vital component of a robust planning portfolio.

Conclusion and Future Work

By treating temporal uncertainty as a state-space divergence problem, this research provides a bridge between complex, uncertain real-world requirements and the mature field of deterministic temporal planning. While current PDDL 2.1 limitations (such as the need for "clip-actions") can create search depth bottlenecks, the underlying logic is sound and complete. Future work aims to integrate this compilation logic directly into hybrid planners to eliminate PDDL-specific performance overhead and extend the framework to support conditional effects.

Summary updated

BibTeX
@inproceedings{micheli2015compiling,
  author = {Andrea Micheli and Minh Do and David E. Smith},
  title = {{Compiling Away Uncertainty in Strong Temporal Planning with Uncontrollable Durations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure