Solving Influence Diagrams using HUGIN, Shafer-Shenoy and Lazy Propagation
This work addresses computational efficiency in decision-making models for AI and operations research, but it is incremental as it builds on existing architectures.
The paper compares three architectures (HUGIN, Shafer-Shenoy, and Lazy Propagation) for evaluating influence diagrams, focusing on Limited Memory Influence Diagrams (LIMIDs) to compute optimal policies, and shows that Lazy Evaluation significantly increases computational savings.
In this paper we compare three different architectures for the evaluation of influence diagrams: HUGIN, Shafer-Shenoy, and Lazy Evaluation architecture. The computational complexity of the architectures are compared on the LImited Memory Influence Diagram (LIMID): a diagram where only the requiste information for the computation of the optimal policies are depicted. Because the requsite information is explicitly represented in the LIMID the evaluation can take advantage of it, and significant savings in computational can be obtained. In this paper we show how the obtained savings is considerably increased when the computations performed on the LIMID is according to the Lazy Evaluation scheme.