Generalized planning aims at computing solutions that work for all
instances of the same domain. In this paper, we show that several
interesting planning domains possess compact generalized heuristics
that can guide a greedy search in guaranteed polynomial time to the
goal, and which work for any instance of the domain. These heuristics
are weighted sums of state features that capture the number of objects
satisfying a certain first-order logic property in any given state.
These features have a meaningful interpretation and generalize
naturally to the whole domain. Additionally, we present an approach
based on mixed integer linear programming to compute such heuristics
automatically from the observation of small training instances. We
develop two variations of the approach that progressively refine the
heuristic as new states are encountered. We illustrate the approach
empirically on a number of standard domains, where we show that the
generated heuristics will correctly generalize to all possible
instances.
