Given the complexity of planning, it is often beneficial to create plans that work for a wide class of problems. This facilitates reuse of existing plans for different instances of the same problem or even for other problems that are somehow similar. In this talk I will present a novel approach for finding such plans using state representation and abstraction techniques originally developed for static analysis of programs.
Our algorithm takes as input a finite 3-valued first-order structure representing a set of initial states and a goal test. The output is a set of "generalized plans" and conditions describing the problem instances for which they work. These plans can include loops, and are infact close to algorithms: they work for a large class of problem scenarios having varying numbers of objects that must be manipulated to reach the goal. We identify the class of domains where our approach is currently applicable, and also show how this framework can be used to learn a general plan from examples.
This is joint work with Neil Immerman and Shlomo Zilberstein.