From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Mon Apr 14 2003 - 23:44:16 PDT
Paper title/author:
Refinement Planning as a Unifying Framework for Plan Synthesis
One-line summary:
The paper discusses a high-level planning framework that trivially
subsumes virtually all other planning approaches, and examines four
families of refinement strategies.
The (two) most important ideas in the paper, and why:
Using Disjunctive representations can speed planning by intelligently
breaking the plan set into subsets, and allow it to scale to large
problems. This has the advantage of not necessarily commiting to a
particular subplan, and potentially of decreasing memory consumption.
Unfortunately, no performance numbers are provided here.
The paper explores four families of refinement strategies: state-space
(growing the plan forward from the initial condition or backward from the
goal), plan-space (building the plan from constraints), task reduction
(building and using meta-actions to ease planning), and tractability
refinements (finding how to order existing actions).
The one or two largest flaws in the paper:
The 3-step framework basically simplifies to:
While (I still have candidate plans)
If I have a plan that reaches the goal, return it
Else, improve the existing plans
EndWhile
Yes, this does subsume every other planning approach, but just because it
is so high-level. I don't see why the author made such a big deal about
it. Am I missing something?
At several places in the paper, the author refers to previous empirical
studies that show that interleaving refinements is sometimes superior to
using just one refinement (p83), when tractability refinements lead to
reductions in search time (p86), that commitment levels in a plan class
indicates the degree of ease of serializability (p87), and that
interactive planner synthesis tools can incorporate domain knowledge into
a plan search (87,89). Unfortunately, these topics were treated in about
one paragraph each. The paper would have benefited from a cursory
explanation of these studies, and maybe a graph or two. Similarly, I have
no idea how refinement planning does on even a toy problem.
Identify two important, open research questions on the topic,
and why they matter:
Interleaving different strategies for plan set refinement is an open area
of research, as admitted by the author. Intuitively, I agree that this
would improve the speed of the search, but I would still like to see
empirical results of this. One can contribute in this vein in several
ways - identifying new refinement techniques and integrating them with
others is one way. Another is to recognize the fact that a refinement
strategy that works very poorly on its own may have a tremendous effect
when interleaved with another strategy. Dynamically determining which
refinements to use, and when to use them is also something that can
improve refinement planning.
The author also mentions the application of machine learning to planners.
Presumably, the planner would learn to first try actions that were
previously tried in similar states, and found them to be "useful". It is
not immediately clear what "useful" means, or how to measure it. Also,
this would have interesting applications in exploiting symetry in planning
problems, and in incorporating experience from similar past problems the
planner has solved.
This archive was generated by hypermail 2.1.6 : Mon Apr 14 2003 - 23:44:16 PDT