Theses and Dissertations

Issuing Body

Mississippi State University

Advisor

Hansen, Eric

Committee Member

Yuan, Changhe

Committee Member

Reese, Donna S.

Committee Member

Archibald, Christopher

Date of Degree

12-11-2015

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

Influence diagrams (ID) are graphical frameworks for decision making in stochastic situations with mathematical models embedded in them. The goal of an optimal algorithm for an ID is to find a strategy that would maximize the expected utility. We will explain a few algorithms for influence diagrams in this thesis. There exists an obvious temporal ordering among decisions in an ID; and any information used in the past will always be available in the future: these two properties are respectively called the “regularity” and “noforgetting” assumptions. A limited memory influence diagram (LIMID) does not follow these two properties. The existing state-of-art depthirst-branch-and-bound (DFBnB) algorithm for solving influence diagrams does not scale very well due to the exponential increase of nodes proportional to the depth of the search (or total stages in the ID). In this paper, we propose and implement an algorithm that combines two widely used methods, depth first branch-andbound search (DFBnB) and value iteration with incremental pruning, for solving IDs and POMDPs, respectively. We describe an algorithm to convert the strategy tree to a strategy graph. Experiments show the effectiveness of these approaches. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this thesis, we provide an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.

URI

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

Comments

Branch and Bound Search||Limited Memory Influence Diagrams||Influence Diagrams

Download

Share

COinS