From: Parag (parag_at_cs.washington.edu)
Date: Fri May 02 2003 - 10:59:59 PDT
SPUDD : Stochastic Planning using Decision Diagrams
Hoey, St-Aubin, Hu & Boutilier
The paper presents an efficient of way performing value
iteration in MDP's using the compact representation offered
by ADD's.
The main idea of the paper is to how the ADDs can be used
to compactly represent the MDPs. Realizing
that there is a lot of duplication in the SPI methods
which use decision trees, they propose using ADDs instead
to avoid duplication to save memory as well computation time.
In particular, they formulate how the value function as
well the action representation can be represented using
ADDs and how the policy iteration can be performed on
these compact representations without actually ever
enumerating the state space.
The authors also propose a couple of optimizations to
improve the space/time efficiency in the naive implementation,
which I did not quite understand.
The experimental section seems quite fair and gives some
insight into where SPUDD might not work that well.
I did not find any flaws in the paper. Though, one thing that
the authors themselves point out is that in the cases where
there is not much duplication, the benefit that you get
from using ADDs may be much less than overheads imposed
by the ADD representation. So, one could possible look at
automatically identifying the domains where it would be useful
to follow the above techniques, and where it might not be.
Another future direction, as pointed by author themselves, is
to exploit the idea of variable ordering to see if that
gives any significant benefits in the performance.
This archive was generated by hypermail 2.1.6 : Fri May 02 2003 - 10:59:59 PDT