SPUDD: Stochastic Planning using Decision Diagrams
Jesse Hoey, Robert St-Aubin, Alan Hu, Craig Boutilier
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).
Keywords: Planning, MDPs, value iteration, optimal policies, decision diagrams, decision trees
PS Link: http://www.cs.ubc.ca/spider/staubin/Spudd/index.html
PDF Link: /papers/99/p279-hoey.pdf
AUTHOR = "Jesse Hoey
and Robert St-Aubin and Alan Hu and Craig Boutilier",
TITLE = "SPUDD: Stochastic Planning using Decision Diagrams",
BOOKTITLE = "Proceedings of the Fifteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-99)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1999",
PAGES = "279--288"