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 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).
]