PLANNING
                         ========

Means-Ends Analysis
-------------------
Means-Ends Analysis (MEA) was the algorithm used in GPS (General
Problem Solver) developed by Newell, Shaw and Simon.   In MEA,
search proceeds backwards from the goal, until an operation is
found which can be performed, in which case the operation is
performed.   This is similar to backward chaining, except that it
is done on forward chaining rules.   The algorithm for MEA is
shown below:

Means-Ends Analysis: (used by GPS)
  Compare the current state to the goal state;
  Choose an operator that chooses the difference;
  Apply the operator if possible -- if not, save the current state,
    and apply MEA to the subproblem of establishing the unsatisfied
    preconditions of that operator;
  When a subproblem is solved, restore the saved state and resume
    work on the original problem.

                        ----------

STRIPS
------
STRIPS (Stanford Research Institute Problem Solver) was developed
by Fikes and Nilsson as the problem solver for a robot called
SHAKEY.   SHAKEY could move around several rooms, and push blocks.
The algorithm used by STRIPS is a very slight variation on the one
used in GPS (GPS used a more general algorithm).   Here it is:

Strips:
  while stack is not empty loop
    if TOS is an action then
      Execute it
    else if TOS is a goal (maybe compound) and it is true then
      Pop it
    else if TOS is a compound goal then
      if if it has been tried before and failed then
        Push each of its components on to the stack in a different
          order
      else
        Push each of its components on to the stack
      end if
    else
      Find an operation which contains an action which would make
        the goal true, i.e. one in which there is an item on its
        add list which unifies with the goal.   Prefer operations
        which can be executed immmediately; (***)
      Push its preconditions on to the stack as a compound goal
    end if
  end loop;

(***) It might be necessary to backtrack to this point and select
another operation.

                            ----------

An Example
----------
It is best to explain the algorithm by tracing a simple example
problem, drawn from the "blocks world".

There are four basic operations (pickup, putdown, stack and
unstack), which a robot can perform on three blocks, (a, b, c).
These operations can be represented as forward chaining rules,
where the THEN part is separated into a delete list and an add
list.   A rule can be executed, or applied, when all of the items
on its precondition (if) list are true (i.e., match items in the
current state description (which roughly corresponds to working
memory)).   If it is applied, all the items on its delete list are
deleted from the current state description, and then all the items
on its add list are added to the current state description.

  pickup(X)
    if:     ontable(X), clear(X), handempty
    delete: ontable(X), clear(X), handempty
    add:    holding(X)

  putdown(X)
    if:     holding(X)
    delete: holding(X)
    add:    clear(X), ontable(X), handempty

  stack(X, Y)
    if:     clear(Y), holding(X)
    delete: clear(Y), holding(X)
    add:    on(X, Y), clear(X), handempty

  unstack(X, Y)
    if:     on(X, Y), clear(X), handempty
    delete: on(X, Y), clear(X), handempty
    add:    clear(Y), holding(X)


                      | |                   +---+    | |
                    +-----+                 | a |  +-----+
             +---+  \     /                 +---+  \     /
             | a |                          | b |
             +---+   +---+                  +---+
             | b |   | c |                  | c |
          ---+---+---+---+---         ------+---+------

             INITIAL STATE                GOAL STATE



 (1) on(a, b) ^ on (b, c)

The top goal on the stack is a compound goal.   Separate it into
its component subgoals.   Push them on to the stack.   Note that
the top goal is true, and so can be popped immediately.

 (2) on(a, b)                          --> POP
     on(b, c)
     on(a, b) ^ on (b, c)

Stack(b, c) is the only operation which could satisfy the top goal
on(b, c).   Push it on to the stack, followed by its precondition.

 (3) clear(c) ^ holding(b)
     stack(b, c)
     on(b, c)
     on(a, b) ^ on (b, c)

Separate the top goal into its component subgoals, of which one can
immediately be popped.

 (4) clear(c)                          --> POP
     holding(b)
     clear(c) ^ holding(b)
     stack(b, c)
     on(b, c)
     on(a, b) ^ on (b, c)

One possible operation to satisfy the top goal holding(b) is
pickup(b).   Push it on to the stack, followed by its
preconditions.

 (5) ontable(b) ^ clear(b) ^ handempty
     pickup(b)
     holding(b)
     clear(c) ^ holding(b)
     stack(b, c)
     on(b, c)
     on(a, b) ^ on (b, c)

The alternative to pickup(b) is unstack(b, Y).   Then, the
following stack is eventually built up:

     clear(Y) ^ holding(b)
     stack(b, Y)
     on(b, Y)
     clear(b)
     handempty
     on(b, Y) ^ clear(b) ^ handempty
     unstack(b, Y)
     holding(b)
     etc.

As the goal, clear(Y) ^ holding(b) is harder to achieve than the
original goal of holding(b), this path can be pruned as unpromising.

Returning to our original choice, push each of the the component
subgoals of the top goal on to the stack.   The top goal is true,
and can be popped immediately.

 (6) ontable(b)                        --> POP
     clear(b)
     handempty
     ontable(b) ^ clear(b) ^ handempty
     pickup(b)
     holding(b)
     clear(c) ^ holding(b)
     stack(b, c)
     on(b, c)
     on(a, b) ^ on (b, c)

Clear(b) can be satisfied by unstack(X, b) or putdown(b).
Unstack(X, b) can be immediately executed if X=a, and so this is
done.   It is then removed from the stack after including it in the
plan.   Then the goal immediately underneath becomes true, and so
can be popped.

 (7) unstack(a, b)                     --> EXECUTE
     clear(b)                          --> POP
     handempty
     ontable(b) ^ clear(b) ^ handempty
     pickup(b)
     holding(b)
     clear(c) ^ holding(b)
     stack(b, c)
     on(b, c)
     on(a, b) ^ on (b, c)


              | |
            +-----+
            \+---+/
             | a |
             +---+

             +---+   +---+
             | b |   | c |
          ---+---+---+---+---

             CURRENT STATE

Putdown(a) satisfies the top goal, and is executed.   Then most
of the stack can be dismantled, giving more steps to the plan.
The alternative to putdown(a) is stack(a, Y), with Y either being
set to b or c.   This will lead to a workable but inefficient plan.

 (8) putdown(a)                        --> EXECUTE
     handempty                         --> POP
     ontable(b) ^ clear(b) ^ handempty --> POP
     pickup(b)                         --> EXECUTE
     holding(b)                        --> POP
     clear(c) ^ holding(b)             --> POP
     stack(b, c)                       --> EXECUTE
     on(b, c)                          --> POP
     on(a, b) ^ on (b, c)


              | |
            +-----+
            \     /  +---+
                     | b |
             +---+   +---+
             | a |   | c |
          ---+---+---+---+---

             CURRENT STATE


Only the original goal is left, but it fails.   While we were
satisfying on(b, c), we undid the goal on(a, b) which was true
initially.   This will have to be achieved again.   As we are
resatisfying a compound goal, we reorder the component subgoals
when we push them on to the stack.

 (9) on(b, c)                          --> POP
     on(a, b)
     on(a, b) ^ on (b, c)

The remaining steps are routine, and are therefore given without
comment.

(10) clear(b) ^ holding(a)
     stack(a, b)
     on(a, b)
     on(a, b) ^ on (b, c)

(11) clear(b)                          --> POP
     holding(a)
     clear(b) ^ holding(a)
     stack(a, b)
     on(a, b)
     on(a, b) ^ on (b, c)

(12) pickup(a)                         --> EXECUTE
     holding(a)                        --> POP
     clear(b) ^ holding(a)             --> POP
     stack(a, b)                       --> EXECUTE
     on(a, b)                          --> POP
     on(a, b) ^ on (b, c)              --> POP

When the goal stack is empty, the goal has been achieved, and the
sequence of steps is available.   In this case, they are:

     unstack(a, b)
     putdown(a)
     pickup(b)
     stack(b, c)
     pickup(a)
     stack(a, b)

                        ----------

Hierarchical Planning
---------------------
The basic STRIPS algorithm only plans at a single level of detail.
For blocks world problems this is not too much of a handicap, but
for larger problems, plans are best considered at more than one
level of detail.

The STRIPS algorithm can be modified to incorporate hierarchical
planning by associating criticality values to each condition, to
reflect the difficulty of achieving them as goals.   The new
algorithm is called ABSTRIPS.   Criticality values that work well
for the blocks world are

  1 + (number of parameters in condition).

ABSTRIPS first considers only conditions with highest criticality,
before considering conditions of lower criticality.   Because of
this, some operations are initially missing from the plan.

NOAH (developed by Sacerdoti) used a "procedural net" instead of
the stack used by STRIPS.   A procedural net is a partially ordered
network of actions representing the plan.   Ordering of operations
in the plan was only done between two subplans when one interfered
with the goals achieved by the other, and when one subplan caused
another subplan's preconditions to become true.   NOAH, however,
still used simple backtracking to recover from an unsuccessful
plan, without noting the reason for the plan's failure and using
this when reformulating the plan.

                        ----------