From: Tal Shaked (tshaked_at_cs.washington.edu)
Date: Fri May 02 2003 - 12:06:16 PDT
SPUDD: Stochastic Planning using Decision Diagrams - J. Hoey, R. St-Aubin,
A. Hu, C. Boutilier
This paper discusses the methods and implementation of SPUDD, which uses
ADDs to represent value functions when computing classical value iteration.
This tends to lead to more compact representations than decision trees (up
to 30-40 when compared to SPI).
The idea of using ADDs to represent value functions and the algorithm of how
to do this to obtain an optimal policy is probably the most important
contribution.
The details were confusing and it might have helped to have more background
presented. However, the paper did discuss some problems, and ways to take
advantage of the structure for various optimizations. This also led to a
discussion of the trade-off between time and space, and a tunable knob
(although they admitted to not really fully understanding how it worked).
It was nice that the paper appeared more critical than usual in their
methods and specifically the strengths and weaknesses. In particular the
best and worst cases were given and compared, as well as adding superfluous
variables to show problems with the current implementation. There also was
a fair amount of explanation of the experiments, although they could have
pointed out the logarithmic scale used.
The experiment section only focuses on best and worst cases plus the factory
examples. It might be interesting to see how it does on other real world
examples to get a better idea of how much structure is really inherent. As
described, there can be work done in exploring the dynamic reordering of
variables perhaps based on new heuristics, that may significantly improve
the space and running time. They also mention that it should not be
difficult to extend ADDs to include multi-valued variables.
This archive was generated by hypermail 2.1.6 : Fri May 02 2003 - 12:07:13 PDT