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.

本文介绍了符号动态规划（SDP）技术的扩展，提供了一种能够处理离散和连续状态的马尔可夫决策过程（DC-MDP）的最优解决方案，在 XADD 中引入约束基剪枝以提高效率。SDP 与 XADD 用于声明性问题的自动规划，从而实现在 DC-MDP 的线性和非线性函数中生成最优解决方案。

离散与连续状态MDP的符号动态规划