Region-based incremental pruning for POMDPs
Zhengzhu Feng, Shlomo Zilberstein · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · 2004
We present a major improvement to the incre-mental pruning algorithm for solving partially observable Markov decision processes. Our tech-nique targets the cross-sum step of the dynamic programming (DP) update, a key source of com-plexity in POMDP algorithms. Instead of reason-ing about the whole belief space when pruning the cross-sums, our algorithm divides the belief space into smaller regions and performs indepen-dent pruning in each region. We evaluate the ben-efits of the new technique both analytically and experimentally, and show that it produces very significant performance gains. The results con-tribute to the scalability of POMDP algorithms to domains that cannot be handled by the best exist-ing techniques. 1