Research map / Learning theory and algorithms / Combinatorial and search optimization
Symbolic Numeric Planning with Patterns
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Symbolic Pattern Planning (Patty), a bounded SMT encoding for linear numeric planning where a pattern (arbitrary action sequence) generalizes rolled-up and relaxed-relaxed-exists encodings, with provable dominance and experiments against IPC 2023 planners.
Problem
Solving linear numeric planning problems symbolically with bounded encodings that need fewer steps and smaller formulas than existing rolled-up and relaxed-relaxed-exists encodings.
Approach
Encode bounded planning using a pattern, an arbitrary action sequence in which actions may repeat, so each action's number of consecutive executions is an integer variable; the pattern encoding provably dominates the rolled-up and RRE encodings, and can be computed via an asymptotic relaxed planning graph.
Key results
- Patty finds plans at a bound lower than or equal to the other symbolic planners on every reported domain, consistent with the dominance theorem.
- Patty has the highest coverage together with ENHSP and the best average solving time on more domains than ENHSP, outperforming all planners on most Highly Numeric domains.
- Patty produces formulas with roughly the same number of variables as SpringRoll and far fewer than RRE, and fewer assertions than both at bound n=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Counters (L) | coverage (%): 60 -> 95 | Helped |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · HPower (S) | coverage (%): 25 -> 100 | Helped |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Pathways (S) | coverage (%): 5 -> 100 | Helped |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Rover (S) | coverage (%): 55 -> 85 | Helped |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Watering (S) | coverage (%): 100 -> 25 | Hurt |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Drone (S) | coverage (%): 85 -> 25 | Hurt |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Delivery (S) | coverage (%): 95 -> 25 | Hurt |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · MPrime (S) | coverage (%): 85 -> 55 | Hurt |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Satellite (S) | coverage (%): 30 -> 10 | Hurt |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Zeno (S) | coverage (%): 100 -> 55 | Hurt |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · BlGroup (S) | coverage (%): 100 -> 100 | No clear effect |
| Use Patty's pattern encoding instead of the strongest listed baseline | Symbolic numeric planning · Sailing (S) | coverage (%): 100 -> 100 | No clear effect |
Surprising findings
- Patty performs poorly relative to search-based planners on Lowly Numeric domains, since solutions there require bounds unreachable for symbolic planners.
Limitations
- Performance depends heavily on the chosen pattern; the ARPG-based pattern construction is a heuristic and needs improvement.
- Performs poorly on Lowly Numeric domains where solutions need large bounds.
- Experiments limited to a 5-minute time limit on a single machine with 8 GB RAM and Z3.
Experimental setup
Datasets: IPC 2023 numeric planning domains
Benchmarks: IPC 2023 numeric planning domains (Agile track) LineExchange
Metrics: coverage solving time bound number of variables number of assertions
Baselines: SpringRoll RRE encoding ENHSP MetricFF NumericFastDownward OMTPlan
Builds on: rolled-up encoding relaxed-relaxed-exists encoding Asymptotic Relaxed Planning Graph
Closest papers by meaning
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.90)
- Temporal Numeric Planning with Patterns (AAAI 2025 · similarity 0.90)
- PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning (AAAI 2025 · similarity 0.90)
- Graph Learning for Numeric Planning (NeurIPS 2024 · similarity 0.88)
- An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types (AAAI 2025 · similarity 0.87)
- On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.