## Equivalence Notions for State-Space Minimization of Combinatorial Filters

Hazhar Rahmani, **Jason M. O'Kane**

*IEEE Transactions on Robotics*

vol. 37

no. 6

pp. 2117–2136

2021
**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}
}

*Last updated 2021-12-14.*