First-Order Open-Universe POMDPs: Formulation and Algorithms
Technical Report Identifier: EECS-2013-243
Abstract: Interest in relational and first-order languages for probability models has grown rapidly in recent years, and with it the possibility of extending such languages to handle decision processes---both fully and partially observable. We examine the problem of extending a first-order, open-universe language to describe POMDPs and identify non-trivial representational issues in describing an agent's capability for observation and action---issues that were avoided in previous work only by making strong and restrictive assumptions. We present a method for representing actions and observations that respects formal specifications of the sensors and actuators available to an agent, and show how to handle cases---such as seeing an object and picking it up---that could not previously be represented. Finally, we argue that in many cases open-universe POMDPs require belief-state policies rather than automata policies. We present an algorithm and experimental results for evaluating such policies for open-unverse POMDPs.