First-Order Open-Universe POMDPs: Formulation and Algorithms

Srivastava, S., Cheng, X., Russell, S., and Pfeffer, A.

Techical Report UCB/EECS-2013-243, EECS Department, University of California, Berkeley, CA (December 2013)

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.

For More Information

To learn more or request a copy of a paper (if available), contact Avi Pfeffer.

(Please include your name, address, organization, and the paper reference. Requests without this information will not be honored.)