A New Representation and Associated Algorithms for Generalized Planning

Siddharth Srivastava, Neil Immerman, and Shlomo Zilberstein. A New Representation and Associated Algorithms for Generalized Planning. Artificial Intelligence, 175(2):615-647, 2011.

Abstract

Constructing plans that can handle multiple problem instances is a longstanding open problem in AI. We present a framework for generalized planning that captures the notion of algorithm-like plans and unifies various approaches developed for addressing this problem. Using this framework, and building on the TVLA system for static analysis of programs, we develop a novel approach for computing generalizations of classical plans by identifying sequences of actions that will make measurable progress when placed in a loop. In a wide class of problems that we characterize formally in the paper, these methods allow us to find generalized plans with loops for solving problem instances of unbounded sizes and also to determine the correctness and applicability of the computed generalized plans. We demonstrate the scope and scalability of the proposed approach on a wide range of planning problems.

Bibtex entry:

@article{SIZaij11,
  author	= {Siddharth Srivastava and Neil Immerman and Shlomo Zilberstein},
  title		= {A New Representation and Associated Algorithms for Generalized Planning},
  journal	= {Artificial Intelligence},
  volume	= {175},
  number	= {2},
  year		= {2011},
  pages		= {615-647},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/SIZaij11.html}
}

shlomo@cs.umass.edu