Solving influence diagrams using heuristic search.
Changhe Yuan, Xiaojian Wu · 2010
(1,1) Existing methods for solving influence diagrams are mostly based on the bottom-up dynamic programming technique. These methods may waste computation in solving decision scenarios that have zero probabilities or are unreachable from any initial state by following an optimal decision policy. Heuristic search was applied in (Qi & Poole 1995) to address these limitations, but their algorithm uses a trivial infinity upper bound and fails to fully utilize the potential of heuristic search. This paper develops an improved heuristic search algorithm for solving influence diagrams based on a more informative upper bound computed by relaxing the models. The algorithm is shown to be able to significantly improve the efficiency and scalability of existing methods for solving influence diagrams. (a)