Advisable Planners

A research project funded by the ARPA/Rome Laboratory Planning Initiative.

Principal Investigator:
Dr. Karen L. Myers
AI Center
SRI International

Executive Summary

Research in AI planning has focused on the development of fully automated techniques for generating plans that satisfy high-level user goals. These methods take a description of the domain along with a set of initial goals, and produce a solution consisting of a set of actions that when executed in the initial state is guaranteed to satisfy the specified goals. These approaches make no provision for users to participate in the planning process. For many applications this design is problematic, since users are reluctant to relinquish full control to an automated system.

The principal objective of the Advisable Planners project was to make AI planning technology more accessible and controllable through a model based on advisability. User-provided advice would specify characteristics for both the desired solution and the problem-solving process to be employed during plan generation. Such advice would be specified in a high-level language that is natural and intuitive for users, then operationalized into constraints that would direct the underlying planning technology during plan construction. As such, the advice-taking interface would allow users to interact with the automated planner at high levels of abstraction in order to guide and influence the planning process, with the system performing the time-consuming work of filling in necessary low-level details and detecting potential problems.

Within this project, we explored two main types of advice. Strategic advice constitutes recommendations on how tasks are to be accomplished, in terms of approaches and entities to be used. Strategic advice is constructed from a domain metatheory that captures key semantic properties of objects in the underlying planning domain. We developed a formal model for satisfaction of strategic advice within hierarchical task network planners, along with corresponding algorithms for advice enforcement. To accommodate conflicting advice, we developed a range of advice relaxation techniques suited to different modes of user interaction.

Plan sketches provide a second form of advice through the specification of individual tasks, possibly spanning multiple abstraction levels, that are to be included in the overall plan. We developed a method for plan sketch completion that expands user-provided sketches to complete solutions. This approach employs abductive plan recognition techniques to generate possible explanations for the inclusion of the elements within a plan sketch, then expands and refines the sketch in order to provide a final plan that is grounded in those explanations.

When faced with planning tasks in complex application domains, humans like to understand the space of options available to them. Our models of advice enable a user to explore the space of possible solutions in a flexible, interactive manner. To complement these methods, we developed a capability for automatically generating sets of qualitatively distinct plans based on analysis of the domain metatheory that is used to construct advice. This capability can be used to generate an initial set of seed solutions, which users can subsequently refine through the application of strategic advice. This combination of techniques enables users to rapidly identify solutions that are well-suited to their particular needs and preferences.

Advisable Planner System
A prototype Advisable Planner system was developed that incorporates our models and algorithms for advisability. The system consists of an advice-taking interface layered on top of the Sipe-2 planning system.

Publications

"Planning with Conflicting Advice", K. L. Myers, in Proceedings of the Fifth International Conference AI Planning and Scheduling (AIPS2000), AAAI Press, Menlo Park, CA, 2000.

"Domain Metatheories: Enabling User-Centric Planning", K. L. Myers, in Proceedings of the Workshop Representational Isses for Real-World Planning Systems (AAAI-2000), AAAI Press, Menlo Park, CA, 2000.

"Generating Qualitatively Different Plans through Metatheoretic Biases", K. L. Myers, and T. J. Lee, in Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI-99), AAAI Press, Menlo Park, CA, 1999.

"Abductive Completion of Plan Sketches", K. L. Myers, in Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), AAAI Press, Menlo Park, CA, 1997.

"Strategic Advice for Hierarchical Planners", K. L. Myers, in Principles of Knowledge Representation and Reasoning: Proceedings of the Fifth International Conference (KR '96), Morgan Kaufmann Publishers, San Francisco, CA, 1996.

"Using Advice to Influence Problem-Solving", K. L. Myers, in Proceedings of the AAAI Spring Symposium on Acquisition, Learning and Demonstration: Automating Tasks for User, AAAI Press, Menlo Park, CA, 1996.

"Advisable Planning Systems", K. L. Myers, in Advanced Planning Technology, edited by A. Tate, AAAI Press, Menlo Park, CA, 1996.

"User Guide for the Advisable Planner", K. L. Myers, Technical Report, Artificial Intelligence Center, SRI International, Menlo Park, CA.