From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Fri Apr 18 2003 - 14:34:50 PDT
I examined the SPUDD planner through its on-line web interface and by
skimming SPUDD: "Stochastic Planning using Decision Diagrams" by Jesse
Hoey, Robert St-Aubin, Alan Hu and Craig Boutilier[1]. This version of
SPUDD takes as input a text file describing the problem to be solved in a
proprietary format. This format includes the variables in the problem,
the actions, the associated probability of transition matrix, a reward
function, a discout factor and a threshold. As output, this web
interfaces provides two .pdf files pictorially giving the policy found,
and a summary of the value of being in each state.
SPUDD is based on value iteration, and in terms of operation, is very
similar. For example, the discount factor works exactly as one would
expect in classical value iteration. The threshold value specifies how
small the changes in state "value" must be before termination. The
examples I tried were too small to characterize the relationship between
this parameter and run-time. Most of my experiements with SPUDD were
related to these two parameters and their interaction with the reward
function.
My only complaint I have with SPUDD is the lack of documentation for its
description file format. It took me a while to fully understand how the
transitions were encoded - a better commented example file would be a
great help.
What I liked best about SPUDD was the representation chosen for policies -
the ADD (Algebraic Decision Diagram). This essentially looks like a
decision tree, with a node for each variable, but where all common
subtrees have been fused together. This representation provides an
advantage over a simple table due to its size: as long some entries in
such a table have the same values, they can be fused together, eliminating
some wasted space. The ADD representation seeks to do this. Of course,
not every domain can exploit this, but I believe most STRIPS-like domains
can. The ADD form was used for both of SPUDD's outputs, and for its
internal representation while planning.
In terms of future work, I'd like to see how a relatively simple
improvement to the ADD form would help out SPUDD. In its current form,
ADD does not exploit symmetry - it just fuses together subtrees
(subgraphs, actually) iff they are exactly the same. An even more compact
representation would be a "parameterized ADD", where we also fuse subtrees
when they have the same shape, but different variables. We would then
label the fused subtree with the possible sets of variables that could be
used in those fused nodes. This should further reduce the size of the
graph, resulting in a more compact representation. Clearly, this would
only work for certain domains that exhibit a particular type of symmetry,
but I think this would be fairly common in real-life STRIPS problems.
[1] In Proceedings of the Fifteenth Conference on Uncertainty in
Artificial Intelligence (UAI 99), Stockholm, Sweden. Linked to from the
SPUDD homepage.
This archive was generated by hypermail 2.1.6 : Fri Apr 18 2003 - 14:34:51 PDT