Research map / Learning theory and algorithms / Combinatorial and search optimization
An Effective Polynomial Technique for Compiling Conditional Effects Away
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 COCOA, a polynomial compilation that removes conditional effects from classical planning by exploiting an effect interference graph, and shows it outperforms Gazen–Knoblock and Nebel compilations in optimal planning for several planners.
Problem
Classical planning with conditional effects is hard to handle: planners often lack native support, and existing compilations either blow up exponentially (Gazen and Knoblock) or lengthen plans polynomially with many extra atoms and actions (Nebel).
Approach
Builds an effect interference graph per action, makes it acyclic by greedily choosing a small feedback propositional set whose conditions are replaced by twin atoms set by a setup action, then compiles the acyclic effects into simple actions ordered by a topological sort, yielding a smaller polynomial encoding than Nebel's.
Key results
- COCOA achieves more coverage than GKCOMP and NCOMP for all planners except COMPLEMENTARY2, where GKCOMP is better; the best configuration is COCOA with METIS2 (1045 problems in total coverage row).
- Compiled NCOMP instances are on average 6.2 times larger than COCOA instances in number of actions and 4.1 times larger in atoms.
- For METIS2, COCOA vs PLAIN shows strong complementarity (319 problems solved by COCOA but not PLAIN), while for A*(hmax) native PLAIN dominates with no complementarity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use COCOA instead of NCOMP | Optimal planning systems · Σ (1608) | coverage: 529 vs 132; 742 vs 212; 617 vs 101; 860 vs 316 | Helped |
| Use COCOA instead of GKCOMP | Optimal planning systems · Σ (1608) | coverage: 529 vs 478; 742 vs 541; 617 vs 649; 860 vs 687 | Mixed |
| Use COCOA instead of PLAIN native conditional-effect support | Optimal planning systems · Σ (1608) | coverage: 529 vs 650; 742 vs 828; 617 vs 703; 860 vs 596 | Mixed |
Surprising findings
- GKCOMP expands fewer nodes than COCOA in general, yet its runtime is often worse on instances with many conditional effects, because its compilation is exponential.
- Native support is generally faster than compilations, yet COCOA complements native planners on METIS2.
Limitations
- Optimal acyclicity requires solving an NP-complete feedback set problem, so a greedy approximation is used, introducing pre-processing overhead.
- Compiled plans are longer than with GKCOMP, which preserves plan length, leading to worse hLM-cut performance.
- Evaluation is limited to optimal planning settings with Fast Downward-based planners.
Experimental setup
Datasets: Fast Downward benchmark collection conformant-to-classical planning compilation benchmarks (Palacios and Geffner 2009; Grastien and Scala 2017) domains from Röger, Pommerening, and Helmert 2014
Benchmarks: collected planning domains with conditional effects
Metrics: coverage expanded nodes runtime complementarity (pairwise solved-set differences)
Baselines: GKCOMP NCOMP PLAIN (native CE support)
Builds on: Nebel's compilation of conditional effects Gazen and Knoblock compilation LM-cut heuristic Fast Downward
Closest papers by meaning
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.88)
- Optimizing the Optimization of Planning Domains by Automatic Action Schema Splitting (AAAI 2024 · similarity 0.86)
- When CEGAR Meets Regression: A Love Story in Optimal Classical Planning (AAAI 2024 · similarity 0.86)
- Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis (AAAI 2024 · similarity 0.85)
- Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans (AAAI 2025 · similarity 0.84)
- An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types (AAAI 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.