Publication

Back to overview

Solving limited memory influence diagrams

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Author Mauá D.D., de Campos C.P., Zaffalon M.,
Project Multi Model Inference for dealing with uncertainty in environmental models
Show all

Original article (peer-reviewed)

Journal Journal of Artificial Intelligence Research
Volume (Issue) 44
Page(s) 97 - 140
Title of proceedings Journal of Artificial Intelligence Research
DOI doi:10.1613/jair.3625

Open Access

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 1064 solutions. We show that these problems are NP-hard even if the underlying graph structure of the problem has low tree-width 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.
-