Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search
  A limited-memory influence diagram (LIMID) generalizes a traditional
influence diagram by relaxing the assumptions of regularity and no-forgetting,
allowing a wider range of decision problems to be modeled. 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 paper, we introduce 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.
