Accelerating combinatorial filter reduction through constraints
Accelerating combinatorial filter reduction through constraints
复制标题
DOI：
10.1109/icra48506.2021.9562036
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Yulin Zhang;Hazhar Rahmani;Dylan A. Shell;J. O’Kane
中科院分区：
文献类型：
--
作者：
Yulin Zhang;Hazhar Rahmani;Dylan A. Shell;J. O’Kane
组合过滤器的减少涉及压缩机器人使用的状态表示。这种优化出现在极简机器人的自动化构造中。但是，精确组合滤波器约简是一个NP完全问题，目前所有的技术要么是不精确的，要么是形式化的，具有指数级的许多约束。本文提出了一种新的形式化，只需要多项式数量的约束，并在三种不同的形式：非线性，线性和合取范式这些约束的特点。实验结果表明，合取范式中的约束最有效地捕捉问题，从而导致优于其他方法的方法。进一步的检查表明，在迭代滤波器减少的约束的相当大的比例保持不活动。为了利用这一观察结果，我们引入了这种约束的即时生成，这提高了效率，并有可能最大限度地减少大型过滤器。
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.