Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis
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.
Theoretical analysis of domain learning from justified (well- or perfectly justified) fully observed STRIPS traces, giving complexity results (P, coNP-complete, NP-complete, Sigma_2^P-complete).
Problem
Learning STRIPS action models (preconditions and effects) from fully observed plan traces that are justified (non-redundant); the computational complexity of deciding whether a consistent domain exists in which the trace is well- or perfectly justified, with and without expert-knowledge constraints,
Approach
Defines domain learning under well-justification and perfect justification, introduces a most-restrictive domain (lattice order on domains) that suffices for checking justification, and uses trace encodings and trace combination to prove complexity results, including that propositional constraints raise complexity to NP-complete or Sigma_2^P-complete.
Key results
- Deciding whether a domain exists in which a trace is well-justified is in P (Theorem 1).
- Deciding whether a domain exists in which a trace is perfectly justified is coNP-complete (Theorem 2).
- With arbitrary propositional constraints, well-justification becomes NP-complete and perfect justification becomes Sigma_2^P-complete (Theorems 3 and 4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require perfect rather than well-justification of the trace | Domain learning · Single-trace domain learning | computational complexity: P -> coNP-complete | Hurt |
| Add arbitrary propositional constraints on the domain | Well-justified domain learning · Single-trace domain learning | computational complexity: P -> NP-complete | Hurt |
| Add arbitrary propositional constraints on the domain | Perfectly justified domain learning · Single-trace domain learning | computational complexity: coNP-complete -> ΣP₂-complete | Hurt |
| Constrain the domain with a monomial instead of an arbitrary formula | Well-justified domain learning with expert constraints · Single-trace domain learning | computational complexity: NP-complete -> P | Helped |
| Constrain the domain with a monomial instead of an arbitrary formula | Perfectly justified domain learning with expert constraints · Single-trace domain learning | computational complexity: ΣP₂-complete -> coNP-complete | Helped |
Surprising findings
- Perfect justification of a plan cannot be checked efficiently unless P = NP, while well-justification can be checked in polynomial time.
Limitations
- Restricted to grounded classical STRIPS without negative preconditions or conditional effects.
- Assumes full observability of state variables and learning from a single trace (extended to multiple traces by combination).
- No empirical evaluation; purely theoretical.
Experimental setup
Builds on: STRIPS Fink and Yang plan justification Lin and Bercher domain modification safe action model (Stern and Juba)
Closest papers by meaning
- Differentiable Learning of Lifted Action Schemas for Classical Planning (NeurIPS 2026 · similarity 0.89)
- Learning Planning Abstractions from Language (ICLR 2024 · similarity 0.88)
- Learning Safe Action Models with Partial Observability (AAAI 2024 · similarity 0.87)
- Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans (AAAI 2025 · similarity 0.87)
- Interpreting Emergent Planning in Model-Free Reinforcement Learning (ICLR 2025 · similarity 0.87)
- SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge (AAAI 2024 · similarity 0.87)
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.