Relational partially observable mdps

Relational Markov Decision Processes (MDP) are a use-ful abstraction for stochastic planning problems since one can develop abstract solutions for them that are indepen-dent of domain size or instantiation. While there has been an increased interest in developing relational fully observ-able MDPs, there has been very little work on relational par-tially observable MDPs (POMDP), which deal with uncer-tainty in problem states in addition to stochastic action ef-fects. This paper provides a concrete formalization of re-lational POMDPs making several technical contributions to-ward their solution. First, we show that to maintain correct-ness one must distinguish between quantification over states and quantification over belief states; this implies that solu-tions based on value iteration are inherently limited to the finite horizon case. Second, we provide a symbolic dynamic programing algorithm for finite horizon relational POMDPs, solving them at an abstract level, by lifting the propositional incremental pruning algorithm. Third, we show that this algo-rithm can be implemented using first order decision diagrams, a compact representation for functions over relational struc-tures, that has been recently used to solve relational MDPs