Automatic Reduction of Combinatorial Filters

Jason M. O'Kane, Dylan A. Shell
In Proc. IEEE International Conference on Robotics and Automation 2013.


We consider the problem of filtering whilst maintaining as little information as possible to perform a given task. The literature includes several illustrations of how adroit choices for state descriptions may lead to concise or even minimal filters tailored to specific tasks. We introduce an efficient algorithm which is able to reproduce these hand-crafted solutions. Specifically, our algorithm accepts as input an arbitrary combinatorial filter, expressed as a transition graph, and outputs an equivalent filter that uses fewer information states to complete the same filtering task. We also show that solving this problem optimally is NP-hard, and that the related decision problem is NP-complete. These hardness results justify the potentially sub-optimal output of our algorithm. In the experiments we describe, our algorithm produces optimal or near-optimal reduced filters for a variety of problem instances. These reduced filters are of interest for several reasons, including their direct application on platforms with severely limited computational power and in systems that require communication over low-bandwidth noisy channels. Moreover, inspection of reduced filters may provide insights into the structure of a problem that can guide the design of the other elements of a robot system.



  author       = {Jason M. O'Kane and Dylan A. Shell},
  title        = {Automatic Reduction of Combinatorial Filters},
  booktitle    = {Proc. IEEE International Conference on Robotics and
  year	       = {2013}

O'Kane's home page
O'Kane's publication list

Wed Sep 20 09:19:46 EDT 2017