Notes on planning using Plan Graph Analysis

Prepared by: Xiuping Yang.
Revised by: Rao Kambhampati [Oct 15, 1995]

Graphplan details:

Graphplan is a new approach to planning problem in STRIPS-like
domains, it is based on the paradigm of Planning Graph Analysis (PGA)
which takes the initial conditions, domain information, and notion of
time to construct a leveled graph.Then this graph is explored to find
a valid plan or state that no plan exists.  Graphplan always returns a
shortest partial-order plan.

Definitions and Notations:

. NO-OP action: the "doing nothing" action is noticed as no-op action

. VALID PLAN: a valid plan for a planning problem consists of a set of
actions and specified time-steps with the requirement that the actions
at a given time step be independent, and finally it must make all the
Problem Goals true at the final time step.  Here  "independent"
means that no two actions could interfere each other at a single
time-step such as deleting the ADD-Effects or the preconditions of the
other's.

. Planning Graphs

It is a directed, leveled graph with two kinds of nodes (action nodes and
proposition nodes) and three kinds of edges (precondition edges, add- and
delete-edges)

. Exclusion Relations

This relations are propagated when the graph is created. Two actions at a
given action level in a planning graph are mutually exclusive if no valid
plan could possibly contain both. Two propositions at a given proposition
level are mutually exclusive if no valid plan could make both true at
that time step. 

Specifically, the following two ways are used to find the exclusion
relations among actions:

(1) [ interference ] For action a and action b, if either of them delete a
precondition or ADD-Effect of the other.

(2) [ Competing Needs ] If there is a precondition of action a is mutually
exclusive with a precondition of action b in the previous proposition level.

Similarly, for propositions P and Q, if all ways of creating them are
exclusive, then they are mutually exclusive.

Notice: THere are two ways "progress" is made in planning as
plan-graph is being constructed. First, the newer proposition levels
may contain more propositions than the previous ones (a proposition
level i must contain all the propositions in level i-1 anyway because
of the no-op actions).  Second, mutual exclusivity among propositions
has to monotonically reduce as the plan graph is expanded.  In
particular, two propositions P and Q may start out being mutex in the
initial proposition levels, and become non-mutex as plan-graph is
expanded. Once they become non-mutex however, they can never become
mutex again.  Exclusivity is reduced along with the increaing of the
length of the Graph.

DESCRIPTION of the ALGORITHM

Generally, the algorithm runs in stage. In stage i, it takes the plan graph
with length i-1 from stage i-1, then extends it one time step, generate next
action level and the following proposition level, then search this extended
graph to see if a valid plan exists or no goals can be achived in time step
i.

(1) Extending the Planning Graph

Put the initial conditions as the first proposition level of the graph,

generate the next action level in this way: for all actions which have
non-exclusive preconditions in previous level, insert action nodes,
then insert all the no-op actions and all the precondition edges. Then
check and record the exclusivivity among nodes.

generate the next proposition level in this way: put all the
ADD-Effects of the actions in the previous level in the next level as
propositions, insert the add-edges and delete-edges Then check and
record the exclusivity among nodes.

(2) Searching for a plan

The general idea is that if the top level goals g1..gn appear at a
proposition level i, then it is POSSIBLE (but not necessary) that
there is a plan of i steps long that will be able to achieve the
goals. Since we are not really sure if this plan exists, we need to do
some backward analysis to check if it does. This is done by a backward
chaining strategy.

Using a backward-chaining strategy, the idea is if the subgoals at
time t-1 could be achieved, then the original goal could also be
achieved at time t.

METHOD: for each goal in a given set of goals at time t, for each action
generating that goal, select it if it is not exclusive with those already
selected. If no actions are available then back up to the previous goal.

Once finished with all the goals at time t, the preconditions to the
selected actions make up the new goal set at time t-1.

Graphplan then recursively continues this procedure at time t-1. At

This process succeeds if we reach stage 0 corresponding to the intial
state (at which point the subgoals that we need to make true at stage
0 will be part of init state). 

The mutual exclusion relations improve the efficiency of GRAPHPLAN because
the search space is  pruned and reduced.
	
Memoing:

We note that the plan graph is prefix-static, in that as the plan graph
of i-stages is expanded, the existing i-stages don't change. This
means that any processing/queries we answered at stage i can be
cached/momoed so that we can reuse them if they get posed again in the
future. 

In particular, suppose  you tried to see if g1, g2,... gn are
satisfiable at stage i, and the backward chaining strategy failed. We
know that we have to continue plan-graph expansion forward. We also
know that if ever, in the future, someone tries to check whether
certain goals are true in the plan-graph at stage i+m, and that in
turn converts into a query that contains g1...gn (among other goals)
 at stage i, then the query WILL FAIL. To make sure we realize this,
we remember each of the failed goal subsets are stored at each stage. 

MAKING GRAPHPLAN COMPLETE

The above basic algorithm is only weakly complete because while the
algorithm terminates when a plan exists, if no valid plan exists, the
algorithm doesn't know when to terminate. [Of course, the plan-space
planners that we studied till now are also only weakly complete since
they are searching in infinite plan spaces and may never terminate if
there is no solution.]  To make graphplan complete, we first introduce
"level off" of a graph.

As we know, Plangraph is used to solve STRIPS-domain problems which
have only finite ground operators such that can only produce finite
propositions. [[From the state-variable representation of the world we
discussed earlier, this means that the world is representable with a
finite number of state variables, each of which have finite domains.]]
If no valid plan exists for a planning problem, we can believe that at
some time in the future, the "level-off" will occur in the Plan Graph
-- the adjacent two levels have the same size of the propositions *and*
have the same mutual exclusion relations among them (the later is also
important, since as we noted earlier, progress continues as long as
the mutex relations reduce).

Once the graph has levelled off, if the current proposition list does
not contain some goals, of if they appear, but some of them are marked
mutually exclusive in the current set, then we can terminate with
failure. Although this is the most normal way for unsuccessful
termination, Blum and Furst point out that this is not sufficient.
That is sometimes the problem is unsolvable and the tests above won't
recognize this since the goals are not marked mutex at the current
level. Blum and Furst provide a more involved test that considers the
set of failed goal sets at stage i which are generated due to a
backward chaining originating at stage n (> i) and are thus memoized. 
Suppose there exists a stage i such that  G-i-n is equal to G-i-(n+1),
and n is a stage after level-off. In this case, we can conclude that
this problem is not solvable since the backchaining from n as well as
n+1 are giving rise to the same failing goal subsets, meaning that
there are no new paths in the plan graph being explored. 

Although this test makes intuitive sense, it is not clear to me (Rao)
as to when it would really be needed.  It would be nice to come up
with an example problem where the more obvious termination tests won't
work, and this more involved check is needed.