A central goal of research in artificial intelligence, operations research, and related fields is the development of algorithmic approaches to decision making under uncertainty. This project considers influence diagrams, a widely-used graphical model for representing and solving problems of sequential decision-making under imperfect information. Influence diagrams were originally developed to provide a more compact representation of a decision problem than is provided by a decision tree, which suffers from an exponential explosion in the number of its branches as a function of the number of variables in the model. Although influence diagrams provide a compact problem representation, standard algorithms for solving influence diagrams do not represent the solution to a decision problem in a similarly compact form. This project addresses this limitation by introducing a more compact graphical representation of decision strategies that improves the scalability of algorithms for solving influence diagrams, makes it easier for a human user to understand the recommended decision strategy, and allows a principled approach to approximation. In addition, the project develops a new approach to solving influence diagrams based on branch-and-bound search, including an incremental approach to probabilistic inference.
The algorithms and software tools developed from this project will improve the scalability and utility of influence diagrams as an approach to automated decision making under uncertainty. These contributions will have a broad impact in the many disciplines in which influence diagrams are applied, including medical decision analysis and support, therapy plan selection, user modeling, information retrieval, climate change analysis, and many others.
