From: Karthik Gopalratnam (karthikg_at_cs.washington.edu)
Date: Wed Nov 19 2003 - 01:11:00 PST
Paper Review #5: "Symbolic Heuristic Search for Factored Markov Decision
Processes"
Authors: Feng & Hansen
Reviewed by: Karthik Gopalratnam
This paper presents a method of combining factored representation
of MDP's and employing heuristic-driven reachability search to solve
MDP's more efficiently by therefore leveraging the benefits of state
abstraction and locally focused computation.
The authors build upon two earlier techniques - the SPUDD
algorithm and the LAO* algorithm (developed by one of the authors
earlier). The SPUDD algorithm provides a symbolic representation of the
MDP in a compact manner that lends itself to an efficient dynamic
programming solution.
The LAO* algorithm is a heuristic driven algorithm that focuses
computation in those states that are reachable from the start state. The
authors represent every aspect of the MDP symbolically as an ADD, and
make use of the LAO* algorithm to locally "expand" the horizon of the
current best policy, in order to "greedily" solve the MDP in symbolic space.
The paper is compactly presented, and well-structured, and the authors make an
admirable case for their technique being a natural extension to their
earlier work.
Though the results are well presented, and bear out the authors'
arguments on the importance of the improvements made over earlier work,
they would have made a stronger case for their algorithm by including
tests on other mode general data sets other than the one used earlier in
the SPUDD paper, and their own artificial data sets (of which no details
are given). Also, a more detailed discussion of generating heuristics
would have added weight to the paper.
As the authors themselves point out, finding more generalized
techniques for exploiting structure in very large state spaces, and
incorporating them into DT planners is a very interesting direction for
future research.
This archive was generated by hypermail 2.1.6 : Wed Nov 19 2003 - 01:11:00 PST