Reasoning with Uncertainties Over Existence of Objects

In this paper we consider planning problems in relationalMarkov processes where objects may “appear” or “disap-pear”, perhaps depending on previous actions or propertiesof other objects. For instance, problems which require to ex-plicitly generate or discover objects fall into this category. Inour formulation this requires to explicitly represent the un-certainty over the number of objects (dimensions or factors)in a dynamic Bayesian networks (DBN). Many formalisms(also existing ones) are conceivable to formulate such prob-lems. We aim at a formulation that facilitates inference andplanning. Based on a specific formulation we investigate twoinference methods—rejection sampling and reversible-jumpMCMC—to compute a posterior over the process conditionedon the first and last time slice (start and goal state). We willdiscuss properties, efficiency, and appropriateness of eachone.