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

Robotics