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