University of Tehran Journal of Algorithms and Computation 2476-2776 50 1 2018 06 01 Improper Filter Reduction 69 99 68340 EN Fatemehzahra Saberifar Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran. Ali Mohades Amirkabir University of Technology Mohammadreza Razzazi Amirkabir University of Technology Jason J. M. O'Kane University of South Carolina Journal Article 2018 02 08 Combinatorial filters, which are discrete representations of estimation processes, have been the subject of increasing interest from the robotics community in recent years. % This paper considers automatic reduction of combinatorial filters to a given size, even if that reduction necessitates changes to the filter's behavior. % We introduce an algorithmic problem called emph{improper filter reduction}, in which the input is a combinatorial filter $F$ along with an integer $k$ representing the target size. The output is another combinatorial filter $F'$ with at most $k$ states, such that the difference in behavior between $F$ and $F'$ is minimal. We present two methods for measuring the distance between pairs of filters, describe dynamic programming algorithms for computing these distances, and show that improper filter reduction is NP-hard under these methods. % We then describe two heuristic algorithms for improper filter reduction, one changed{greedy sequential} approach, and one randomized global approach based on prior work on weighted improper graph coloring. We have implemented these algorithms and analyze the results of three sets of experiments.

https://jac.ut.ac.ir/article_68340_4cb7b0907ca92ebe199a2f85d9a913d3.pdf