From: Stanley Kok (koks_at_cs.washington.edu)
Date: Mon Apr 21 2003 - 23:26:40 PDT
Paper Title: Planning with Incomplete Information as Heuristic
Search in Belief Space
Authors: Blai Bonet and Hector Geffner
One-line summary:
This paper presents how classical and stochastic planning
problems can be reduced to heuristic search problems.
Most Important Ideas in the Paper:
1. The formulation of partially observable and stochastic
planning problems as heuristic search problems.
Flaw in the Paper:
1. The results in the tables can be more succinctly presented
as graphs. It is not immediately clear what the tables (e.g.
Table 1) comparing GPT and other planners are supposed to show.
The reader is misled in thinking that the relative
solution times are being compared. However, such a comparison
is specious as the GPT planner is implemented in a different
language and run on a different platform from the other planners.
The reader can only draw conclusions about the scalability of
each planner (which could be more convincingly shown with graphs).
On a related note, in some planning problems (e.g. Medical), the
paper compares the solution times of SGP and RTDP. Again, this
is incorrect as the planners are implemented in different
languages (one in C++ and the other in Lisp).
2. A minor complaint is that the paper redefines
"non-deterministic" and "probabilistic" to refer to different
types of planning problems even though the terms are synonymic.
Important, open research questions:
1. In the Discussion section, the paper states that, for
probabilistic planning, GTP does not even "get off the ground"
for a sufficiently large state space. This suggests that their
test cases are small-scaled. An open research question is
to design a heuristic search algorithm that scales well.
2. The paper's h_dp heuristic does not work well in the Sorting
Network problems. Why does the heuristic fail? The answer could
help in designing better heuristics for conformant problems.
This archive was generated by hypermail 2.1.6 : Mon Apr 21 2003 - 23:26:40 PDT