Planning Seminar Course, Jan 26
Note taken by XuanLong Nguyen, xuanlong@asu.edu

Following up the previous class, we discuss how most of current planning
algorithms can be placed under the "Refinement Planning" framework.
Relevant papers are Rao's "Refinement planning as a unifying framework for 
plan synthesis" AI magazine summer 1997 and his IJCAI-99 tutorial
"Recent Advances in AI planning: A unified view".

Refinement Planning is an elegant framework compassing most of current 
of planning approaches. Putting different planning approaches under
this single framework has several advantages: (1) Better understanding
and comparison of tradeoff b/w different planners  (2) Openning avenue
for hybrid approaches. In particular, it provides explication of the
connection b/w planning and CSP, SAT and ILP.

The basic idea of refinement planning is, starting with a set of all
possible solutions (which, for example, may be syntactically a set 
of all action sequences), refinement planning involves narrowing down
the set of possible solutions (i.e prunning non-solutions) until
a solution is identified and verified.  The identification and
verification of solution is called the extraction of solution.
Last class discussed about checking (verifying) the correctness
of a solution plan.

Syntactically, the set of possible solutions can be represented as 
a partial plan, which in turn are represented in terms of sets of
constraints. For example, a partial plan represented by a single
constraint 0<infinity can be thought of as a set of all possible sequences 
of actions. After one refinement we get a set of constraint 0*A1<infinity, 
which can be thought of as all possible sequences of actions that start
with action A1. In this example, we can see that after the refinement,
the set of possible solutions is narrowed down in the sense that
it is a strict subset of the set of posssible solutions before the refinement.
The refinement involves adding constraints ( contiguity constraint 0*A1) 
to the earlier set of constraint representing the partial plan.
There are several types of constraints: step constraints, ordering
constraints, auxiliary constraints, etc

Specifically, a partial plan = (steps, ordering, aux constraints).
A step specifies a unique number and represents one action (as in
sequential planner) or a number of actions (as in a normal (parallel 
Graphplan). 

A candidate set of a partial plan is defined as a set of action sequences
that contains actions corresponding to all steps and satisfies all
constraints (ordering and auxiliary constraints). Thus the candidate
set is corresponding to the set of all possible solutions.
Since such a set is still infinite in size, it is useful to have
a notion of "minimal candidate set", which contains of action
sequences (candidates) that can NOT be reduced in term of number of actions
(and constraints ??). Every candidate (i.e possible solution) of a 
partial plan corresponds to a unique minimum candidate.  Specially, 
the minimal candidate set is finite. 

Now it's quite clear that the refinement process involves (1) reducing the
set of  candidates and (2) increase the length of minimal candidates
The refinement (pruning) strategy involves propagating the constraints
onto the partial plan. There are several properties to be considered:
A refinement strategy R: P -> P' reducing a partial plan P to P' is 
(1) complete if P' contains all possible solutions in P, (2) monotonic 
if P' has *longer* minimal candidates than P', (3) progressive if P'  
is a proper subset of P, and (4) systematic if components of P' do
not share candidates (i.e disjoint).

[
Note that systematicity helps avoid the redundancy of the search
although it may or may not improve the effecitiveness of the search process. 
In state space search, systematicity is not a big issue is because
it's automatically ensured by the way the search space is being splitted.
In plan space search, systematicity is ensured by certain kind of
constraints added to the partial plans. In disjunctive planners,
systematicity is not an issue because the search space is not splitted.
]

In state space search, the refinement process involves adding step 
constraints (by adding actions at the prefix of the plan as in progression 
search and at the postfix of the plan as in regression search)
while all ordering and causal constraints are easily satisfied and
verified.  Refinement in plan space search adds ordering and causal 
constraints and resolves the constraint conflicts.  
These were examples of *conjunctive* planners where the refinement 
process effectively splits the plan sets into search space and recursively 
refine the partial plans in each partition of the search space.  Thus
in conjunctive planner approaches, the most critical issue is an effective
splitting strategy (i.e heuristics) to guide the refinement process.

In disjunctive planners (exemplified by Graphplan, SAT, CSP approaches)
the resolving of constraints are delayed to the solution extraction phase.
Thus, a main difference w/ conjunctive planners is that the set
of constraints are  represented as a set of disjunctive constraints,
and the search space is NOT splitted.  Thus in disjuctive planner
approaches, the critical issue that decides the effectiveness of
the search lies in the extraction phase, because checking a set of
disjunctive constraints is computationally hard.  Good heuristics 
(as in CSP, SAT) and various search techniques can be employed like 
stochastic search.

[
Actually, although plan space planning is catergorized as conjunctive
planner, its lazy "least committment" approache put it somewhere in the 
middle between progression/regression state space search and disjunctive
planners as far as the resolving of constraints is concerned.  
(state space search is at an extreme: it resolves the causal constraints
completely after each splitting, disjunctive planners is at another
extreme where all causal constraints are kept unresolved until
the extraction phase begins. In both cases the step and ordering constraints
are completely known, which is not the case for the plan space planners ).

Thus the failure of current plan space  planners can be explained
by its lack of good heuristics.  State space planners, by committing
early to the step and ordering constraints are able to devise
informed heuristic that guide the refinement (splitting) process.
Disjuctive planners by having all the constraints available on
the table at the last minute, are also able to have smarter strategy
for solution extraction.  The reason the current plan space planners 
does not have a good and informed splitting strategy is probably
having something to do with its ignorance of the step and ordering
constraints, and its relatively weak commitment to the causal constraints.

This fatal performance tradeoff is paid for a more flexible 
representation of the partial plans.  As we move to reasoning
about resource and time constraints, it is probably easier to use
the plan space planner's approach to deal with new set of constraints.
But to have a good performance, we still need to devise good heuristics
that guide the refiment/search.  It seems easier to have good heuristics 
by moving closer to either extremes (state space search or CSP approach).
]