Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
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.
Keywords: null
Pages: 146-153
PS Link:
PDF Link: /papers/04/p146-feng.pdf
BibTex:
@INPROCEEDINGS{Feng04,
AUTHOR = "Zhengzhu Feng and Shlomo Zilberstein",
TITLE = "Region-Based Incremental Pruning for POMDPs",
BOOKTITLE = "Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-04)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2004",
PAGES = "146--153"
}


hosted by DSL   •   site info   •   help