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.
Saberifar,F , Mohades,A , Razzazi,M and J. M. O'Kane,J . (2018). Improper Filter Reduction. Journal of Algorithms and Computation, 50(1), 69-99. doi: 10.22059/jac.2018.68340
MLA
Saberifar,F , , Mohades,A , , Razzazi,M , and J. M. O'Kane,J . "Improper Filter Reduction", Journal of Algorithms and Computation, 50, 1, 2018, 69-99. doi: 10.22059/jac.2018.68340
HARVARD
Saberifar F, Mohades A, Razzazi M, J. M. O'Kane J. (2018). 'Improper Filter Reduction', Journal of Algorithms and Computation, 50(1), pp. 69-99. doi: 10.22059/jac.2018.68340
CHICAGO
F Saberifar, A Mohades, M Razzazi and J J. M. O'Kane, "Improper Filter Reduction," Journal of Algorithms and Computation, 50 1 (2018): 69-99, doi: 10.22059/jac.2018.68340
VANCOUVER
Saberifar F, Mohades A, Razzazi M, J. M. O'Kane J. Improper Filter Reduction. J. Algo. Comp.. 2018;50(1):69-99. doi: 10.22059/jac.2018.68340
