From: Masaharu Kobashi (mkbsh_at_cs.washington.edu)
Date: Tue Nov 18 2003 - 23:39:55 PST
Title: Symbolic Heuristic Search for Factored Markov Decision Processes
Authors: Zhengzhu Feng and Eric A. Hansen
[Summary]
The paper reports a new attempt to efficiently solve the
large scale MDPs by using the symbolic reachability analysis with
dynamic programming and an admissible heuristic.
[Most Important Ideas]
First, their system focuses on set of states rather than individual
state. They used a generalized LAO* algorithm which manipulates sets
of states. Thus they achieved substantial speedup in solving the MDPs
which are know to be problematic due to exponential explosion of
state space with increase of number of features.
Second, their use of dynamic programming focuses on computation on
reachable states using their idea of masking which limits the coverage
to subsets of the total state space. It is similar to the structured
reachability analysis. But Feng and Hansen's method is stronger in
that it ignores the states which cannot be reached from the start
state by following an optimal policy, while the standard structured
reachability analysis ignores only those states which cannot be
reached by any policy.
[Largest Flaws]
I see no large flaws. The description and coverage is appropriate
for this subject. If allowed to be a little picky, I missed more
analysis and justification of their heuristic as well as comparative
analysis with other possibilities.
[Important Open Research Questions]
One is the study of wider variety of heuristics to use with
their system as well as nondeterministic plannings.
Another, which is stated by the authors, is the study of the
possibility of incorporating additional strategies into the
decision-theoretic planner.
This archive was generated by hypermail 2.1.6 : Tue Nov 18 2003 - 23:39:55 PST