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 lan- guages (PPLs), handle uncertainty over the ex- istence and identity of objects—forms of uncer- tainty occurring in many real-world situations. We examine the problem of extending a declar- ative PPL to define decision problems (specifi- cally, POMDPs) and identify non-trivial repre- sentational issues in describing an agent’s ca- pability 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 speci- fications provably consistent with the sensor and actuator capabilities of the agent. We also de- scribe a variant of point-based value iteration for solving open-universe POMDPs. Thus, we han- dle cases—such as seeing a new object and pick- ing it up—that could not previously be repre- sented 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 lan- guages (PPLs), handle uncertainty over the ex- istence and identity of objects—forms of uncer- tainty occurring in many real-world situations. We examine the problem of extending a declar- ative PPL to define decision problems (specifi- cally, POMDPs) and identify non-trivial repre- sentational issues in describing an agent’s ca- pability 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 speci- fications provably consistent with the sensor and actuator capabilities of the agent. We also de- scribe a variant of point-based value iteration for solving open-universe POMDPs. Thus, we han- dle cases—such as seeing a new object and pick- ing it up—that could not previously be repre- sented 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 lan- guages (PPLs), handle uncertainty over the ex- istence and identity of objects—forms of uncer- tainty occurring in many real-world situations. We examine the problem of extending a declar- ative PPL to define decision problems (specifi- cally, POMDPs) and identify non-trivial repre- sentational issues in describing an agent’s ca- pability 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 speci- fications provably consistent with the sensor and actuator capabilities of the agent. We also de- scribe a variant of point-based value iteration for solving open-universe POMDPs. Thus, we han- dle cases—such as seeing a new object and pick- ing it up—that could not previously be repre- sented 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