This project is developing automated methods of artificial intelligence (AI) for creating generalized 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 is to reason about plans with loops and to do so without using automated theorem proving, which tends to be intractable. In particular, research is accomplishing the following 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; (5) extend the framework to include sensing actions, conditional plans, and domain-specific knowledge in the form of partially specified plans; (6) create a new set of challenging benchmark problems and perform a rigorous evaluation of the approach; and (7) 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. This new framework may significantly improve the scope and applicability of automated planning systems.
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 an 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 most 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. If similar planning problems are likely to be encountered, why not directly search for plans that work for a large class of similar problems? Generalized planning is designed specifically to address that key challenge. When this project began, there was no unified view of what generalized planning means. There was no evaluation method for generalized plans. There was very limited theoretical understanding of the aspects of the problem that are tractable and how to create generalized plans with well-defined applicability conditions. The community of researchers interested in this problem had not been interacting regularly. This project contributed significantly to each one of these aspects. The main outcome of the project is 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 respect is reasoning about plans with loops, without resorting to theorem proving, which tends to be intractable. The project produced the following results: (1) new theoretical foundations for generalized planning; (2) effective abstraction mechanisms and new plan representations to support these new capabilities; (3) effective algorithms for plan synthesis as well as generalization of sample plans; (4) analysis tools to reason about the applicability, correctness and efficiency of generalized plans; (5) extensions of the framework to include sensing actions, conditional plans, and domain-specific knowledge in the form of partially specified plans; and (6) a set of new challenging benchmark problems. Thus, the intellectual merit of this project includes foundational contributions to the field of automated planning. The new approach improves planning technology along three key dimensions. First, it addresses the challenge of plan reuse by providing methods for plan generalization and generalized plan synthesis. The solution resolves an important open problem regarding the ability to find such plans with their preconditions without using theorem proving. Second, it addresses the challenge of planning under uncertainty by allowing sensing actions to be used for determining state properties. Finally, it addresses the challenge of planning with numeric variables by using a powerful abstraction mechanism to model uncertainty in state properties as well as unknown quantities of objects and resources. The broader impact of the project stems from the wide applicability of the resulting planning technology; the educational impact at UMass Amherst that includes undergraduate and graduate student training and curriculum development; extensive dissemination efforts, making the new plan representation and algorithms available to the research community; and enhancing existing international collaborations, particularly with program verification researchers.
