From: Christophe Bisciglia (chrisrb_at_cs.washington.edu)
Date: Thu May 01 2003 - 23:05:38 PDT
Jesse Hoey, Robert St-Aubin, Alan Hu and Craig Boutilier SPUDD: Stochastic
Planning using Decision Diagrams
This paper presents SPUDD, a planner that uses ADDs for a new value
iteration algorithm for MDPs.
The main idea presented in this paper was the clever use of ADDs to reduce
the time and space requirements with respect to similar algorithms. This
allows larger problems to be solved faster.
Another interesting idea this paper uses is an explicit means to control
some of the time-space trade offs. To manage the increased diagram size
from step 3b of figure 3, SPUDD multiplies dual action diagrams
differently. Of course, in saving space, they waste time. To counter this,
they have the option of pre-computing the product of dual action diagrams.
However, this get expensive in the space domain. The solution was to break
the large diagram into a user defined number of subsets, and pre-computing
the action digrams in the subsets.
One thing that would have been nice would have been comparing SPUDD to
more planners. I'm not sure if SPI was the only thing avaialble at the
time, but the problems they described seemed like they should have worked
with others just fine.
As suggested in the conclusions, in would be very interesting to see what
kind of effects could be achieved through dynamic variable re-ordering.
This archive was generated by hypermail 2.1.6 : Thu May 01 2003 - 23:05:38 PDT