From: Lucas Kreger-Stickles (lucasks_at_cs.washington.edu)
Date: Mon Nov 17 2003 - 08:49:53 PST
* Paper title/Author
SPUDD: Stochastic Planning using Decision Diagrams
Hoey, St-Aubin, Hu, and Boutilier
* One-line summary
The authors describe an algorithm for solving Markov decision processes
that uses algebraic decision diagrams or ADDs.
* The (two) most important ideas in the paper, and why
Two of the most important ideas of the paper is that ADDs -can- lend
themselves toward a compact representation of planning problems and that
the authors have created an algorithm (SPUDD) which utilizes ADDs to
solve MDPs.
Another important idea is that ADDs are NOT always a more compact
representation and can occasionally require an exponentially larger
representation than certain trees. While this is not a favorable
conclusion for their algorithm it is certainly an important idea of the
paper.
* The one or two largest flaws in the paper
In my mind the largest flaw of the paper is the 'glossing over" that
they do of the problems that they encounter ie:
-ADDs can be exponentially bigger than well chosen trees but... we don't
seem to think that will happen very often.
In addition, while I appreciate the use of many diagrams to convey what
they are talking about (since prose regarding structures one has never
come across before can be hard to follow), they often place the diagrams
and algorithms several pages after they talk about our reference them
which makes following along difficult.
*future work
While not terribly complex, I think it would be nice to see some
empirical run-time data. The authors discount theirs, saying that it
depends too much on implementation specifics and their paper is mostly
about space requirements but it would be nice to see some results that
attempt to deal with these specifics and which indicate run time results
as compared to other techniques.
This archive was generated by hypermail 2.1.6 : Mon Nov 17 2003 - 10:48:01 PST