Using Abstraction for Generalized Planning

Siddharth Srivastava, Neil Immerman, and Shlomo Zilberstein. Using Abstraction for Generalized Planning. Proceedings of the ICAPS Workshop on Artificial Intelligence Planning and Learning, Providence, Rhode Island, 2007.

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.

Bibtex entry:

@inproceedings{SIZicaps07ws,
  author	= {Siddharth Srivastava and Neil Immerman and Shlomo Zilberstein},
  title		= {Using Abstraction for Generalized Planning},
  booktitle     = {Proceedings of the {ICAPS} Workshop on Artificial Intelligence
                   Planning and Learning},
  year		= {2007},
  pages		= {},
  address       = {Providence, Rhode Island},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/SIZicaps07ws.html}
}

shlomo@cs.umass.edu