Foundations and Applications of Generalized Planning
National Science Foundation,
Division of Information & Intelligent Systems
Award Number 0915071
Shlomo Zilberstein, PI
Neil Immerman, CoPI
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.
- AAAI 2011 Workshop on Generalized Planning
- ICAPS 2009 Workshop on Generalized Planning: Macros, Loops, Domain Control
- Qualitative Planning under Partial Observability in Multi-Agent Domains.
- Multiagent Planning, Control, and Execution.
- Applicability Conditions for Plans with Loops: Computability Results and Algorithms.
- A New Representation and Associated Algorithms for Generalized Planning.
- Directed Search for Generalized Plans Using Classical
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.
- Termination and Correctness Analysis of Cyclic
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
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.
- Challenges in Finding Generalized Plans.
- Finding Plans with Branches, Loops and Preconditions.
- Abstract Planning with Unknown Object Quantities and Properties.
- Learning Generalized Plans Using Abstract Counting.
- Using Abstraction for Generalized Planning.