D. McDermott, Planning and Acting. Cognitive Science, 2, 1978.

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

Cite this paper for:

• Planning as problem solving via subgoaling (task-reduction refinement),
• Not necessarily all of the effects of actions can be represented (because of noisy action and observation, the use of "state" here is actually observation in our sense)
• Interleving action with planning,
• Using choice rules (control knowledge, may be high order) to eliminate multiple retieval (mainly reduction), and such rules are considered part of the states of the problem solver,
• The alternative reductions are stored in the form of choice rules for later access,
• Making the state of problem solver accessible to the problem solver itself (a rule based system).

Also: Readings in Planning, J. Allen, editor, Morgen Kaufmann, section 4.3.

Readings in Planning summary:
  McDermott(1978) describes a planning system, called NASL, which did not
  make the assumption that all of the effects of actions could be
  summarized as state changes or that they could be fully explicated and
  stored in effect tables.  Instead, it assumed that planning steps were
  achieved on the fly -- it expanded and executed pieces of the plan as it
  went along.  Thus, it could not use syntactic means of checking for the
  interactions between subplans, as was done in NOAH, etc.  However, NASL
  could use logical inference to conditionally retrieve the add and delete
  statements used by its operators.  Thus, NASL's behavior could be changed
  by conditions of the environment -- for example, it might have a
  different "to-add" rule for a "going" action depending on whether the
  action resulted in reaching a final destination.  This use of deductive
  retrieval allowed NASL to provide a uniform treatment of its planning
  operators, regardless of whether they succeeded or failed during
  execution (an ability not aviable in the classical framework).


1. Introduction.
   * "Problem solving is part of the study of action.  A problem is a
     difficult action.  Solving a problem is the construction and
     successful execution of a plan to carry it out.  Doing this
     efficiently depends on shallow deduction about evolving plans and the
     effects of actions."  (I think evolving in terms of adding rules and
     facts to the system on the fly.  Such things are added during
     processing choice rules, and demand addativity (monotonicity).)
   * The target for the theory is to attain Analytical Adequacy (sufficient
     notations for what to talk about) and Addativity (the program can
     access and make use of all the facts represented in the notation, and
     such facts are incorperated incrementally s.t. (ideally) no change is
     made to old facts).
     
2. A theory of planning and acting.
   * Planning is reduction, the system (NASL) basically is a rule-based system.
     However, the reduction is not in AND/OR graph form (not explicitly)
   * Notions:
     + Task: any describable action.
     + Problem: any task which cannot be immediately carried out.
     + Reduction: a problem is reduced to a collection of subtasks s.t. the
       problem can be carried out by doing all the subtasks.  The
       collection is a plan.
   * Task taxonomy:
     + primitive vs. problematic: above
     + inferential vs. worldly: whether affects the real world
     + primary vs. secondary: whether stands by itself
       - secondary tasks are manners, also called policies.
   * Reduction of a problem:
     + "Extract 'features' of the problem statement, and use them to
       retrieve subproblem schemata (via an 'index' of some kind) which can
       be instantiated to give a plan."  This results a network of
       subtasks, which are connected by subtask and successor
       relationships.
     + Why interleaving planning and acting? or What to do if the retrieval
       gets more than one results?
       - traditionally, backtracking, etc.
       - if considering execution in real world, actions are carried out, the
	 backups are not applicable right away.
       - it is possible some real-world states are not represented in the
	 system.
       - human: try, wait for error (result), correct error, continue.
       - design decision: every task has just one reduction.
	 = How: add choice rules (control rules), either selective or
	   synthetic.
   * Error correction:
     + planning error: rephrase
     + execution error: a set of error-correcting actions
	   
3. Implementation.
   * Representation: a network of tasks, connected by super-sub, and
     pred-succ relationships.  Further, NASL has a notion of main subtasks,
     namely, if a task's main subtasks are completed, then we can proceed
     to the subsequent tasks of this task, although this task might have
     "clean-up" subtasks to do.
   * Main loop:
     Pick a task to work on;
     if primitive then Execute it;
                  else Reduce it;
     repeat until no more tasks.
     + Picking:
       - task-status: pending, active, finished; used mainly by user rules
       - enable-status: blocked, enabled, subs-enabled, succs-enabled; used
	 mainly by interpreter (including creating choice facts).
       - picking enabled tasks only.
       - criteria for enabling rules, straightforward
     + Working on: instantiation and so on.
     + Primitivity test:
       - user-provided operators: very similar to STRIPS operators.
       - built-in primitive operators:
	 = DO-SUBNET: actually introduce a reduction by adding a fact into
	   the system, in the form of (PLAN-INSTANCE ...), this is where
	   multiple retrieval could occur.
	 = in more detail, the retrieval is done by a bunch of TO-DO
	   indices.
       - user provide how a task should be reduced, avoiding loop is user
	 responsibility.
     + Multiple retrieval and choice rules
       - When multiple retrieval occurs, a choice fact and a couple of
	 options, to record choice points and alternatives.
       - Choice rules usually take the choices and options as preconditions
	 to RULE-IN, RULE-OUT, RULE-TOGETHER (for synthesis) options.
       - QUIESCENCE to give the system one more chance.
   * Policy issues:
     + manner constraints
     + largely the same as primary tasks: reduction, status, etc.
     + primary policies:
       - MONITOR: activated when some task is removed
       - action PRIM: a way of doing conditionless operators, similar to
	 the Start operator in POP.
     + representations:
       - explicit
       - SCOPE to connect policies to primary tasks
       - CONTINUE to do a policy during a period of time

4. An extended example.
   * different implication rules
     + ->C p q: to prove p, prove q
     + ->A p q: if p is recorded, record q
     + ->G p q: prove p, then for each instance generated (for which p is
       true), record an instance of q
   * close-world assumption: PRESUMABLY and CONSISTENTLY
   * complex constructions:
     + PREREQ: for the purpose of protect properties during a period,
       similar to auxiliary constraints in POP; archieved by PROTECT
     + PROTECT: as a policy
     + ugly rules: result of closed-world assumption
     + if the protection is violated (because we cannot reason about
       future!), what to do: reachieve it after the violator is finished.
       (avoiding loop: user responsibility!)
   * a lot of rules are created on the fly!
   * Error correction: for avoid "over-planning", only consider errors when
     they happen!
     
5. Transcending NASL's limits.
   * A notion of time and event: for the purpose of lookahead, or reasoning
     about possible future events.
   * Success condition for tasks: one more level of check
     - Most policies have effects via inference, if the inferences have no
       chance to be done, the policies are indicated failed, (I didn't
       think about it!)
     - The assumption "subtasks succeed -> the supertask succeeds" not quite
       valid.
     - user rules might be wrong.
   * Error detection and correction ("abondon")
   * Rephrasing
     
6. Conclusions.

Summary author's notes:

• Addativity is not a feasible goal at all. Non-monotonicity kicks in inevitably.
• The logic approach (problem solver) seems not a good choice for planning, especially because of the protecting issues.
• Lookahead is a big problem.