From: Tal Shaked (tshaked_at_u.washington.edu)
Date: Mon Apr 14 2003 - 22:35:12 PDT
Refinement Planning as a Unifying Framework for Plan Synthesis – Subbarao
Kambhapmpati
This paper considers many of the techniques planners currently use, and
unifies them into one abstract framework describing at a high level the
process that takes place when going from a planning problem to a solution.
In particular, it discusses the notion of refinement planning in which the
set of all action sequences is reduced to the set of all solutions.
The most important ideas relate to the mapping or grouping of existing
planners into the hierarchy described. Specifically there is the idea of a
plan set, which can be split into components and handled separately
(analogous to branching in state space, or adding an action to plan space),
and also that the candidate set can be pruned by using structure in the
problem. The examples of standard refinements do a good job of illustrating
the more abstract ideas, as well as describing the types of refinements.
Another important aspect is the separation of refinement from solution
extraction. Refinement reduces the search space, and solution extraction is
a form of CSP. The extremes and variations are illustrated through examples
such as a standard state space search versus a naïve complication to a
satisfiability problem. This abstract representation of the planning
problem also allows an intuitive description of planning complexity, and the
tradeoffs between various properties and their relative computational costs.
This unification of techniques also more clearly highlights what areas have
been well explored, as well as what future areas seem promising. This
allows the author to back up many of his opinions in where to focus future
research.
The challenge of abstracting a well-known problem can be tricky when the
reader is familiar with many specific techniques. For whatever reason, it
was not clear to me what the main idea was until a second reading. Perhaps
a more concrete mapping of current planners to the refinement and solution
extraction abstraction earlier on would have made things clearer. There
also seemed to be a lot of new terms introduced in order to clearly describe
the abstraction, which made things confusing. It took some time to
appreciate what exactly some terms meant such as plan set, candidate set,
progressive, systemic, partial plan, minimal candidate, etc. In fact they
often were not used until much later in the specific mappings of current
planners.
There was a ton of research questions given related to filling in the holes
of mixing different refinement techniques. Given the trend at the time (and
now), some of the more interesting areas appear to be the disjunctive
representation which takes into account some structure of the problem, but
moves a lot of the cost to the solution extraction phase which hopefully can
be done efficiently using CSP techniques. Not surprisingly many of the best
planners use variants of planning graphs and satisfiability compilations.
Also mentioned was the idea of using disjunctive representations for
non-classical problems such as incomplete information that require
contingent planning and might be well suited for that kind of refinement.
Finally it sounds appealing to further explore learning techniques to
discover structure in the problem to guide which refinement technique to
use.
This archive was generated by hypermail 2.1.6 : Mon Apr 14 2003 - 22:35:12 PDT