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.