Automatic reduction of combinatorial filters

Abstract

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