Abstract
Temporal numeric planning involves finding valid action sequences in environments where actions have durations, can overlap, and interact with numeric variables. This paper introduces $PATTY_T$, a new SMT-based planner that extends the Symbolic Pattern Planning (SPP) framework. By employing pattern-based encodings and a novel "rolling durative actions" mechanism, $PATTY_T$ can represent multiple action executions within a single transition. Experimental results across ten complex domains demonstrate that $PATTY_T$ significantly outperforms existing state-of-the-art planners, achieving higher coverage and finding plans with substantially fewer discrete steps.
1. Introduction
Automated planning in temporal numeric domains (PDDL 2.1 level 3) is a challenging task, often proving undecidable in general cases. A primary difficulty for symbolic planners—which translate planning problems into Satisfiability Modulo Theories (SMT) formulas—is the "step-by-step" nature of traditional encodings. If a solution requires many repetitions of an action or complex overlapping behaviors (required concurrency), the resulting SMT formulas become prohibitively large.
This research addresses these bottlenecks by introducing $PATTY_T$, a planner designed to handle concurrency and numeric constraints more efficiently through pattern-based reasoning.
2. Methodology
The core of $PATTY_T$ is the extension of the Symbolic Pattern Planning (SPP) framework to the temporal numeric setting.
2.1 Pattern-Based Encoding
Unlike standard encodings that process one action per step, $PATTY_T$ uses "patterns"—pre-computed sequences of action starts and ends. This allows the SMT solver to reason about complex interactions within a single state transition, effectively "dominating" traditional encodings by requiring a lower or equal bound $n$ to find a solution.
2.2 Rolling Durative Actions
A key innovation is the "rolling" of durative actions. If an action does not interfere with its own execution, $PATTY_T$ can represent executing that action $p$ times consecutively as a single mathematical operation in the SMT formula. This drastically compresses the search space, allowing the planner to solve problems with a bound of $n=1$ that might otherwise require $n=100$ or more.
2.3 Temporal and Numeric Constraints
The encoding incorporates $\epsilon$-separation to ensure actions are temporally distinct and handles "lasting" conditions directly within the pattern logic. The system is formally proven to be both sound (finding only valid plans) and complete (eventually finding a plan if one exists).
3. Experimental Evaluation
The performance of $PATTY_T$ was evaluated against several state-of-the-art planners, including $ANMLSMT$, $ITS_{AT}$, $LPG$, $OPTIC$, and $TFD$. The test suite consisted of 10 domains characterized by required concurrency:
- Classic Benchmarks: CUSHING, MATCHAC, MATCHMS, OVERSUB, and PAINTER.
- New/Modified Domains: POUR, SHAKE, PACK, BOTTLES, and MAJSP, designed to test intricate numeric interactions like simultaneous uncapping and pouring.
4. Results and Discussion
$PATTY_T$ demonstrated superior performance across nearly all metrics. It achieved the highest coverage in 9 out of 10 domains, solving a total of 157 out of 200 problems, whereas the next best planner, $ANMLSMT$, solved 98.
As shown in the table above, $PATTY_T$ is particularly effective in domains like POUR and BOTTLES, where other planners often fail entirely. Furthermore, the "Bound (Common)" column highlights the efficiency of the pattern-based approach; $PATTY_T$ consistently finds plans at much lower bounds than its competitors. For instance, in CUSHING, $PATTY_T$ finds a solution at bound 3.00, while $ANMLSMT$ requires a bound of 11.33.
4.1 Limitations
The planner faced challenges in the PAINTER domain, where it was slightly outperformed by $ANMLSMT$. This is attributed to the encoding generating a higher number of numeric variables, which increased the SMT solver's workload. Additionally, the current "rolling" mechanism is optimized for linear numeric effects; extending this to non-linear dynamics remains a subject for future work.
5. Conclusion
$PATTY_T$ represents a significant advancement in temporal numeric planning. By leveraging symbolic patterns and rolling action executions, it overcomes the scalability issues of traditional SMT-based encodings. Its ability to handle required concurrency and complex numeric constraints makes it a powerful tool for modern automated planning tasks.
Summary updated