From: Christophe Bisciglia (chrisrb_at_cs.washington.edu)
Date: Tue Apr 22 2003 - 11:11:13 PDT
Planning with Incomplete Information as Heuristic Search in Belief Space
B. Bonet and H. Geffner
This paper formalizes the representation of four classes of planning
problems as heuristic search in belief space.
These formalizations are the main point of the paper. It is shown that
classical, conformant, and contingent planning can all thought of with
heuristic search in belief space. What belief space is to each class of
problems is a bit different, ranging from a set of states to a probability
distribution over states. Nevertheless, for each of these non-classical
classes of problems, a general domain independent heuristic is proposed.
What was more interesting was unlike HSPr, the heuristic was admissible,
therefore lending itself to classical search algorithms such as A* (when
there is no sensor feedback). This heuristic is also combined with greedy
search to form the foundation for their real time dynamic programming
algorithm (in the presence of sensor feedback), which appears to work
well, but is not optimal.
My criticism of this paper is the same of the HSPr paper. After reading
it, I feel reasonably confidant in my understanding of the ideas, and now
just need some data to justify them. Like the last paper from these
authors, they present a bunch of tables that don't really make it clear
what they're trying to prove. Maybe this is just their way of doing
things, but please, a graph, or something more visual that solidifies that
has been going on for the last few pages.
As far as open research areas goes, I think it would be interesting to
look into how discretization is performed. This isn't really discussed
much, but it seems intuitive that one size wont fit all. Some things are
simply more likely than others to happen.
This archive was generated by hypermail 2.1.6 : Tue Apr 22 2003 - 11:11:13 PDT