Improper Filter Reduction

Abstract

Combinatorial 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.