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 gen-eralized to solve LIMIDs, however, and only re-cently 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 re-lated to the approach of solving an influence di-agram by converting it to an equivalent decision tree, with the difference that the LIMID is con-verted to a much smaller decision graph that can be searched more efficiently.