D. D. Maua, C. P. de Campos and M. Zaffalon (2012) "Solving Limited Memory Influence Diagrams", Volume 44, pages 97-140

PDF | PostScript | doi:10.1613/jair.3625

We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that these problems are NP-hard even if the underlying graph structure of the problem has low treewidth and the variables take on a bounded number of states, and that they admit no provably good approximation if variables can take on an arbitrary number of states.

Click here to return to Volume 44 contents list