University of TehranJournal of Algorithms and Computation2476-277650120180601Improper Filter Reduction699968340ENFatemehzahraSaberifarDepartment of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran.AliMohadesAmirkabir University of TechnologyMohammadrezaRazzaziAmirkabir University of TechnologyJasonJ. M. O'KaneUniversity of South CarolinaJournal Article20180208Combinatorial filters, which are discrete representations of estimation<br />processes, have been the subject of increasing interest from the robotics<br />community in recent years.<br />%<br />This paper considers automatic reduction of combinatorial filters to a given<br />size, even if that reduction necessitates changes to the filter's behavior.<br />%<br />We introduce an algorithmic problem called emph{improper<br /> filter reduction}, in which the input is a combinatorial filter $F$ along<br />with an integer $k$ representing the target size. The output is another<br />combinatorial filter $F'$ with at most $k$ states, such that the difference<br />in behavior between $F$ and $F'$ is minimal.<br />We present two methods for measuring the distance between pairs of filters, describe dynamic <br />programming algorithms for computing these distances, and<br />show that improper filter reduction is NP-hard under these methods.<br />%<br />We then describe two heuristic algorithms for improper filter reduction, one<br />changed{greedy sequential} approach, and one randomized global approach based on prior work<br />on weighted improper graph coloring. We have implemented these algorithms<br />and analyze the results of three sets of experiments.https://jac.ut.ac.ir/article_68340_4cb7b0907ca92ebe199a2f85d9a913d3.pdf