Theses and Dissertations


Jinchuan Shi

Issuing Body

Mississippi State University


Hansen, Eric.

Committee Member

Banicescu, Ioana.

Committee Member

Swan, Edward J., II

Committee Member

Young, Maxwell.

Date of Degree


Document Type

Dissertation - Open Access


Computer Science

Degree Name

Doctor of Philosophy


James Worth Bagley College of Engineering


Department of Computer Science and Engineering


An influence diagram is a widely-used graphical model for representing and solving problems of sequential decision making under imperfect information. A closely-related model for the same class of problems is a partially observable Markov decision process (POMDP). This dissertation leverages the relationship between these two models to develop improved algorithms for solving influence diagrams. The primary contribution is to generalize two classic dynamic programming algorithms for solving influence diagrams, Arc Reversal and Variable Elimination, by integrating them with a dynamic programming technique originally developed for solving POMDPs. This generalization relaxes constraints on the ordering of the steps of these algorithms in a way that dramatically improves scalability, especially in solving complex, multi-stage decision problems. A secondary contribution is the adoption of a more compact and intuitive representation of the solution of an influence diagram, called a strategy. Instead of representing a strategy as a table or as a tree, a strategy is represented as an acyclic graph, which can be exponentially more compact, making the strategy easier to interpret and understand.