Decision Processes In Influence Diagrams: Formulation and Analysis

Abstract

Abstract : This thesis addresses the problem of extending influence diagram theory such that decision processes can be effectively modeled within this graphical modeling language. Specifically, the extension allows value function separability and the principle of optimality to be captured in an influence diagram and then used in analysis. To accomplish this, the concept of a subvalue node has been developed. The set of value preserving operations on influence diagrams have been expanded to include operations that exploit the presence of these nodes. Also an algorithm has been developed to solve influence diagrams with subvalue nodes. This work is important from two perspectives. From the decision analysis perspective, it allows a full and simple exploitation of all separability in the value function of a decision problem. Importantly, this means that algorithms can be designed to solve influence diagrams that automatically recognize the opportunity for applying the principle of optimality. From the decision processes perspective, influence diagrams with subvalue nodes allow efficient formulation and solution of nonstandard decision processes. Also it allows the conditional independence among the variables in the problem to be exploited. This significantly reduces the data storage requirements and computational complexity of solving the problem. Finally, the influence diagram with subvalue nodes enhances understanding of many of the critial characteristics of various decision processes.