Loading...
Please wait, while we are loading the content...
Similar Documents
Region-based dynamic programming for partially observable markov decision processes.
| Content Provider | CiteSeerX |
|---|---|
| Author | Feng, Zhengzhu |
| Abstract | We present a major improvement to the dynamic programming (DP) algorithm for solving partially observable Markov decision processes (POMDPs). Our technique first targets the cross-sum pruning step of the DP update, a key source of complexity in POMDP algorithms. Unlike previous approaches, which reason about the whole belief space, the algorithms we present divide the belief space into smaller regions and perform independent pruning in each region. Because the number of useful vectors over each region can be much smaller than those over the whole belief space, we show that the linear programs used in the pruning process can be made exponentially smaller. With this exponential improvement to cross-sum pruning, we shift our attention to the next bottleneck, the maximization pruning step. Using the same region-based reasoning, we identify two types of structures in the belief space of a POMDP and show how to exploit them to reduce significantly the number of constraints in the linear programs used for maximization pruning. We discuss future research directions on extending these techniques to improve the scalability of POMDP algorithms. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Region-based Dynamic Programming Partially Observable Markov Decision Process Linear Program Belief Space Pomdp Algorithm Whole Belief Space Observable Markov Decision Process Dynamic Programming Future Research Direction Key Source Maximization Pruning Useful Vector Cross-sum Pruning Step Exponential Improvement Previous Approach Pruning Process Dp Update Next Bottleneck Region-based Reasoning Major Improvement Cross-sum Pruning |
| Content Type | Text |
