Solving Influence Diagrams using Branch and Bound Search

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 depthirst-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