Solving Limited Memory Influence Diagrams

D. D. Mauá, C. P. de Campos, M. Zaffalon

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)97-140
Number of pages44
JournalJournal of Artificial Intelligence Research
Volume44
DOIs
Publication statusPublished - 2012

Fingerprint

Dive into the research topics of 'Solving Limited Memory Influence Diagrams'. Together they form a unique fingerprint.

Cite this