M. Stefik, Planning and Meta-Planning (MOLGEN: Part 2). Artificial Intelligence 16 (2), 1981.

Author of the summary: Yaxin Liu, 1999, yxliu@red.cc.gatech.edu

Cite this paper for:

• Planning directly at the problem level could be too complex because the number of objects is large and many actions are applicable at each state.
• Some control structures are proposed, but either not flexible enough (fixed priority) or too many interactions to consider (schedulers, or dynamic priority).
• A possible solution is to have layered control structure so as to better control the search process.
• The meta-level control selects tasks to work on according to the result of meta-planning. Conceptually, there could be even higher meta-levels. In reality, the control levels stop at a point where the control is fixed, or a simple FSA as in the paper. Moreover, the control levels are usually limited to two, as shown in the paper.

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.
    * High level operators manipulate lower level operators.
2.3 Advice and control

3. A Model for Planning
   * Features or contributions
     + A simple finite-state machine as the top-level interpreter
     + Factoring of control and world knowledge
     + Operators at meta-level and their control (meta-meta-control)
   * Layers
     + laboratory space (domain space)
     + design space
     + strategy space
     + interpreter
3.1 Control messages
    * consider operators are triggered by messages
    * to communicate cross layers
    * to provide as much isolation as possible
3.2 Laboratory space
    * MARS operators
3.3 Design space
    * Planning as operations on constraints
    * Design objects to work upon
      + constraint
      + difference
      + refinement
      + tuple
    * Design operators
      + comparison
        - Find-Unusual-Features
        - Check-Prediction
      + temporal-extension
        - Propose-Operator
        - Propose-Goal
        - Predict-Results
      + specialization
        - Refine-Operator
        - Propagate-Constraint
        - Refine-Object
3.3.1 Design operators
3.3.1.1 Comparison operators
        * Find-Unusual-Features: goal-checking, MEA-type difference
        * Check-Prediction: goal-checking for forward-chaining
3.3.1.2 Temporal-extension operators
        * Propose-Operator: expansion, MEA-type difference reduction
        * Propose-Goal: subgoaling (?)
        * Predict-Results: forward-chaining
3.3.1.3 Specialization operators
        * Refine-Operator: hierarchical-flavored operator refinement
        * Propagate-Constraint: some reasoning process
        * Refine-Object: react to constraint propagation, or binding commitment
3.3.2 Interface to laboratory space
      * messages
3.4 Strategy space and its interpreter
    * FSA, and two principles: least-commitment and heuristic
      + least-commitment is preferred, try heuristic only when
        least-commitment is impossible
3.4.1 Strategy operators
3.4.1.1 Focus
        * Focus creates and executes new design tasks
        * Tasks terminate in four possible states
          + done, failed (over-constrained), suspended (under-constrained),
            cancelled (due to constraint propagation)
        * Focus goes through the agenda to run tasks, if over-constrained,
          goto Undo (by interpreter)
        * A fixed priority for design-space operators (for both Focus and 
Resume)
3.4.1.2 Resume
        * restarts suspended tasks
3.4.1.3 Guess
        * explore
3.4.1.4 Undo
        * backtracking, limited
3.4.2 The interface to design space
      * messages
3.4.3 Significance of the strategy space
      * combination of conservative reasoning (least-commitment) and
        plausible reasoning (heuristic)

4. Relationships to Other Work
4.1 GPS
    * heuristic-compiler
4.2 TEIRESIAS
    * fixed control-rules
4.3 HEARSAY-like systems
    * blackboard model (single-layered)
4.3.1 SU-X and SU-P
      * multi-layered and multi-planes
4.3.2 The Hayes-Roth planning model
      * mixture of goal- and data-driven behavior
      * multi-plane
      * opportunistic (bi-directional) and hierarchical

5. Limitations and Further Research

6. Summary

Summary author's notes:

• none