Equivalence Notions for State-Space Minimization of Combinatorial Filters
Hazhar Rahmani, Jason M. O’Kane · IEEE Transactions on Robotics · 2021
Combinatorial filters are formal structures for filtering and reasoning over discrete sensor data. This article presents a series of results addressing the question whether thefilter minimization(FM) problem, an NP-hard problem of state-space reduction on such filters, and a variant of it, thefilter partitioning minimization(FPM) problem, 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 ofbisimulationand show that, although bisimulation always yields feasible solutions to FM and FPM problems, it does not necessarily induce optimal solutions. We also establish a connection between filter reduction and the notion ofsimulation; specifically, we show that the FM problem is equivalent to the problem of inducing a minimal filter that simulates a given filter. We then introduce a variant of bisimulation, which we callcompatibility, and prove that the FPM problem can always be solved by computing the quotient of the input filter under acompatibility equivalencerelation having a minimum number of equivalence classes. On the other hand, computing optimal solutions to the FM problem requires to look for relations beyond equivalence relations, and in fact, the FM problem can be solved by computing the quotient of the original filter under a closed covering of the state space with the minimum number of compatibility classes. Subsequently, we introduce two special relations,the union of all compatibility relationsandthe mergeability relation, which 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 problems are solvable in polynomial time.