Research map / Learning theory and algorithms / Combinatorial and search optimization
On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence
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.
Studies the computational complexity of plan verification, bounded plan existence, and (bounded) plan optimality verification for grounded and lifted classical and HTN planning, filling gaps for lifted HTN planning.
Problem
Complexity of plan verification, bounded plan existence, and plan optimality verification in classical and HTN planning, especially lifted HTN planning, which had not been studied.
Approach
Derives complexity bounds via reductions and a general two-step guess-and-verify argument (Formula 1) that relates bounded plan existence to plan verification; shows plan optimality verification is the complement of bounded plan existence with the bound in unary, and that grounded HTN plan verification is NP-complete even with a primitive initial task network.
Key results
- Lifted HTN plan verification is PSPACE-hard and in NEXPTIME (Theorem 2), much harder than the grounded case.
- Grounded HTN plan verification is NP-complete even when the initial task network is primitive (Proposition 2).
- Bounded plan existence for grounded HTN planning with k in binary is NEXPTIME-complete (Theorem 3); with k in unary, grounded HTN is NP-complete (Theorem 5).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Represent HTN planning in lifted rather than grounded form | HTN plan verification · Plan verification | computational complexity | Mixed |
| Represent classical planning in lifted rather than grounded form | Classical k-length plan existence with k in binary · k-length plan existence, k in binary | computational complexity | Hurt |
| Represent HTN planning in lifted rather than grounded form | HTN k-length plan existence · k-length plan existence, k in binary | computational complexity | Hurt |
| Encode the bound k in unary rather than binary | Classical planning, grounded · k-length plan existence | computational complexity | Helped |
| Encode the bound k in unary rather than binary | Classical planning, lifted · k-length plan existence | computational complexity | Helped |
| Encode the bound k in unary rather than binary | HTN planning, grounded · k-length plan existence | computational complexity | Helped |
| Encode the bound k in unary rather than binary | HTN planning, lifted · k-length plan existence | computational complexity | Mixed |
| Represent HTN planning in lifted rather than grounded form | HTN plan optimality verification · Plan optimality verification | computational complexity | Hurt |
Surprising findings
- Grounded HTN plan verification remains NP-complete even with a primitive initial task network, a restricted special case.
- Lifted HTN plan verification is significantly harder than its grounded counterpart, reaching PSPACE-hardness.
Limitations
- Results are purely theoretical; no empirical evaluation.
- Lifted HTN bounds are not tight (PSPACE-hard vs. NEXPTIME membership gap for verification).
Experimental setup
Builds on: Bäckström and Jonsson 2011 unary bound complexity Behnke, Höller, and Biundo 2015 HTN plan verification Bylander 1994 plan existence complexity Erol, Hendler, and Nau 1996 HTN simulation of classical planning
Closest papers by meaning
- Symmetries and Other Variations of “End-Recursive” HTN Problems: Mapping the Border Between Decidable and Undecidable Restrictions (AAAI 2026 · similarity 0.92)
- HTN Plan Verification by Qualitative Temporal Reasoning (AAAI 2026 · similarity 0.91)
- totSAT - Totally-Ordered Hierarchical Planning Through SAT (AAAI 2018 · similarity 0.89)
- Counting and Reasoning with Plans (AAAI 2025 · similarity 0.86)
- An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types (AAAI 2025 · similarity 0.85)
- Symbolic Numeric Planning with Patterns (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.