A new representation and associated algorithms for generalized planning

By Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein. 2011

101 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Reinforcement Learning

Citations in the corpus

Neural Logic Machines (2019, methodology): “General planning methods solve these tasks via planning based on rules (Hu & De Giacomo, 2011; Srivastava et al., 2011; Jiménez et al., 2019).”
Learning Features and Abstract Actions for Computing Generalized Plans (2018, methodology): “Generalized planning has also been formulated as a problem in ﬁrst-order logic (Srivastava, Immerman, and Zilberstein 2011), and general plans over ﬁnite horizons have been derived using ﬁrst-order regression (Boutilier, Reiter, and Price 2001; Wang, Joshi, and Khardon 2008; van Otterlo, M. 2012;…”
Model-free, Model-based, and General Intelligence (2018, background): “The task of computing solutions to families of planning problems, for example, all instances of Blocks world featuring blocks A and B where the goal is A on B, is called generalized planning [Srivastava et al., 2011; Hu and De Giacomo, 2011; Bonet et al., 2017].”
A review of generalized planning (2019, background): “The series of work by Srivastava et al. [90] on generalized planning encodes the eﬀects of actions with update formulas.”
Learning Generalized Reactive Policies using Deep Neural Networks (2017, unknown): “On the other hand, the literature on generalized planning (Srivastava, Immerman, and Zilberstein 2011; Hu and De Giacomo 2011) has focused on computing iterative generalized plans that solve broad classes of problem instances, with strong formal guarantees of correctness.”
Discovering State and Action Abstractions for Generalized Task and Motion Planning (2021, methodology): “We chose tasks that are physical instantiations of widely used tasks in generalized planning literature (Srivastava, Immerman, and Zilberstein 2011; Bonet, Francès, and Geffner 2018; Illanes and McIlraith 2019) or classically difficult TAMP domains with large numbers of objects.”