Improper Filter Reduction
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, onechanged{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.
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.