Planning and Meta-Planning (MOLGEN: Part 2) Mark Stefik (PARC, Xerox) 1. Introduction * There exists the need for reasoning control and a control structure. 2. The Rationale for Layers 2.1 The trouble with agendas * Fixed order (order of the tasks being generated) * Priority (fixed) * Scheduler (dynamic priority) * All are at the agenda side, not the interpreter side 2.2 Recognizing the meta-problem * Goal at the meta-level is to find a solution to the problem. Main Points The research seeks to enhance the power of problem solvers by enabling them to reason about their own reasoning process. The paper argues that the organization of a problem solver can be simplified by partitioning problem solving knowledge into layers. It describes a control structure, termed meta-planning, which enables a planner to reason (to some degree) about its own reasoning process. A control structure is a framework for organizing decisions on when actions of a plan can be applied and how they should be combined. A sophisticated control structure should: 1. Take advantage of new information 2. Make guesses and correct mistakes 3. Should be able to recognize when an approach is succeeding 4. Recognize when an approach is failing 5. Decide what action to try 6. Know when to make commitments and when to wait Meta-Planning provides framework for partitioning control knowledge into layers so that flexibility is achieved. The paper considers the control of decision making in planning. A computer program, named MOLGEN, was used to study planning. The Meta-Problem Many of the important actions, goals, and constraints can be characterized as being on a meta-level Any choices or evaluation criteria, which relate to the process of problem solving, can be characterized as meta-level considerations. Monolithic agenda approaches provide no meta-level concepts or global prospective for scheduling and arbitration. A Model for Planning Features A trivial finite-state machine as the top-level interpreter The factoring of the knowledge for using plausible and logical reasoning from the planning operations The development of a vocabulary of operators and concepts for hierarchical planning with constraints Three layers and an interpreter Laboratory space: Describes what can be done in the laboratory, but not when to do it in an experiment. Design Space: Execute steps in order to create and refine the laboratory plan Strategy space: Execute steps to create and execute the steps in the design space. Interpreter: Outer control loop Creates and executes steps in the strategy space The design operators plan by creating and scheduling laboratory steps The strategy operators "meta-plan" by creating and scheduling design steps MOLGEN Laboratory Space Model of the objects and actions relevant to gene cloning experiments Define the set of possible laboratory experiments by describing the allowable laboratory objects and operators. Operators represent physical process that can be carried out in the genetics laboratory Organized in four groups (Merge, Amplify, React, sort) Design Space Contains operators for planning Planning can be viewed as operations on constraints (formulation, propagation, and satisfaction) Strategy Space and Interpreter Strategy space is organized as four strategy operators: Focus - Used to create and execute new design tasks Resume - Restarts suspended design steps Guess - Sends a guess message to the operator of every suspended design step. Undo - The strstegy operator for backtracking when a plan has become over-constrained When MOLGEn has run out of least-commitment changes to a plan, it looks for a plausible commitment that will allow it to continue with the design process. This is recognized by MOLGEN when the Focus and Resume strategy operators have nothing to do.