Symbolic Dynamic Programming for Discrete and Continuous State MDPs
This work addresses decision-theoretic planning problems in real-world applications by expanding the class of DC-MDPs that can be solved optimally, though it is incremental in extending existing SDP techniques.
The authors tackled the problem of finding optimal solutions for discrete and continuous state Markov decision processes (DC-MDPs) by extending symbolic dynamic programming (SDP) with XADDs, achieving the first optimal automated solutions for DC-MDPs with linear and nonlinear piecewise partitioned value functions.
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.