Theses and Dissertations

Issuing Body

Mississippi State University

Advisor

Hansen, Eric A.

Committee Member

Banicescu, Ioana

Committee Member

Iannucci, Stefano

Committee Member

Rahimi, Shahram

Date of Degree

12-13-2024

Original embargo terms

Worldwide

Document Type

Dissertation - Open Access

Major

Computer Science

Degree Name

Doctor of Philosophy (Ph.D.)

College

James Worth Bagley College of Engineering

Department

Department of Computer Science and Engineering

Abstract

Exact dynamic programming algorithms for planning problems that are represented as partially observable Markov decision processes rely on a subroutine that removes, or ``prunes", dominated vectors from sets of vectors that represent piecewise-linear and convex value functions. The classic vector pruning subroutine solves one linear program per vector, where the number of variables is equal to the size of the state space and the number of constraints is equal to the number of vectors shown so far to be undominated. Thus, its scalability is limited not only by the number of linear programs it solves, but especially by their size. Recent work shows how to improve the performance of this vector pruning subroutine by limiting the number of constraints in the linear programs it solves, using a row-generation technique. This work shows how to further improve its performance by similarly limiting the number of variables using a column-generation technique, which improves scalability with respect to the size of the state space. This new technique allows vector pruning to be used for problems with a much larger state space than was previously possible. Additionally, the most widely used dynamic programming algorithm for solving partially observable Markov decision processes is bottlenecked by vector pruning during its cross-sum step. This work adapts geometrical insights for speeding up the cross-sum step to the row and column generation technique, showing how to improve its performance even further. These techniques speed up exact algorithms for solving POMDPs as well as related optimization problems with hidden variables for which similar vector pruning techniques are used, such as multi-objective planning problems, partially observable stochastic games, and in a recent variable elimination algorithm for influence diagrams.

Download

Share

COinS