Not Everything Is Permitted: Constrained Cartesian Abstractions for Optimal Classical Planning

Building a single Cartesian abstraction is usually not enough to obtain an informative heuristic for classical planning. Therefore, state-of-the-art methods decompose the original task into subtasks-for example, one per goal atom-and compute an abstraction for each individual subtask. However, building a single abstraction suffers from diminishing returns, while building multiple abstractions loses information about how to achieve the associated subtasks jointly. We interpolate between these two extremes by first considering subtasks individually and then merging some of the resulting abstractions. We introduce an efficient algorithm for merging pairs of Cartesian abstractions using their refinement hierarchies and show that it yields more informative abstractions in less time than a naive approach. Furthermore, we prove that adding merged abstractions can only improve a cost-partitioned heuristic based on saturated posthoc optimization and that for maximal heuristic values, we need to keep the individual abstractions. Our experiments show that merging abstractions drastically improves the resulting heuristics.