State-Space Abstractions for Probabilistic Inference: A Systematic
  Review
  Tasks such as social network analysis, human behavior recognition, or
modeling biochemical reactions, can be solved elegantly by using the
probabilistic inference framework. However, standard probabilistic inference
algorithms work at a propositional level, and thus cannot capture the
symmetries and redundancies that are present in these tasks. Algorithms that
exploit those symmetries have been devised in different research fields, for
example by the lifted inference-, multiple object tracking-, and modeling and
simulation-communities. The common idea, that we call state space abstraction,
is to perform inference over compact representations of sets of symmetric
states. Although they are concerned with a similar topic, the relationship
between these approaches has not been investigated systematically. This survey
provides the following contributions. We perform a systematic literature review
to outline the state of the art in probabilistic inference methods exploiting
symmetries. From an initial set of more than 4,000 papers, we identify 116
relevant papers. Furthermore, we provide new high-level categories that
classify the approaches, based on common properties of the approaches. The
research areas underlying each of the categories are introduced concisely.
Researchers from different fields that are confronted with a state space
explosion problem in a probabilistic system can use this classification to
identify possible solutions. Finally, based on this conceptualization, we
identify potentials for future research, as some relevant application domains
are not addressed by current approaches.
