Factored Probabilistic Belief Tracking
  The problem of belief tracking in the presence of stochastic actions and
observations is pervasive and yet computationally intractable. In this work we
show however that probabilistic beliefs can be maintained in factored form
exactly and efficiently across a number of causally closed beams, when the
state variables that appear in more than one beam obey a form of backward
determinism. Since computing marginals from the factors is still
computationally intractable in general, and variables appearing in several
beams are not always backward-deterministic, the basic formulation is extended
with two approximations: forms of belief propagation for computing marginals
from factors, and sampling of non-backward-deterministic variables for making
such variables backward-deterministic given their sampled history. Unlike,
Rao-Blackwellized particle-filtering, the sampling is not used for making
inference tractable but for making the factorization sound. The resulting
algorithm involves sampling and belief propagation or just one of them as
determined by the structure of the model.
