Monotonic Variants of Saturated Cost Partitioning

Abstract

One of the strongest approaches for optimal classical planning is to compute multiple abstractions and combine them admissibly with cost partitioning. Ideally, a cost partitioning algorithm should be monotonic: refining an abstraction and adding it to the set of abstractions should never decrease any heuristic estimates. However, due to its greedy nature, the state-of-the-art saturated cost partitioning (SCP) algorithm lacks this monotonicity property. To address this, we introduce two algorithms that guarantee monotonicity for any cost partitioning scheme. Empirically, we show that the monotonic SCP variant outperforms standard SCP for Cartesian abstractions and pattern databases.