First-Order Open-Universe POMDPs: Formulation and Algorithms

Siddharth Srivastava, Paul Ruan, Xiang Cheng, Stuart Russell
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:206-215, 2014.

Abstract

Open-universe probability models, representable by a variety of probabilistic programming languages (PPLs), 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 PPL to define decision problems (specifically, 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 semantic definitions that lead to POMDP specifications provably consistent with the sensor and actuator capabilities of the agent. We also describe a variant of point-based value iteration for solving open-universe POMDPs. Thus, we handle cases—such as seeing a new object and picking it up—that could not previously be represented or solved.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-srivastava14a, title = {First-Order Open-Universe POMDPs: Formulation and Algorithms}, author = {Srivastava, Siddharth and Ruan, Paul and Cheng, Xiang and Russell, Stuart}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {206--215}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/srivastava14a/srivastava14a.pdf}, url = {https://proceedings.mlr.press/r12/srivastava14a.html}, abstract = {Open-universe probability models, representable by a variety of probabilistic programming languages (PPLs), 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 PPL to define decision problems (specifically, 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 semantic definitions that lead to POMDP specifications provably consistent with the sensor and actuator capabilities of the agent. We also describe a variant of point-based value iteration for solving open-universe POMDPs. Thus, we handle cases—such as seeing a new object and picking it up—that could not previously be represented or solved.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T First-Order Open-Universe POMDPs: Formulation and Algorithms %A Siddharth Srivastava %A Paul Ruan %A Xiang Cheng %A Stuart Russell %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-srivastava14a %I PMLR %P 206--215 %U https://proceedings.mlr.press/r12/srivastava14a.html %V R12 %X Open-universe probability models, representable by a variety of probabilistic programming languages (PPLs), 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 PPL to define decision problems (specifically, 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 semantic definitions that lead to POMDP specifications provably consistent with the sensor and actuator capabilities of the agent. We also describe a variant of point-based value iteration for solving open-universe POMDPs. Thus, we handle cases—such as seeing a new object and picking it up—that could not previously be represented or solved. %Z Reissued by PMLR on 04 October 2026.
APA
Srivastava, S., Ruan, P., Cheng, X. & Russell, S.. (2014). First-Order Open-Universe POMDPs: Formulation and Algorithms. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:206-215 Available from https://proceedings.mlr.press/r12/srivastava14a.html. Reissued by PMLR on 04 October 2026.

Related Material