Dynamic Programming for POMDPs Using a Factored State Representation

Contingent planning -- constructing a plan in which action seh, ction is contingent on imperfect infornlation received during plan execution - can be forma]ized ~s the problemof solving a partially observabh, Markov decision process (POMDP). Traditional dynamic programmiug algorittmm for POMDPsuse a flat state representation that enunmrat(. sall possible states au, l staCe tr~msitions. By contrast, AI plmming algorithms use a fiwt. ored state rcpres(. ntation that supports state abstraction and allows prolfloms with large state spaces to be represented and solved nmre efficiently. Boutilier ~mdPeele (1996) have recently described howa factored state rcpresent. ation c~ut be exploited by a dynamic programmingalgorithm for POMDPs. We. extend their framework, describe an implementationof it, test its performance, and assess how mucl~ this approach improves the computational effk: iency of dynaanic l)rogrammingfi, r POMDPs.

Authors

• Eric A. Hansen
• Zhengzhu Feng

Keywords

No keywords are indexed for this paper.