Theses and Dissertations

Issuing Body

Mississippi State University

Advisor

Hansen, Eric

Committee Member

Bethel, Cindy L.

Committee Member

Eksioglu, Burak

Date of Degree

12-14-2013

Document Type

Graduate Thesis - Open Access

Major

Computer Science

Degree Name

Master of Science (M.S.)

College

James Worth Bagley College of Engineering

Department

Department of Computer Science and Engineering

Abstract

A stochastic shortest path (SSP) problem is an undiscounted Markov decision process with an absorbing and zero-cost target state, where the objective is to reach the target state with minimum expected cost. This problem provides a foundation for algorithms for decision-theoretic planning and probabilistic model checking, among other applications. This thesis describes an implementation and evaluation of recently developed error bounds for SSP problems. The bounds can be used in a test for convergence of iterative dynamic programming algorithms for solving SSP problems, as well as in action elimination procedures that can accelerate convergence by excluding provably suboptimal actions that do not need to be re-evaluated each iteration. The techniques are shown to be effective for both decision-theoretic planning and probabilistic model checking.

URI

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

Download

Share

COinS