Publications

Accelerated Vector Pruning for Optimal POMDP Solvers

Erwin Walraven and Matthijs T. J. Spaan. Accelerated Vector Pruning for Optimal POMDP Solvers. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 3672–3678, 2017.

Download

pdf [446.1kB]

Abstract

Partially Observable Markov Decision Processes (POMDPs) are powerful models for planning under uncertainty in partially observable domains. However, computing optimal solutions for POMDPs is challenging because of the high computational requirements of POMDP solution algorithms. Several algorithms use a subroutine to prune dominated vectors in value functions, which requires a large number of linear programs (LPs) to be solved and it represents a large part of the total running time. In this paper we show how the LPs in POMDP pruning subroutines can be decomposed using a Benders decomposition. The resulting algorithm incrementally adds LP constraints and uses only a small fraction of the constraints. Our algorithm significantly improves the performance of existing pruning methods and the commonly used incremental pruning algorithm. Our new variant of incremental pruning is the fastest optimal pruning-based POMDP algorithm.

Supplementary Material

Supplement

BibTeX Entry

@InProceedings{Walraven17aaai,
  author =       {Erwin Walraven and Matthijs T. J. Spaan},
  title =        {Accelerated Vector Pruning for Optimal {POMDP}
                  Solvers},
  booktitle =    {Proceedings of the 31st AAAI Conference on
                  Artificial Intelligence},
  pages =        {3672--3678},
  year =         2017
}

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Generated by bib2html.pl (written by Patrick Riley) on Thu Feb 29, 2024 16:15:45 UTC