From: Parag (parag_at_cs.washington.edu)
Date: Tue Apr 22 2003 - 10:58:01 PDT
Planning with Incomplete Information as Heuristic Search in Belief Space
Blai Bonet and Hector Geffner
The paper formulates the problem of planning with with incomplete
information as a heuristic search in belief space and gives a
couple of interesting algorithms for performing the search.
The authors do a great job of first specifying a model
for formulating the classical planning as a heuristic
search in state space and then extending the idea to
more complex domains like conformant planning and
contingent planning, by introducing the notion of
belief space. Under the models defined, the conformant
planning as well contingent planning can be viewed as
deterministic planning problems (in the belief space)
and hence, many of the standard search techniques can
easily be extended to handle these domains. They even
extend the idea to the case of probabilistic contingent
planning. And the whole appraoch given seems to be
very systematic and mathematical.
I had some problems with the experimental section. First,
I had to go through it several times, before I could make
out what are they trying to convey. As already pointed
out, probably results could have better been represented
in the form of graphs. I also felt that there was too
much use of acronyms for defining the planning domains
i.e. BT, BMTC, BTUC, BTC etc. and it was difficult to make
out what corresponds to what.
Another question about the probabilistic planning that I have
is - the authors do not seem to report the performance of
any other planners when they talk about probabilistic
domains. Is it that their's is the first planner which
handles these domains?
For future work - the authors mention using h=0 as their
heuristic function along with hdp, and in some of
the problem domains (like sorting networks), they report
that hdp offers no extra advantage. If one could identify
such domains, where hdp offers no advantage over h=0,
then one could save a lot of preprocessing time(reported
as one of the bottolnecks) by not calculating hdp at all.
Another direction could be, in case of probablistic planning,
to analyze the tradeoff between how much close the final solution
is to optimal and the level of discretization - which would
determine how much to discrtize (thereby reducing the size
of search space a lot) versus how close we want to be
to the optimal.
This archive was generated by hypermail 2.1.6 : Tue Apr 22 2003 - 10:58:02 PDT