Paper ID: 2309.06664

A fixed-parameter tractable algorithm for combinatorial filter reduction

Yulin Zhang, Dylan A. Shell

What is the minimal information that a robot must retain to achieve its task? To design economical robots, the literature dealing with reduction of combinatorial filters approaches this problem algorithmically. As lossless state compression is NP-hard, prior work has examined, along with minimization algorithms, a variety of special cases in which specific properties enable efficient solution. Complementing those findings, this paper refines the present understanding from the perspective of parameterized complexity. We give a fixed-parameter tractable algorithm for the general reduction problem by exploiting a transformation into clique covering. The transformation introduces new constraints that arise from sequential dependencies encoded within the input filter -- some of these constraints can be repaired, others are treated through enumeration. Through this approach, we identify parameters affecting filter reduction that are based upon inter-constraint couplings (expressed as a notion of their height and width), which add to the structural parameters present in the unconstrained problem of minimal clique covering. Compared with existing work, we precisely identify and quantitatively characterize those features that contribute to the problem's hardness: given a problem instance, the combinatorial core may be a fraction of the instance's full size, with a small subset of constraints needing to be considered, and even those may have directly identifiable couplings that collapse degrees of freedom in the enumeration.

Submitted: Sep 13, 2023