Fatemehzahra Saberifar; Ali Mohades; Mohammadreza Razzazi; Jason J. M. O'Kane
Abstract
Combinatorial filters, which are discrete representations of estimationprocesses, have been the subject of increasing interest from the roboticscommunity in recent years.%This paper considers automatic reduction of combinatorial filters to a givensize, even if that reduction necessitates changes to the ...
Read More
Combinatorial filters, which are discrete representations of estimationprocesses, have been the subject of increasing interest from the roboticscommunity in recent years.%This paper considers automatic reduction of combinatorial filters to a givensize, 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$ alongwith an integer $k$ representing the target size. The output is anothercombinatorial filter $F'$ with at most $k$ states, such that the differencein 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, andshow 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 workon weighted improper graph coloring. We have implemented these algorithmsand analyze the results of three sets of experiments.