From: Alan L. Liu (aliu_at_cs.washington.edu)
Date: Mon Nov 17 2003 - 02:03:04 PST
Paper Title: SPUDD: Stochastic Planning using Decision Diagrams
Authors: Jesse Hoey, et. al.
Summary:
The authors devised a new algorithm for solving factored Markov decision
process problems using algebraic decision diagrams. SPUDD uses Algebraic
decision diagrams (ADDs) that can exploit regularities in problem
structure, leading to significant time and space gains over traditional
planning representations.
Important Ideas:
I thought one of the key ideas was that, for MDPs with regularity in
structure, using ADDs could lead to much more compact representations
that avoid duplicating entire subtrees. This goes back to the idea that
gleaning insight from a problem can often lead to much better algorithms
for attacking it. In SPUDD's case, this insight leads to dramatic wins
in time and space requirements for some planning problems.
Flaws:
The justification for their "tuning knob" was valid enough, but its use
in examples was shaky. They even admitted to using it while they were
not clear about its effects on SPUDD's performacne. In the table of
results, they explained that they used some value for some of the
problems, and another value for some others, but they didn't say why
they chose those values, other than that their initial value wouldn't
work with 1GB RAM so they increased it.
I had a hard time following the paper in section 4, where the SPUDD
algorithm is introduced "in a conceptually clear way." Two specific
things gave me trouble -- almost all references to figures were on
separate pages from the figures themselves, and often-times the paper
would claim that something was self-evident (such as the regularity of
their example problem structure) or assume the reader was familiar with
the content of their paper references.
As an aside, the paper is riddled with typos and grammatical errors --
even the first sentence of the abstract has one! It's as though the
authors felt an intense hatred for spelling- and grammar-checkers. I
found it odd that they would put so little effort into polishing their
paper.
Open research questions:
SPUDD's performance depends heavily on the ordering of a problem's
variables. One question would be how to dynamic reorder variables to
achieve peak performance.
One might investigate the effects of limiting non-leaf nodes to Boolean
values. For more complex problems, might this be a big issue? Could
creating many different variables to overcome this limitation reduce the
compactness of the ADD representation?
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 02:03:05 PST