From: Alexander Yates (ayates_at_cs.washington.edu)
Date: Tue Apr 15 2003 - 10:51:41 PDT
Review of "Refinement planning as a unifying framework for plan synthesis,"
by S. Kambhampati.
Kambhampati presents a framework called "refinement planning", in which
planning is cast as a search through a space of sets of partial plans, each
of which corresponds to a "candidate set" of action sequences that may or
may not be solutions to the planning problem. The author claims that this
framework can be instantiated in a number of different ways that correspond
to all, or at least most, of the major planning techniques.
The author claims that refinement planning is an abstract form that is
expressive enough to capture almost all major planning algorithms, including
state-space search, plan-space search, and Graphplan and Satplan. This is
important because it facilitates comparisons between the major approaches to
planning. A second contribution of this paper is the idea of disjunctive
representations in planning. The author claims that several modern planners
(including Graphplan, Satplan, and I think UCPOP-D) make use of this
technique without really knowing it (or at least without calling it that),
and he claims that this representation is a major reason for their success.
As a tutorial introduction to the topic, this paper didn't really suffer
from any major flaws. There were places where I would have liked more
details and examples, especially in the analysis of asymptotic tradeoffs,
but that's to be expected from an overview like this one. One complaint I
had was that the author advocated using disjunctive representations to scale
up refinement planning, but it wasn't clear to me why the disjunctive
representation would help so much. As the author says, it decreases the
progress factor, and so there is clearly a tradeoff in using it.
There are several interesting ways to look at extending this work. One
would be to try to find a similar unifying framework for more expressive
languages than STRIPS, like planning with incomplete information or
uncertainty. Another possible extension is to look at a principled way of
choosing among various refinement strategies based on an analysis of the
domain. For example, noticing that certain subgoals will have to
interact -- maybe because all of the actions satisfying one have
preconditions that are affected by all of the actions satisfying another --
might cause the planner to use lower-commitment strategies.
This archive was generated by hypermail 2.1.6 : Tue Apr 15 2003 - 10:52:00 PDT