Directed search for generalized plans using classical planners

We consider the problem of finding generalized plans for sit-uations where the number of objects may be unknown and unbounded during planning. The input is a domain specifi-cation, a goal condition, and a class of concrete problem in-first-order representation. Starting with an empty generalized plan, our overall approach is to incrementally increase the ap-plicability of the plan by identifying a problem instance that it cannot solve, invoking a classical planner to solve that prob-lem, generalizing the obtained solution and merging it back into the generalized plan. The main contributions of this pa-per are methods for (a) generating and solving small problem instances not yet covered by an existing generalized plan, (b) translating between concrete classical plans and abstract plan representations, and (c) extending partial generalized plans and increasing their applicability. We analyze the theoretical properties of these methods, prove their correctness, and il-lustrate experimentally their scalability. The resulting hybrid approach shows that solving only a few, small, classical plan-ning problems can be sufficient to produce a generalized plan that applies to infinitely many problems with unknown num-bers of objects.