From: Alexander Yates (ayates_at_cs.washington.edu)
Date: Tue Apr 22 2003 - 00:08:42 PDT
Review of "Planning with Incomplete Information as Heuristic Search in
Belief Space", by Blai Bonet and Hector Geffner.
This paper gives mathematical models, algorithms, and experimental results
for planning without the closed world knowledge of classical planning, and
the methods are shown to be effective for conformant planning, contingent
planning, and probabilistic planning with partial observability (POMDPs).
One of the main ideas of this paper is that planning with incomplete
information can be viewed as a search problem in the space of beliefs about
what states are possible, and that there are simple models for three
different kinds of planning problems that fit this paradigm. This idea is
apparently an old one, but this paper makes it explicit and coherent. A
second contribution of the paper is to provide domain-independent heuristics
for the three kinds of search problems in the form of solutions to relaxed
problems that have more observability.
I don't have a good sense for how hard these kinds of problems are and how
good the competing algorithms are, but it doesn't seem like their algorithms
will scale very well. Even the heuristics they're using take time
polynomial in the size of the state space to compute, and that doesn't bode
well for scaling up, I don't think. Also, I think the same criticism Dan
had of the HSPr paper applies here: the experiments don't really seem to
test any hypothesis. Rather, they simply report on run times in various
domains.
Possible future directions include looking at different representations
(BDDs, ADDs) to allow the algorithms to scale better and looking for better
heuristics or heuristics that are faster to calculate.
This archive was generated by hypermail 2.1.6 : Tue Apr 22 2003 - 00:08:42 PDT