Representation and Solution of Decision Problems Using Sequential Decision Diagrams
提出一种新图结构：序贯决策图，用于不确定性下序贯决策问题的建模、表述和求解，兼具影响图的紧凑性和决策树对非对称问题的处理能力，并给出统一框架和递归算法。
In this paper we introduce a new graph, the sequential decision diagram, to aid in modeling formulation, and solution of sequential decision problems under uncertainty. While as compact as an influence diagram, the sequential diagram captures the asymmetric and sequential aspects of decision problems as effectively as decision trees. We show that a unified framework consisting of a sequential diagram, an influence diagram, and a common formulation table for the problem’s data, suffices for compact and consistent representation, economical formulation, and efficient solution of (asymmetric) decision problems. In addition to asymmetry, the framework exploits other sources of computational efficiency, such as conditional independence and value function decomposition, making it also useful in evaluating dynamic-programming problems. The formulation table and recursive algorithm can be readily implemented in computers for solving large-scale problems. Examples are provided to illustrate the methodology in both asymmetric and symmetric cases.