Region-Based Incremental Pruning for POMDPs
Zhengzhu Feng
Shlomo Zilberstein
Abstract
We present a major improvement to the incremental
pruning algorithm for solving partially
observable Markov decision processes. Our technique
targets the cross-sum step of the dynamic
programming (DP) update, a key source of complexity
in POMDP algorithms. Instead of reasoning
about the whole belief space when pruning
the cross-sums, our algorithm divides the belief
space into smaller regions and performs independent
pruning in each region. We evaluate the benefits
of the new technique both analytically and
experimentally, and show that it produces very
significant performance gains. The results contribute
to the scalability of POMDP algorithms to
domains that cannot be handled by the best existing
techniques.
Download
[pdf]