Abstract
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