From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Mon Apr 21 2003 - 20:29:55 PDT
Planning with Incomplete Information as Heuristic Search in Belief Space
Blai Bonet and Hector Geffner
Main Idea:
This paper presents 4 models for planning problems, and briefly discusses
a few algorithms for solving them and their performances in several
domains.
I liked their classifications of planning problems, dividing them up in
increasingly difficult classes: classical (deterministic) planning,
conformant planning (where the agent maintains a belief of its current
state and has deterministic actions), contingent planning (like conformant
planning, but the agent gets deterministic sensor feedback from its
current state, giving information about its current state), and
probabilistic contingent planning (POMDPs). It was pretty well written
and straight-forward.
The authors transform problems at a high level into one of the above four
models. This allows them to select the algorithm best suited to solving
each problem. Their final planning tool called GPT is then evaluated on a
number of problems, and is found to be superior to two other planners
(CMBP and CGP).
All the problems tested had very few states (almost all of them had < 100
states). I know that POMDPs are hard, but how does GPT perform on larger
but relatively tame POMDPs? And CMBP and CGP weren't run on most problems
presented in the paper - it would be instructive to know if GPT was
superior to other planners in domains that did not involve exploding
toilets.
The authors do not really describe GPT, they merely present its
performance in a few toy problems as evidence that it is better than CMBP
and CGP. I'm sure there were paper length limitations, but it would have
been helpful if they sacrificed some discussion of the problem models for
more description in the translation from STRIPS to their proprietary
language, and more information on how it actually plans.
GPT performance seems to vary by a tremendous amount (between 50% and 2
orders of magnitude) depending on the heuristic used, specifically in the
Square, Cube, and SortN domains. As with the other heurisitic-based
searches we've seen so far, it is not obvious that the chosen heuristics
are the best ones to choose; there may be better heuristics out there.
Also, it would be nice if GPT could predict which heuristic would perform
better, essentially necessitating a 2nd-order heuristic for guessing which
heuristic is better for the search. I haven't spent any serious though on
how to do this though. (Machine learning classifiers maybe?)
GPT does not compute exact solutions for POMDPs, but instead relies on
discretizations over probability distributions to make the computation
tractable. We are not told how this discretization is computed: is it a
constant granularity? If so, it may improve solution accuracy and
convergence time to instead discretize belief space based on the local
probability (ie, if a region in belief space is more likely, discretize it
more finely; if it is less likely, discretize it coarsely). This of
course assumes that we can compute the belief function quickly. Another
approach that may be interesting is to solve the problem several times,
each time adapting the discretization to focus on areas that prove useful
(ie, have a higher probability or relate to frequently used states or
observations).
This archive was generated by hypermail 2.1.6 : Mon Apr 21 2003 - 20:29:56 PDT