### Solving Influence Diagrams Using Branch and Bound Search

## Abstract

Influence diagrams (ID) are graphical frameworks for decision making in stochastic
situations with mathematical models embedded in them. The goal of an optimal algorithm
for an ID is to find a strategy that would maximize the expected utility. We will explain
a few algorithms for influence diagrams in this thesis. There exists an obvious temporal
ordering among decisions in an ID; and any information used in the past will always be
available in the future: these two properties are respectively called the “regularity” and “noforgetting”
assumptions. A limited memory influence diagram (LIMID) does not follow
these two properties.

The existing state-of-art depth-first-branch-and-bound (DFBnB) algorithm for solving
influence diagrams does not scale very well due to the exponential increase of nodes proportional
to the depth of the search (or total stages in the ID). In this paper, we propose and
implement an algorithm that combines two widely used methods, depth first branch-andbound
search (DFBnB) and value iteration with incremental pruning, for solving IDs and
POMDPs, respectively. We describe an algorithm to convert the strategy tree to a strategy
graph. Experiments show the effectiveness of these approaches.

Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this thesis, we provide an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.

## Bibtex

@phdthesis{Khaled15solving,author = {Arindam Khaled},

title = {Solving Influence Diagrams Using Branch and Bound Search},

school = {Mississippi State University},

address = {Department of Computer Science and Engineering},

year = {2015}

}