Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
SPUDD: Stochastic Planning using Decision Diagrams
Jesse Hoey, Robert St-Aubin, Alan Hu, Craig Boutilier
Abstract:
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
Pages: 279-288
PS Link: http://www.cs.ubc.ca/spider/staubin/Spudd/index.html
PDF Link: /papers/99/p279-hoey.pdf
BibTex:
@INPROCEEDINGS{Hoey99,
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"
}


hosted by DSL   •   site info   •   help