Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Symbolic Dynamic Programming for Discrete and Continuous State MDPs
Scott Sanner, Karina Valdivia Delgado, Leliane Nunes de Barros
Abstract:
Many real-world decision-theoretic planning problems can be naturally modeled with discrete and continuous state Markov decision processes (DC-MDPs). While previous work has addressed automated decision-theoretic planning for DCMDPs, optimal solutions have only been defined so far for limited settings, e.g., DC-MDPs having hyper-rectangular piecewise linear value functions. In this work, we extend symbolic dynamic programming (SDP) techniques to provide optimal solutions for a vastly expanded class of DCMDPs. To address the inherent combinatorial aspects of SDP, we introduce the XADD - a continuous variable extension of the algebraic decision diagram (ADD) - that maintains compact representations of the exact value function. Empirically, we demonstrate an implementation of SDP with XADDs on various DC-MDPs, showing the first optimal automated solutions to DCMDPs with linear and nonlinear piecewise partitioned value functions and showing the advantages of constraint-based pruning for XADDs.
Keywords:
Pages: 643-652
PS Link:
PDF Link: /papers/11/p643-sanner.pdf
BibTex:
@INPROCEEDINGS{Sanner11,
AUTHOR = "Scott Sanner and Karina Valdivia Delgado and Leliane Nunes de Barros",
TITLE = "Symbolic Dynamic Programming for Discrete and Continuous State MDPs",
BOOKTITLE = "Proceedings of the Twenty-Seventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-11)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2011",
PAGES = "643--652"
}


hosted by DSL   •   site info   •   help