Dynamic programming and influence diagrams

The concept of a super value node is developed to extend the theory of influence diagrams to allow dynamic programming to be performed within this graphical modeling framework. The operations necessary to exploit the presence of these nodes and efficiently analyze the models are developed. The key result is that by representing value function separability in the structure of the graph of the influence diagram, formulation is simplified and operations on the model can take advantage of the separability. From the decision analysis perspective, this allows simple exploitation of separability in the value function of a decision problem which can significantly reduce memory and computation requirements. Importantly, this allows algorithms to be designed to solve influence diagrams that automatically recognize the opportunity for applying dynamic programming. From the decision processes perspective, influence diagrams with super value nodes allow efficient formulation and solution of nonstandard decision process structures. They also allow the exploitation of conditional independence between state variables. Examples are provided that demonstrate these advantages.