SPUDD: Stochastic Planning using Decision Diagrams
  Markov decisions processes (MDPs) are becoming increasing popular as models
of decision theoretic planning. While traditional dynamic programming methods
perform well for problems with small state spaces, structured methods are
needed for large problems. We propose and examine a value iteration algorithm
for MDPs that uses algebraic decision diagrams(ADDs) to represent value
functions and policies. An MDP is represented using Bayesian networks and ADDs
and dynamic programming is applied directly to these ADDs. We demonstrate our
method on large MDPs (up to 63 million states) and show that significant gains
can be had when compared to tree-structured representations (with up to a
thirty-fold reduction in the number of nodes required to represent optimal
value functions).
