Foundations and Applications of Generalized Planning

Sponsored by:
National Science Foundation, Division of Information & Intelligent Systems
Award Number 0915071

Shlomo Zilberstein, PI
Neil Immerman, CoPI

Project Description

Automated planning -- the ability to reason about the course of actions necessary to achieve one's goals -- is the hallmark of intelligence and a core area of AI research. While there has been tremendous progress with the efficiency and scope of planning systems over the past 30 years, there has been little progress with the deeper representational and algorithmic challenges. For example, a simple handwritten plan to deliver any number of crates to any number of destinations using a truck cannot be constructed by existing planners because it includes a loop. Clearly, once a plan for delivering 7 crates is found, one should not search from scratch for a plan for delivering 8 or 10, or even a thousand crates. From the early work on plan generalization using triangle tables to more recent efforts in case-based and explanation-based planning, researchers have developed mechanisms to apply existing plans to new situations. This project takes these efforts to a new level: if similar planning problems are likely to be encountered, why not directly search for plans that work for a large class of similar problems?

We develop a new framework for creating generalized plans -- algorithm-like plans that include loops and branches, can handle unknown quantities of objects, and work for large classes of problem instances. One of the key challenges in this project is to reason about plans with loops and to do so without using theorem proving, which tends to be intractable. We have developed a comprehensive approach to overcome this problem and accomplish the following set of goals: (1) develop new theoretical foundations for generalized planning; (2) develop effective abstraction mechanisms and new plan representations to support these new capabilities; (3) develop effective algorithms for plan synthesis as well as generalization of sample plans; (4) develop analysis tools to reason about the applicability, correctness and efficiency of generalized plans; and (5) extend the framework to include sensing actions, conditional plans, and domain-specific knowledge in the form of partially specified plans; rigorous evaluation of the approach. Another goal of the project is to increase the interaction between the AI community and other communities, particularly model checking, that study the abstraction mechanisms and theoretical foundations necessary for generalized planning.

At the core of the approach is a powerful abstraction methodology that was developed originally for static analysis of programs, and implemented as a system called TVLA. TVLA provides a method of modeling an infinite set of similar configurations using a single, finite three-valued structure. We have shown how to extend TVLA's abstraction mechanism to reason about unbounded sets of configurations of planning problems. One key component of the approach can automatically derive loops in which measurable progress is made toward the goal, even as the plan returns to the same abstract state. Another key component identifies the overall effects of sequences and loops of actions in order to determine the preconditions under which certain paths will be followed. These new capabilities address some of the hardest longstanding challenges in automated planning.

Useful Links

Related Publications

  • Qualitative Planning under Partial Observability in Multi-Agent Domains.

    R.I. Brafman, G. Shani, and S. Zilberstein. Proceedings of the Twenty-Seventh Conference on Artificial Intelligence (AAAI), 130-137, Bellevue, Washington, 2013. [abs] [bib] [pdf]

  • Multiagent Planning, Control, and Execution.

    E. Durfee and S. Zilberstein. In G. Weiss (Ed.), Multiagent Systems, Second Edition, 485-546, MIT Press, 2013. [abs] [bib] [pdf]

  • Applicability Conditions for Plans with Loops: Computability Results and Algorithms.

    S. Srivastava, N. Immerman, and S. Zilberstein. Artificial Intelligence, 191:1-19, 2012. [abs] [bib] [pdf]

  • A New Representation and Associated Algorithms for Generalized Planning.

    S. Srivastava, N. Immerman, and S. Zilberstein. Artificial Intelligence, 175(2):615-647, 2011. [abs] [bib] [pdf]

  • Directed Search for Generalized Plans Using Classical Planners.

    S. Srivastava, N. Immerman, S. Zilberstein, and T. Zhang. Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling (ICAPS), 226-233, Freiburg, Germany, 2011. [abs] [bib] [pdf]

  • Qualitative Numeric Planning.

    S. Srivastava, S. Zilberstein, N. Immerman, and H. Geffner. Proceedings of the Twenty-Fifth Conference on Artificial Intelligence (AAAI), 1010-1016, San Francisco, California, 2011. [abs] [bib] [pdf]

  • Termination and Correctness Analysis of Cyclic Control.

    S. Srivastava, N. Immerman, and S. Zilberstein. Proceedings of the Twenty-Fifth Conference on Artificial Intelligence (AAAI Nectar Track), 1567-1570, San Francisco, California, 2011. [abs] [bib] [pdf]

  • Merging Example Plans into Generalized Plans for Non-deterministic Environments.

    S. Srivastava, N. Immerman, and S. Zilberstein. Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1341-1348, Toronto, Canada, 2010. [abs] [bib] [pdf]

  • Computing Applicability Conditions for Plans with Loops.

    S. Srivastava, N. Immerman, and S. Zilberstein. Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS), 161-168, Toronto, Canada, 2010. [abs] [bib] [pdf]

  • Challenges in Finding Generalized Plans.

    S. Srivastava, N. Immerman, and S. Zilberstein. ICAPS Workshop on Generalized Planning: Macros, Loops, Domain Control, Thessaloniki, Greece, 2009. [abs] [bib] [pdf]

  • Finding Plans with Branches, Loops and Preconditions.

    S. Srivastava, N. Immerman, and S. Zilberstein. ICAPS Workshop on Verification and Validation of Planning and Scheduling Systems, Thessaloniki, Greece, 2009. [abs] [bib] [pdf]

  • Abstract Planning with Unknown Object Quantities and Properties.

    S. Srivastava, N. Immerman, and S. Zilberstein. Proceedings of the Eighth Symposium on Abstraction, Reformulation and Approximation (SARA), Lake Arrowhead, California, 2009. [abs] [bib] [pdf]

  • Learning Generalized Plans Using Abstract Counting.

    S. Srivastava, N. Immerman, and S. Zilberstein. Proceedings of the Twenty-Third Conference on Artificial Intelligence (AAAI), 991-997, Chicago, Illinois, 2008. [abs] [bib] [pdf]

  • Using Abstraction for Generalized Planning.

    S. Srivastava, N. Immerman, and S. Zilberstein. Proceedings of the Tenth International Symposium on Artificial Intelligence and Mathematics (ISAIM), Ft. Lauderdale, Florida, 2008. [abs] [bib] [pdf]

shlomo@cs.umass.edu
UMass Amherst