From: Jessica Kristan Miller (jessica_at_cs.washington.edu)
Date: Wed Nov 19 2003 - 00:40:47 PST
Paper Reviewed: Symbolic Heuristic Search for Factored Markov Decision
Processes
Paper Author: Feng, Hansen
Reviewed By: Jessica Miller
Summary:
This paper combines state space pruning and heuristic search to improve
the SPUDD algorithm for solving MDPs of very large state spaces
efficiently.
Two Important Most Ideas:
(1) One clear innovative idea in this paper is the use of a heuristic
search with state abstraction to solve MDPs. The authors have developed a
version of the LAO* algorithm using ADDs to represent sets of states and
the other elements of the MDP. Using this heuristic search the authors
focus the computation on the parts of the state space that are reachable
from the starting state. Pruning the state space in this way makes for a
more efficient algorithm to solve large MDPs.
(2) Another idea that the authors present (although it may have been
investigated before) is the use of dynamic programming to create an
admissible heuristic. Perhaps this is only a good idea for MDPs due to
the fact that iteratively better value functions are generated and can be
used as admissible heuristics, but it'd be interesting to see if you could
automatically generate admissible heuristics for other AI search problems.
Largest Flaw in the Paper:
There are two things that bother me about this paper. First of all they
are very vague about the a1-a4 examples. They give very little
description about what these examples entail so we as the readers have to
just trust their judgment. The other thing that bothers me is the fact
that they don't test their improvements on any sort of real world
problems. So, my main complaints are about the way they conducted their
experiments.
Two Open Research Questions:
(1) This paper shows how getting the right combination of ideas together
can result in a better algorithm. The authors mention that further
research into integrating additional "strategies" might yield in even
better results for solving MDPs.
(2) A tangential open research idea is the one I mentioned above
concerning automatically generating admissible heuristics for other
domains.
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 00:40:47 PST