## On the relationship between bisimulation and combinatorial filter reduction

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

In *Proc. IEEE International Conference on Robotics and Automation*

2018
**Abstract**
Combinatorial filters are discrete structures for modeling and reasoning
about robotic systems. Such filters are of interest not only because of the
potential for reduction of the computational power needed to execute the
filter, but also for the insight they can sometimes provide into the
information requirements of certain robotic tasks. It is known that the
filter minimization problem —that is, for a given filter, to find a
combinatorial filter with the minimal number of states among all filters
with equivalent behavior— is NP-hard. Intuition might suggest that the
well-known notion of bisimulation might be of direct use for this
minimization problem. Indeed, the bisimilarity relation —the union of all
bisimulation relations over the state space of the original filter— is an
equivalence relation, and one might attempt to reduce a filter by merging
states that are equivalent under this relation. This paper studies this
relationship between bisimulation and combinatorial filter reduction.
Specifically, we show that every filter minimization problem can be solved
by computing a quotient of the input filter with some relation, but that
for some filters, the bisimilarity relation is not the correct relation for
this purpose. We also characterize the result of the bisimulation quotient
operation as the solution to a different, stricter filter minimization
problem, and identify several classes of filters for which a variant of
bisimulation, called compatibility, can be used to minimize filters in
polynomial time.

@inproceedings{RahOKa18,
author = {Hazhar Rahmani and Jason M. O'Kane},
booktitle = {Proc. IEEE International Conference on Robotics and Automation},
title = {On the relationship between bisimulation and combinatorial filter
reduction},
year = {2018}
}

*Last updated 2020-09-23.*