From Projections to Cartesian Abstractions and Merge-and-Shrink: Comparing the Compactness of Abstraction Representations

Abstract

The four major classes of state space abstractions in classical planning are projections, domain abstractions, Cartesian abstractions and merge-and-shrink abstractions. We study the representations for these classes through the lens of compactness: one class is at least as compact as another if it can represent all abstractions the other can represent with a polynomially bounded increase in representation size. We complete the picture of compactness relationships among the four classes of abstractions, in particular resolving an open question from the literature on the relative compactness of Cartesian abstractions and merge-and-shrink.