
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.
Recommended Citation
Bowman, Thomas Jonathan, "Improved vector pruning for partially observable Markov decision processes" (2024). Theses and Dissertations. 6446.
https://scholarsjunction.msstate.edu/td/6446