SPUDD: Stochastic Planning using Decision Diagrams
This work addresses the challenge of efficient decision-theoretic planning for large-scale problems, representing an incremental improvement over existing structured methods.
The authors tackled the problem of scaling Markov decision processes (MDPs) for large state spaces by proposing a value iteration algorithm using algebraic decision diagrams (ADDs) to represent value functions and policies, resulting in up to a thirty-fold reduction in nodes compared to tree-structured representations for MDPs with up to 63 million states.
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).