Generalized Planning: Synthesizing Plans that Work for Multiple Environments
Yuxiao Hu and Giuseppe De Giacomo
Generalized planning, where a single plan works for multiple planning problems, has recently been drawing increasing attention in the planning community. In this paper, we give, possibly for the first time, a formal definition of generalized planning that is independent of any representation formalism. We assume that our generalized plans must work on a set of deterministic environments, which are essentially unrelated to each other. We prove that generalized planning for a finite set of environments is always decidable and EXPSPACE-complete (as conditional planning under partial observability with deterministic operators, which turn out to be a special case of our notion of generalized planning). Our proof is constructive and gives us a sound, complete and computationally optimal technique. Interestingly, our technique is based on compilation into classical planning. We also consider infinite sets of environments, and show that generalized planning for the infinite ``one-dimensional problems,'' known in the literature to be recursively enumerable when restricted to finite-state plans, is in fact EXPSPACE-decidable in general, and solvable by generalized planning for finite sets.