Cover Combinatorial Filters and Their Minimization Problem
Cover Combinatorial Filters and Their Minimization Problem
复制标题
涵盖组合滤波器及其最小化问题
DOI：
10.1007/978-3-030-66723-8_6
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Shell, Dylan A.
中科院分区：
文献类型：
--
作者：
Zhang, Yulin;Shell, Dylan A.
最近的研究已经研究了最小化机器人资源足迹的算法。人们研究了组合滤波器（广泛使用的概率估计量的离散变体）类，并介绍了减少其空间需求的方法。本文扩展了现有的组合滤波器，通过引入一个自然的推广：覆盖组合滤波器。在解决新的-但仍然是NP-完全-问题的覆盖过滤器的最小化，我们表明，以前认为组合过滤器（和实际上被证明，声称，或假设）的多个概念实际上是假的。例如，最小化不会导致等价关系。我们给出了一个精确算法的覆盖过滤器最小化问题。与以前的工作（基于图着色），我们考虑了一种类型的覆盖问题，涉及一个新的条件约束，从中我们可以找到更一般的关系。除了解决更一般的问题，该算法还纠正了所有先前的滤波器减少方法中存在的缺陷。在采用SAT，该算法提供了一个有前途的基础，为未来的实际发展。
Recent research has examined algorithms to minimize robots’ resource footprints. The class of combinatorial filters (discrete variants of widely-used probabilistic estimators) has been studied and methods for reducing their space requirements introduced. This paper extends existing combinatorial filters by introducing a natural generalization: cover combinatorial filters. In addressing the new —but still NP-complete— problem of minimization of cover filters, we show that multiple concepts previously believed about combinatorial filters (and actually conjectured, claimed, or assumed to be) are in fact false. For instance, minimization does not induce an equivalence relation. We give an exact algorithm for the cover filter minimization problem. Unlike prior work (based on graph coloring) we consider a type of clique-cover problem, involving a new conditional constraint, from which we can find more general relations. In addition to solving the more general problem, the algorithm also corrects flaws present in all prior filter reduction methods. In employing SAT, the algorithm provides a promising basis for future practical development.