AAAI Publications, Thirteenth Annual Symposium on Combinatorial Search

Font Size: 
Heuristic AND/OR Search for Solving Influence Diagram
Junkyu Lee, Radu Marinescu, Rina Dechter

Last modified: 2020-05-08


An influence diagram is a graphical representation of sequential decision-making under uncertainty, defining a structured decision problem by conditional probability functions and additive utility functions over discrete state and action variables. The task of finding the maximum expected utility of influence diagrams is closely related to the cost-optimal probabilistic planning, stochastic programmings, or model-based reinforcement learning. In this position paper, we address the heuristic search for solving influence diagram, where we generate admissible heuristic functions from graph decomposition schemes. Then, we demonstrate how such heuristics can guide an AND/OR branch and bound search. Finally, we briefly discuss the future directions for improving the quality of heuristic functions and search strategies.

Full Text: PDF