Dynamic programming for POMDPs using a factored state representation

Abstract

Contingent planning -- constructing a plan in which action selection is contingent on imperfect information received during plan execution -- can be formalized as the problem of solving a partially observable Markov decision process (POMDP). Traditional dynamic programming algorithms for POMDPs use a flat state representation that enumerates all possible states and state transitions. By contrast, AI planning algorithms use a factored state representation that supports state abstraction and allows problems with large state spaces to be represented and solved more efficiently. Boutilier and Poole (1996) have recently described how a factored state representation can be exploited by a dynamic programming algorithm for POMDPs. We extend their framework, describe an implementation and test its performance, and assess how much this approach improves the computational efficiency of dynamic programming for POMDPs. Introduction Many AI planning researchers have adopted Markov...