Symbolic Heuristic Search Value Iteration for Factored POMDPs

Abstract

We propose Symbolic heuristic search value iteration (Symbolic HSVI) algorithm, which extends the heuris-tic search value iteration (HSVI) algorithm in order to handle factored partially observable Markov decision processes (factored POMDPs). The idea is to use al-gebraic decision diagrams (ADDs) for compactly rep-resenting the problem itself and all the relevant inter-mediate computation results in the algorithm. We lever-age Symbolic Perseus for computing the lower bound of the optimal value function using ADD operators, and provide a novel ADD-based procedure for computing the upper bound. Experiments on a number of standard factored POMDP problems show that we can achieve an order of magnitude improvement in performance over previously proposed algorithms. Partially observable Markov decision processes (POMDPs) are widely used for modeling stochastic sequential deci-sion problems with noisy observations. However, when we model real-world problems, we often need a compact rep-resentation since the model may result in a very large num-ber of states when using the flat, table-based representation. Factored POMDPs (Boutilier & Poole 1996) are one type of such compact representation. Given a factored POMDP, we have to design an algo-rithm that does not explicitly enumerate all the states in the model. For this purpose, it has gained popularity over the years to use the algebraic decision diagram (ADD) represen-tation (Bahar et al. 1993) of all the vectors and matrices used