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

Arindam Khaled and Changhe Yuan and Eric Hansen

Abstract

A limited-memory influence diagram (LIMID) is a gen- eralization of a traditional influence diagram in which the assumptions of regularity and no-forgetting are re- laxed. Lauritzen and Nilsson (2001) introduced this model and proposed an iterative algorithm, called single policy updating (SPU), that converges to a locally opti- mal solution. In this paper, we describe a branch-and- bound algorithm that finds a globally optimal solution. Initial experiments suggest that the branch-and-bound approach scales better than SPU.

PDF

Bibtex

@INPROCEEDINGS{Khaled12solving,
author = {Arindam Khaled and Changhe Yuan and Eric Hansen},
title = {Solving Limited Memory Influence Diagrams Using Branch-and-Bound Search},
booktitle = {Proceedings of the International Symposium on Artificial Intelligence and Mathematics (ISAIM-12)},
address = {Ft Lauderdale, FL},
year = {2012}
}