Document Type : Research Paper
Authors
1 Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran.
2 Amirkabir University of Technology
3 University of South Carolina
Abstract
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.
Keywords
)