Using Abstraction for Generalized Planning
Siddharth Srivastava
Neil Immerman
Shlomo Zilberstein
Abstract
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. We present novel approaches for learning, and
even finding such plans using state representation and abstraction
techniques originally developed for static analysis
of programs. The generalized plans that we compute include
loops and work for a large class of problem scenarios having
varying numbers of objects that must be manipulated to reach
the goal. Our algorithm for learning generalized plans takes
as its input an example plan for a certain problem instance
and a finite 3-valued first-order structure representing a set
of initial states from different problem instances. It learns a
generalized plan along with a classification of the problem instances
where it works. The algorithm for finding plans takes
as input a similar 3-valued structure and a goal test. Its output
is a set of generalized plans and conditions describing the
problem instances for which they work.
Download
[pdf]