Temporal Planning with Intermediate Conditions and Effects

Alessandro Valentini, Andrea Micheli, Alessandro Cimatti

Introduction

In automated temporal planning, the timing of events is as critical as the events themselves. Traditionally, the PDDL 2.1 standard has modeled actions as intervals where conditions and effects occur primarily at the boundaries (start or end) or as invariants throughout the duration. However, real-world industrial processes—such as chemical heating cycles or robotic assembly—often require Intermediate Conditions and Effects (ICE).

Modeling these in standard PDDL usually involves "clipping," a process of fragmenting long actions into multiple smaller ones. This approach exponentially increases search space complexity and degrades solver performance. This paper introduces the TAMER planner, designed to handle ICE natively through a specialized search engine and automated code generation.

Methodology

The authors propose a multi-faceted approach to overcome the limitations of traditional temporal planners:

  1. Native ICE Search Engine: Rather than compiling ICE into simpler primitives, the search space treats internal conditions and effects as discrete "time-point" events. A Simple Temporal Network (STN) is employed to symbolically manage timing constraints, ensuring mathematical feasibility without the overhead of artificial helper actions.
  2. STRIPS-based Heuristic Relaxation: To guide the search, the complex temporal problem is relaxed into a simpler classical planning problem. The progress of a durative action is represented as a "unary counter" of its internal events, allowing standard heuristics like $h_{add}$ to estimate the distance to the goal.
  3. Quasi-Domain-Dependent Code Generation: For industrial applications where the domain structure is static but problem instances vary, the authors developed a tool to generate specialized C++ source code. This "hard-codes" domain-specific logic, optimizing memory and execution speed.
The TAMER planner generation workflow, illustrating the compilation of domain-specific C++ source code.

Experimental Evaluation

The TAMER planner was evaluated against state-of-the-art solvers (e.g., OPTIC, TFLAP) across three benchmarks:

  • Temporal IPC-14: Standard benchmarks to verify general performance on problems without ICE.
  • MAJSP (Multi-Agent Job-Shop Scheduling): A domain requiring precise timing for item transport between machines.
  • PAINTER: A novel domain involving multi-coat painting with strict wait-time constraints between layers, making it exceptionally difficult to model without native ICE support.

Key Results and Insights

The results demonstrate that treating intermediate points as first-class citizens significantly improves efficiency. On the MAJSP and PAINTER domains, TAMER outperformed traditional tools by a wide margin.

Solving time performance on PAINTER (a) and MAJSP (b) domains, comparing TAMER variants against state-of-the-art planners.

The "deployment phase" optimization proved highly effective; the compiled version (COMP. TAMER) was approximately 243% faster than the standard version on average. In the PAINTER domain, it solved the most complex instances in seconds, whereas competitors frequently timed out. Furthermore, TAMER remained competitive on standard IPC benchmarks, indicating that the architectural support for ICE does not compromise performance on simpler temporal problems.

Conclusion and Future Work

TAMER demonstrates that native support for intermediate conditions and effects, combined with domain-specific compilation, provides a robust solution for complex scheduling tasks. Future work includes extending the search schema to support optimal planning (e.g., minimizing makespan) and refining heuristics with more sophisticated temporal relaxations. Additionally, the authors aim to explore further optimizations for self-overlapping actions to balance feature support with raw computational speed.

Summary updated

Abstract

Automated temporal planning is the technology of choice when controlling systems that can execute more actions in parallel and when temporal constraints, such as deadlines, are needed in the model. One limitation of several action-based planning systems is that actions are modeled as intervals having conditions and effects only at the extremes and as invariants, but no conditions nor effects can be specified at arbitrary points or sub-intervals. In this paper, we address this limitation by providing an effective heuristic-search technique for temporal planning, allowing the definition of actions with conditions and effects at any arbitrary time within the action duration. We experimentally demonstrate that our approach is far better than standard encodings in PDDL 2.1 and is competitive with other approaches that can (directly or indirectly) represent intermediate action conditions or effects.
BibTeX
@inproceedings{valentini2020temporal,
  author = {Alessandro Valentini and Andrea Micheli and Alessandro Cimatti},
  title = {{Temporal Planning with Intermediate Conditions and Effects}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6553},
}
Figure