Optimised Variants of Polynomial Compilation for Conditional Effects in Classical Planning


  • Francesco Percassi University of Huddersfield
  • Enrico Scala Università degli Studi di Brescia
  • Alfonso Emilio Gerevini Università degli Studi di Brescia




Conditional effects are a key feature in classical planning, enabling the description of actions whose outcomes are state-dependent. It is well known that the polynomial removal of conditional effects necessarily increases the size of a valid plan by a polynomial factor while preserving exactly the plan size requires an exponential encoding of the problem. The paper proposes and empirically evaluates optimisations for existing polynomial compilations. These optimisations aim to make the resulting compilations more suitable for planners while limiting the increase in plan size, which is inevitable if we want to keep the compilation polynomial. Specifically, the paper introduces a polynomial compilation technique that expands conditional effects when their number is below a certain threshold and sequentialises them otherwise. Additionally, the paper demonstrates that even straightforward optimisations can have a notable impact.