Publications

Point-Based Value Iteration for Finite-Horizon POMDPs

Erwin Walraven and Matthijs T. J. Spaan. Point-Based Value Iteration for Finite-Horizon POMDPs. Journal of Artificial Intelligence Research, 65:307–341, 2019.

Download

pdf [948.4kB] HTML

Abstract

Partially Observable Markov Decision Processes (POMDPs) are a popular formalism for sequential decision making in partially observable environments. Since solving POMDPs to optimality is a difficult task, point-based value iteration methods are widely used. These methods compute an approximate POMDP solution, and in some cases they even provide guarantees on the solution quality, but these algorithms have been designed for problems with an infinite planning horizon. In this paper we discuss why state-of-the-art point-based algorithms cannot be easily applied to finite-horizon problems that do not include discounting. Subsequently, we present a general point-based value iteration algorithm for finite-horizon problems which provides solutions with guarantees on solution quality. Furthermore, we introduce two heuristics to reduce the number of belief points considered during execution, which lowers the computational requirements. In experiments we demonstrate that the algorithm is an effective method for solving finite-horizon POMDPs.

BibTeX Entry

@Article{Walraven19jair,
  author =       {Erwin Walraven and Matthijs T. J. Spaan},
  title =        {Point-Based Value Iteration for Finite-Horizon {POMDPs}},
  journal =      {Journal of Artificial Intelligence Research},
  volume =       65,
  pages =        {307--341},
  year =         2019
}

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