Research map / Large language models / Agents, code and math
Counting and Reasoning with Plans
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.
Introduces quantitative and qualitative reasoning over polynomially bounded plan spaces (counting, probability, facet reasoning), and the Planalyst tool that compiles planning into SAT and d-DNNF for plan counting.
Problem
Classical planning typically seeks one plan or enumerates plans, but quantitative reasoning over the plan space (counting plans, conditional probabilities of operators) is largely unexplored and counting is computationally hard.
Approach
Encode bounded-length planning tasks as propositional formulas whose models correspond one-to-one to plans, compile them into d-DNNF via knowledge compilation, and answer counting, probability, and facet queries via polynomial-time d-DNNF traversal; also introduces facets (operators that are brave but not cautious) as an easier-to-compute significance notion.
Key results
- On the 1.0 length bound, Count solves 335 tasks versus K* 351 and SymK 309; at the 1.5 bound Count solves 170 versus K* 112 and SymK 91.
- Count has the highest coverage for bounds 1.1 to 1.5, and the gap grows as bounds increase.
- In blocksworld the largest solved task had 1.5e9 plans and in psr-small 8.9e12 plans, while K* counted only up to about 10 million plans in these domains.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Planalyst Count instead of K* for plan counting | IPC planning benchmark suite · Length bounds ×1.0 to ×1.5 | coverage: ×1.0: 351 vs 335; ×1.1: 289 vs 300; ×1.2: 212 vs 251; ×1.3: 177 vs 210; ×1.4: 142 vs 189; ×1.5: 112 vs 170 | Mixed |
| Use Planalyst Count instead of SymK for plan counting | IPC planning benchmark suite · Length bounds ×1.0 to ×1.5 | coverage: 309 vs 335; 231 vs 300; 173 vs 251; 135 vs 210; 112 vs 189; 91 vs 170 | Helped |
| Additionally enumerate all plans rather than only counting them | Planalyst · IPC planning benchmark suite, length bounds ×1.0 to ×1.5 | coverage: 253 vs 335; 182 vs 300; 130 vs 251; 101 vs 210; 77 vs 189; 61 vs 170 | Hurt |
Surprising findings
- Enumeration (Enum) ranks last overall, even though counting via d-DNNF scales to plan spaces where enumeration becomes infeasible.
- K* outperforms the SAT-based Count approach at the tightest length bound (1.0) on coverage.
Limitations
- SAT encoding (Madagascar-based sequential encoding) is not concise enough for some domains, e.g., airport.
- Grounding by Madagascar fails for some tasks such as organic-synthesis.
- Restricted to polynomially bounded plan lengths and unit operator costs; the paper reports no empirical results for the d-DNNF queries beyond counting.
Experimental setup
Datasets: IPC optimal planning domains 1998-2023 (unit cost, no conditional effects or axioms) planning.domains bounds
Benchmarks: IPC optimal planning domains (1094 tasks across 30 domains)
Metrics: coverage number of plans counted
Baselines: K* SymK
Builds on: Madagascar d4 ddnnife top-quality planning
Closest papers by meaning
- On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence (AAAI 2024 · similarity 0.86)
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.85)
- ACPBench: Reasoning About Action, Change, and Planning (AAAI 2025 · similarity 0.85)
- Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning (AAAI 2024 · similarity 0.85)
- Symbolic Numeric Planning with Patterns (AAAI 2024 · similarity 0.85)
- On the self-verification limitations of large language models on reasoning and planning tasks (ICLR 2025 · similarity 0.84)
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.