Accelerating combinatorial filter reduction through constraints
This work addresses a computational bottleneck in robot automation, offering incremental improvements in efficiency for filter reduction.
The paper tackles the NP-complete problem of combinatorial filter reduction for minimalist robots by proposing a new formalization with polynomial constraints, showing that conjunctive normal form constraints are most effective and introducing just-in-time constraint generation to improve efficiency.
Reduction of combinatorial filters involves compressing state representations that robots use. Such optimization arises in automating the construction of minimalist robots. But exact combinatorial filter reduction is an NP-complete problem and all current techniques are either inexact or formalized with exponentially many constraints. This paper proposes a new formalization needing only a polynomial number of constraints, and characterizes these constraints in three different forms: nonlinear, linear, and conjunctive normal form. Empirical results show that constraints in conjunctive normal form capture the problem most effectively, leading to a method that outperforms the others. Further examination indicates that a substantial proportion of constraints remain inactive during iterative filter reduction. To leverage this observation, we introduce just-in-time generation of such constraints, which yields improvements in efficiency and has the potential to minimize large filters.