Point-Based Value Iteration for Finite-Horizon POMDPs

Erwin Walraven, Matthijs T.J. Spaan

Research output: Contribution to journalArticleScientificpeer-review

120 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)307-341
Number of pages35
JournalThe Journal of Artificial Intelligence Research
Volume65
Publication statusPublished - 2019

Fingerprint

Dive into the research topics of 'Point-Based Value Iteration for Finite-Horizon POMDPs'. Together they form a unique fingerprint.

Cite this