Representing Perfect Saturated Cost Partitioning Heuristics in Classical Planning

Saturated cost partitioning (SCP) is one of the strongest

methods for admissibly combining heuristics for optimal

classical planning. The quality of an SCP heuristic depends

heavily on the order in which its component heuristics are

considered. For high accuracy, it is essential to maximize

over multiple SCP heuristics computed using different

component orders. However, for n component heuristics, even

enumerating all n! orders is usually infeasible.

Consequently, previous work resorted to using greedy

algorithms and local optimization. In contrast, we present

the first practical method for computing the perfect SCP

heuristic that is equivalent to considering all component

orders. We show that a set of SCP heuristics forms an

additive disjunctive heuristic, which allows us to

concisely represent component orders as a directed acyclic

graph. Furthermore, once certain components have been

considered, the order of the remaining components often

becomes irrelevant. By exploiting this characteristic, we

can reduce the size of the heuristic representation by

several orders of magnitude in practice. Finally, our work

makes it possible to compare the quality of existing SCP

methods with that of the perfect SCP heuristic, revealing

that existing approximations are nearly optimal for

standard benchmarks.