Efficient Maximization in Solving POMDPs
Zhengzhu Feng
Shlomo Zilberstein
Abstract
We present a simple, yet effective improvement to the dynamic
programming algorithm for solving partially observable
Markov decision processes. The technique targets the
vector pruning operation during the maximization step, a key
source of complexity in POMDP algorithms. We identify two
types of structures in the belief space and exploit them to reduce
significantly the number of constraints in the linear programs
used for pruning. The benefits of the new technique are
evaluated both analytically and experimentally, showing that
it can lead to significant performance improvement. The results
open up new research opportunities to enhance the performance
and scalability of several POMDP algorithms.
Download
[pdf]