From: Alexander Yates (ayates_at_cs.washington.edu)
Date: Fri Apr 18 2003 - 16:39:08 PDT
Review of SPUDD, Stochastic Planning Using Decision Diagrams. Jesse Hoey,
Robert St-Aubin, Alan Hu, and Craig Boutilier.
SPUDD is a planner for STRIPS-like problems with uncertainty in the effects
of actions and the current state of the world. It makes the stationary
Markov assumption. It uses algebraic decision diagrams (ADDs) to make
relatively compact representations of the transition function, the reward
function, and the optimal value and policy functions.
I installed SPUDD and tried a number of their example domains. I had
trouble compiling the fltk-based GUI, so I was stuck looking at the text
output. Several things struck me about the planner. For one, the size of
the problems it handles are smaller than STRIPS planners, which makes sense
of course, since the problems are harder. The factory6 domain, for example,
has ~35 variables and ~20 actions, and it took about 13.6 minutes to solve.
I don't really know how fast STRIPS planners would be on comparably-sized
domains, but it seems like it's kinda slow.
I was also struck by the size of the output. Since STRIPS planners just
need to output a valid plan, their output is a function of the number of
actions in the plan. The output for SPUDD is an optimal policy, whose size
is a function of the size of the state space. Even for medium-sized
problems, like factory1 (21 variables), the optimal policy took up a file of
close to 6000 lines. The output is also fairly unintelligible to me,
although I expect that it would be much easier to read the diagrams (even if
they're big) than it is to read the text output.
Alex
This archive was generated by hypermail 2.1.6 : Fri Apr 18 2003 - 16:39:08 PDT