Equivalence notions for state-space minimization of combinatorial filters

Abstract Combinatorial filters are formal structures for filtering and reasoning over discrete sensor data. This paper presents a series of results addressing the question whether the filter minimization problem (FM), an NP-hard problem of state space reduction on such filters, and a variant of it, filter partitioning minimization problem (FPM), which requires the reduced filter to partition the state space of the original filter, can be solved via quotient operations under equivalence relations of the state space. We first consider the well-known notion of bisimulation and show that, although bisimulation always yields feasible solutions to FM and FPM, it does not necessarily induce optimal solutions. We also establish a connection between filter reduction and the notion of simulation; specifically, we show that FM is equivalent to the problem of inducing a minimal filter that simulates a given filter. We then introduce a variant of bisimulation, which we call compatibility, and prove that FPM can always be solved by computing the quotient of the input filter under a compatibility equivalence relation having a minimum number of equivalence classes. On the other hand, computing optimal solutions to FM requires to look for relations beyond equivalence relations, and in fact, FM can be solved by computing the quotient of the original filter under a closed covering of the state space with minimum number of compatibility classes. Subsequently, we introduce two special relations, the union of all compatibility relations and the mergeability relation, that are both computable in polynomial time. By analyzing where these two relations become an equivalence relation, we identify several classes of filters for which FM and FPM are solvable in polynomial time.

@article{RahOKa21,
  author = {Hazhar Rahmani and Jason M. O'Kane},
  doi = {10.1109/TRO.2021.3070967},
  journal = {IEEE Transactions on Robotics},
  number = {6},
  pages = {2117--2136},
  title = {Equivalence notions for state-space minimization of
           combinatorial filters},
  volume = {37},
  year = {2021}
}