From: Lincoln Ritter (lritter_at_cs.washington.edu)
Date: Tue Nov 18 2003 - 18:56:44 PST
Symbolic Heuristic Search for Factored Markov Decision Processes
Feng, Hansen
Reviewed by Lincoln Ritter
MDP solving is formulated in terms of search using symbolic
representation of state space (using ADDs) to allow for pruning based
on reachability analysis and heuristics.
The big idea here is the realization of the authors that MDP solving
can be formulated in terms of search. Coupled with the gains achieved
by Hoey et al using symbolic manipulation (ADDs etc) this enables the
solver to "intelligently" investigate possible solutions instead of
blindly finding solutions for all possible starting conditions.
Further, the characterization of MDPs in terms of search means that a
large body of knowledge can now be applied to MDPs with many potential
benefits.
I would like to comment that, especially in comparison to the paper
by Hoey et al, I found this paper to be rather well written with
clear, yet concise explanations of prerequisite work. Further, the
detailed analysis of the experimental results is well done.
While length is certainly a consideration, I would have liked to have
seen a little more investigation into the effect of various heuristic
functions on the search. While some discussion is present on how to
compute various heuristics, no space was devoted to the difference
these heuristics actually made.
I think that future research could definitely focus on what additional
knowledge from search can be brought to bear on MDPs. This may
involve heuristic formulation or investigation into the use of other
types of search.
This archive was generated by hypermail 2.1.6 : Tue Nov 18 2003 - 18:56:44 PST