Research map / Learning theory and algorithms / Combinatorial and search optimization
PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning
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.
Adapts pattern-database (PDB) heuristics to optimal simple numeric planning by bounding infinite numeric projections via partial progression search, and combines PDBs admissibly (iPDB, systematic patterns, canonical heuristic) in Numeric Fast Downward.
Problem
Optimal classical-style PDB heuristics have never been applied to numeric planning, because projections onto numeric variables yield infinite state spaces, so regression-based PDB construction fails.
Approach
Construct PDBs over a finite sub-LTS obtained by progression from the abstract initial state up to a state limit, with fringe states given admissible minimum-action-cost estimates; combine pattern collections with the canonical heuristic and adapt iPDB and systematic pattern generation using numeric intervals and causal graphs.
Key results
- Numeric iPDB reduces expansions by up to six orders of magnitude relative to finite-domain iPDB, and beats blind search and hmax-based heuristics in coverage (numeric PDBs total 311 vs. blind 203 out of 635 instances).
- Numeric PDBs fall short of OPC and LMc in total coverage, trailing LMc by 61 instances (LMc 303 vs. 311 for iPDB... see table: LMc 303, OPC 216, iPDB 311 total).
- iPDB solves 24 more minecraft instances than the best of the compared baselines in the two minecraft variants, while lagging on farmland and sailing.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use numeric variables in iPDB patterns rather than ignoring all numeric variables (ablation) | iPDB · Numeric planning benchmarks | state expansions | Helped |
| Use numeric iPDB instead of blind search | A* search · Numeric planning benchmarks | state expansions | Helped |
| Use numeric iPDB instead of LM-cut | A* search · Numeric planning benchmarks | state expansions | Mixed |
| Use numeric iPDB instead of LM-cut | A* search · All benchmarks | coverage (solved instances): 311 vs. 250 | Hurt |
| Use numeric iPDB instead of blind search | A* search · minecraft-pogo and minecraft-sword | coverage (solved instances): 14 -> 18; 20 -> 20 | Mixed |
| Use numeric iPDB instead of LM-cut | A* search · farmland (IPC 2023) | coverage (solved instances): 15 -> 4 | Hurt |
| Use numeric iPDB instead of operator counting | A* search · sailing (IPC 2023) | coverage (solved instances): 9 -> 0 | Hurt |
| Use numeric iPDB instead of operator counting | A* search · All benchmarks | coverage (solved instances): 303 vs. 250 | Hurt |
| Use numeric iPDB instead of finite-domain iPDB (ablation) | iPDB · Numeric planning benchmarks | state expansions | Helped |
Surprising findings
- Finite-domain iPDB that ignores numeric variables performs similarly to single-pattern numeric PDBs, but numeric iPDB is much better overall.
Limitations
- Canonical PDB heuristics with numeric PDBs do not match the total coverage of LM-cut and operator counting.
- Fringe states without computed distances use minimum action cost approximations, and unexpanded abstract states lead to lookup misses; bounds are not sound in general.
Experimental setup
Datasets: IPC 2023 simple numeric benchmarks numeric planning benchmarks from literature (counters, depots, farmland, sailing, petri-net, rover-unit, satellite, zeno forestfire (new) minecraft (new, 20 advanced instances per variant)
Benchmarks: IPC 2023 numeric track domains literature numeric benchmarks forestfire minecraft-pogo minecraft-sword
Metrics: coverage expansions until last f-layer runtime time score lookup miss percentage
Baselines: blind search imax rmax LM OPC LMc finite-domain iPDB
Builds on: pattern databases iPDB Numeric Fast Downward LM-cut for numeric planning structurally restricted numeric fragments
Closest papers by meaning
- Temporal Numeric Planning with Patterns (AAAI 2025 · similarity 0.90)
- Symbolic Numeric Planning with Patterns (AAAI 2024 · similarity 0.90)
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.89)
- Dealing with Numeric and Metric Time Constraints in PDDL3 via Compilation to Numeric Planning (AAAI 2024 · similarity 0.88)
- Graph Learning for Numeric Planning (NeurIPS 2024 · similarity 0.87)
- Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code (NeurIPS 2025 · similarity 0.86)
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.