An extension of lazy evaluation for influence diagrams avoiding redundant variables in the potentials

Abstract

Standard methods for solving influence diagrams consist in stepwise elimination of variables, and along with elimination of a variable a set of new potentials over new domains is calculated. It is well known that these methods tend to produce unnecessarily large domains resulting in excessive consumption of time and memory.

The lazy evaluation method represents a partial solution to the problem. We extend any potential with two graphs over its domain representing the dependencies of variables.

When a node A is eliminated, all necessary structural information for establishing the minimal sets of domains for potentials is contained in these graphs. We push lazy evaluation a step more to avoid performing unnecessary multiplications and subsequent division with equivalent potentials.