Modeling Domain Independent Planning to Advance Application

This project is sponsored by National Science Foundation under grant # IIS-0138690. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Project Description

Planning underlies any complex human endeavor -- from organizing a busy life to operating a large airline or testing large software systems. In each case, we need to track an enormous number of details, marshal resources and ensure that actions necessary to achieve our goals can be taken in a timely matter. However, automated planning has had little effect on how planning is actually accomplished.

Research on domain independent planning has made significant gains in recent years, as indicated by the emergence of several new techniques and considerable increases in the size of problems that can be solved. Unfortunately, those advances have not yet translated into many new applications or an understanding of what constitutes the best technique. On the contrary, we have evidence from several large scale comparisons that suggests that not all planners will do well on a particular domain, we have little evidence of how planners perform on realistic problems, and we have little understanding of why and when particular planners and planner types work well.

The key question that we propose to study is: What planner works well when? We propose to construct a metaplanner that will allow us to test performance of existing and hybridized planners on a suite of domains, especially more realistic domains. Based on the results of our studies, we will develop predictive models of planner performance that translate problem and domain features to estimates of how much time would be needed by a given planner to solve the problem. The models, in turn, will be operationalized in the metaplanner.

This research will extend some previous work in applying planning to automated software test generation. In that project, we were unable to find a single planner that could manage the scale of the application; consequently, we constructed a prototype metaplanner to schedule the efforts of six planners. While quite limited in the number of planners and the types of information it used to select from them, the metaplanner still showed promise for solving a broader set of problems in less than average time.

We propose to assist the transition to applications through three contributions. First, with the help of colleagues, we will collect and develop applications and realistic domains to augment the current benchmark set. Second, we will model the performance of state of the art planners, some new simplified, heuristic planners and some component combinations of planners on these new problems. The models will highlight the strengths and weaknesses of the planners and point out needed directions for research. Third, we will significantly enhance our metaplanner, which is directed by the models to select a planner to solve a particular domain/problem.  

People

We are part of the Artificial Intelligence Group in the Computer Science Department of Colorado State University.