Conditional effects are a key feature in classical planning, enabling the description of actions whose outcomes are statedependent. It is well known that removing conditional effects in a polynomial way necessarily increases the size of a valid plan by a polynomial factor. However, preserving the exact plan size requires encoding the problem exponentially. 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.
Optimised Variants of Polynomial Compilation for Conditional Effects in Classical Planning
Percassi F.;Scala E.;Gerevini A. E.
2024-01-01
Abstract
Conditional effects are a key feature in classical planning, enabling the description of actions whose outcomes are statedependent. It is well known that removing conditional effects in a polynomial way necessarily increases the size of a valid plan by a polynomial factor. However, preserving the exact plan size requires encoding the problem exponentially. 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.