Solving Limited Memory Influence Diagrams

Details Solving Limited Memory Influence Diagrams Solving Limited Memory Influence Diagrams

2011-09-08

arxiv.org/abs/1109.1754v2

Computer Science

Artificial Intelligence

43 pages, 8 figures

Scientific paper

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 the problem is NP-hard even if the underlying graph structure of the problem has small treewidth and the variables take on a bounded number of states, but that a fully polynomial time approximation scheme exists for these cases. Moreover, we show that the bound on the number of states is a necessary condition for any efficient approximation scheme.

Affiliated with

Also associated with

No associations

Rating

Solving Limited Memory Influence Diagrams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving Limited Memory Influence Diagrams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Limited Memory Influence Diagrams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-475513