An Effective Polynomial Technique for Compiling Conditional Effects Away

Alfonso Emilio Gerevini, Francesco Percassi, Enrico ScalaAAAI 2024 · DOI

In automated planning, conditional effects (CEs) allow for the modeling of actions with state-dependent outcomes—for instance, a switch that toggles a light's state. While expressive, CEs pose significant challenges for modern planners, which often lack native support or struggle to compute efficient heuristics when they are present. This paper, presented at AAAI-24, introduces COCOA (COmpiling COnditional effects Away), a novel polynomial-time compilation technique that transforms problems with CEs into standard STRIPS problems while maintaining search efficiency.

The Problem with Existing Compilations

Researchers traditionally handle CEs through either native support or compilation. Existing compilations, however, face a difficult trade-off:

  • GKCOMP: Preserves plan length but can lead to an exponential explosion in the number of actions.
  • NCOMP (Nebel’s compilation): Avoids exponential growth but "stretches" plans significantly, adding a massive number of auxiliary actions and atoms that slow down the search.

COCOA addresses the primary weakness of NCOMP: its "blindness" to the actual dependencies between effects. NCOMP treats every effect as if it might interfere with every other, leading to unnecessary bloat. The authors found that NCOMP's approach produced problems that were, on average, 6.2 times larger in terms of actions and 4.1 times larger in terms of atoms compared to COCOA.

The COCOA Methodology

The core innovation of COCOA is the Effect Interference Graph. For every action, the authors construct a directed graph where nodes represent individual conditional effects. An edge exists from effect A to effect B if the outcome of A modifies a variable used in the condition of B.

Handling Dependencies

  • Acyclic Graphs: If the interference graph is acyclic, the effects can be applied in a specific linear order. COCOA generates a sequence of simple actions following this order.
  • Breaking Cycles: For cyclic dependencies (e.g., A affects B and B affects A), COCOA identifies a Minimal Feedback Propositional Set (MFPS). It uses a small set of "twin atoms" to temporarily store state values, effectively breaking the cycles and allowing for a linear compilation.
  • Optimization: Unlike previous methods that separate condition evaluation from effect application, COCOA performs them simultaneously whenever possible, resulting in significantly shorter plans in the compiled space.

Key Results and Performance

The authors evaluated COCOA against GKCOMP, NCOMP, and native support (PLAIN) across a broad suite of benchmarks using four different optimal planners.

Comparison of COCOA against GKCOMP and NCOMP in terms of expanded nodes and runtime (log10 scale). Points below the diagonal favor COCOA.

As illustrated in the scatter plots above, COCOA consistently outperforms NCOMP, requiring fewer node expansions and less runtime. Compared to the exponential GKCOMP, COCOA demonstrates superior scalability as the number of conditional effects per operator increases, avoiding the catastrophic failures associated with action explosion.

Coverage comparison across different optimal planners ($A^*(h^{max})$, $A^*(h^{LM-cut})$, COMPL2, and METIS2).

The coverage results (the number of problems solved within a time limit) highlight COCOA's robustness. While native support is often fastest for simple heuristics, COCOA is highly competitive. Notably, for the METIS2 planner—which utilizes symmetry breaking—using COCOA actually resulted in better performance than the planner's native CE handling. This suggests that COCOA's structured encoding allows advanced planners to exploit problem symmetries more effectively.

Conclusion

COCOA provides a powerful new tool for the planning community, offering a concise polynomial compilation that bridges the gap between exponential length-preserving methods and bloated polynomial alternatives. By exploiting the inherent dependency structure of conditional effects, it enables off-the-shelf optimal planners to handle complex domains with significantly improved efficiency. Future work may explore integrating interference graph logic directly into native heuristic calculations to create "CE-aware" solvers.

Summary updated

BibTeX
@inproceedings{gerevini2024effective,
  author = {Alfonso Emilio Gerevini and Francesco Percassi and Enrico Scala},
  title = {{An Effective Polynomial Technique for Compiling Conditional Effects Away}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.29989},
}

Loading related content...

Figure