Alert button
Picture for Arindam Khaled

Arindam Khaled

Alert button

Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search

Add code
Bookmark button
Alert button
Sep 26, 2013
Arindam Khaled, Eric A. Hansen, Changhe Yuan

Figure 1 for Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search
Figure 2 for Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search
Figure 3 for Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search
Figure 4 for 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.

* Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013) 
Viaarxiv icon
Github IconAccess Paper or Ask Questions
Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon