Executive Summary
CRIKEY3 represents a significant advancement in automated planning, being the first to fully support the complex temporal semantics of PDDL2.1 (Level 3) alongside numeric resource management. By introducing a novel integration of snap-action heuristics and temporal scheduling, CRIKEY3 solves "required concurrency" problems—scenarios where actions must overlap or self-overlap to achieve a goal—that were previously beyond the reach of state-of-the-art planners.
The Challenge of Temporal Coordination
Traditional temporal planning often relies on "compressed" representations, treating durative actions as atomic blocks. While computationally efficient, this approach fails in domains requiring intricate temporal coordination. The authors identify two critical gaps in existing planners:
- Required Concurrency: Problems where a goal can only be achieved if specific actions occur simultaneously (e.g., extracting coal only while a mine is actively "open").
- Self-Overlapping Actions: Scenarios in numeric domains where multiple instances of the same action (e.g., "charge battery") must run concurrently to meet a resource threshold within a strict deadline.
Methodology: Snap Actions and STNs
CRIKEY3 addresses these challenges by decomposing durative actions into "start" and "end" snap actions. This decomposition allows the planner to interleave other tasks during the execution of a long-running action.
The system interleaves state-space search with a scheduling phase using Simple Temporal Networks (STN). This ensures that the timestamps assigned to snap actions remain consistent with required durations and logical dependencies. Furthermore, the authors introduced the Temporal Relaxed Planning Graph (TRPG), a heuristic that respects PDDL2.1 semantics by ensuring "end" effects are only considered available after an action's minimum duration has elapsed. To optimize performance, CRIKEY3 employs Inevitable Cycle Pruning to detect temporal contradictions early in the search process.
Evaluation and Key Results
The planner was evaluated against standard benchmarks (IPC3 Driverlog, IPC4 Satellite, and PipesWorld) and a custom "Coal Mining" domain designed to test required concurrency and numeric resource management.
Performance and Expressivity
- Competitive Performance: On standard benchmarks, CRIKEY3 performed competitively with the Sapa planner. Despite the increased search space caused by action splitting, the TRPG heuristic provides accurate guidance, keeping time-to-solution comparable to simpler planners.
- Superior TIL Support: In the PipesWorld domain involving Timed Initial Literals (TILs), CRIKEY3 solved 16 problems, significantly outperforming TIL-SAPA, which solved only 2.
- Handling Overlap: CRIKEY3 is uniquely capable of handling self-overlapping actions in both propositional and numeric domains, where previous planners like VHPOP often produced invalid plans.
- Scalability: In the numeric coal mining domain, the planner demonstrated sub-exponential scaling as production requirements increased, proving its robustness for complex resource tasks.
Conclusion and Future Directions
CRIKEY3 demonstrates that simplifying temporal actions into STRIPS-like blocks is a loss of expressivity that limits real-world applicability. While splitting actions increases branching complexity, the integration of STNs and the TRPG heuristic makes complex temporal coordination tractable. Future work will focus on extending these techniques to PDDL+ semantics, including continuous numeric effects like steady fuel consumption.
Summary updated