First-Order Open-Universe POMDPs

Abstract

Open-universe probability models handle uncertainty over the existence and identity of objects, forms of uncertainty occurring in many real-world situations. We examine the problem of extending a declarative probabilistic programming language to define decision problems (specifically, POMDPs) and identify non-trivial representational issues in describing an agent's capability for observation and action. We present semantic definitions that lead to POMDP specifications provably consistent with the sensor and actuator capabilities of the agent, and describe a variant of point-based value iteration for solving open-universe POMDPs, handling cases such as seeing a new object and picking it up that could not previously be represented or solved.