Theses and Dissertations

Jinchuan Shi

Issuing Body

Mississippi State University

Advisor

Hansen, Eric.

Committee Member

Banicescu, Ioana.

Committee Member

Swan, Edward J., II

Committee Member

Young, Maxwell.

Date of Degree

5-4-2018

Document Type

Dissertation - Open Access

Major

Computer Science

Degree Name

Doctor of Philosophy

College

James Worth Bagley College of Engineering

Department

Department of Computer Science and Engineering

Abstract

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.

URI

https://hdl.handle.net/11668/16640

Download

Share

COinS