State-Dependent Cost Partitionings
for Cartesian Abstractions in Classical Planning
Abstract
guide optimal search algorithms in classical planning. Cost partitionings allow to sum heuristic estimates admissibly by distributing action costs among the heuristics. We introduce statedependent cost partitionings which take context information of actions into account, and show that an optimal state-dependent cost partitioning dominates its state-independent counterpart. We demonstrate the potential of our idea with a statedependent variant of the recently proposed saturated cost partitioning, and show that it has the potential to improve not only over its stateindependent counterpart, but even over the optimal state-independent cost partitioning. Our empirical results give evidence that ignoring the context of actions in the computation of a cost partitioning leads to a significant loss of information.