From: Xu Miao (xm_at_u.washington.edu)
Date: Mon Nov 17 2003 - 10:29:49 PST
Title: SPUDD:Stochastic Planning using Decision Diagrams
Author: Jesse Hoey ,etc.
Summary:
This paper describes a new SPUDD algorithm for MDPs, demonstrates
the a significant improvement from a tree-stuctured represented algorithm.
Important Ideas:
1. By using Binary Decision Diagram instead of Binary Decision
Tree, we can reduce a lot and save many redandent computational time and
duplicated space. Also the author developed the ADD representation so that
it can map a binary space to a real space and represent the real value
problem. Usually the real space problem always cause the Curse of
dimensionality problem, but ADD can effecively dealling with real value
problem without using expontential time and space. At the same time, the
usage of BDD makes it possible that DP without complete state enumeration,
which is SPUDD algorithm.
2. Some optimization techniques are introduced or discussed, for
example, tuning knob and heuristics reordering of variables, so that the
SPUDD can deal with some special cases.
Flaws:
Although they claim it can deal with real value, but actually the
variables are still boolean. And factoring a real value variable into
several boolean variables is still gonna make the problem exponentially
fast.
Possible research directions:
1. Optimization methods although be disscussed, some of them are
still not been implemented, such as dynamic variabl reodering.
2. Other DP algorithm to be applied, like they claimed.
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 10:29:10 PST