Optimised Variants of Polynomial Compilation for Conditional Effects in Classical Planning

Abstract

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.