近似新奇搜索 (Approximate Novelty Search)

Width-based search algorithms seek plans by prioritizing states according to a suitably defined measure of novelty, that maps states into a set of novelty categories. Space and time complexity to evaluate state novelty is known to be exponential on the cardinality of the set. We present novel methods to obtain polynomial approximations of novelty and width-based search. First, we approximate novelty computation via random sampling and Bloom filters, reducing the runtime and memory footprint. Second, we approximate the best-first search using an adaptive policy that decides whether to forgo the expansion of nodes in the open list. These two techniques are integrated into existing width-based algorithms, resulting in new planners that perform significantly better than other state-of-the-art planners over benchmarks from the International Planning Competitions.

翻译：基于 Width 的搜索算法通过根据适当界定的新颖度量确定国家的优先次序来寻找计划,这些新颖度度将绘制成一套新颖的类别。用于评估国家新颖度的空间和时间复杂性在这套新颖度的基点上是指数化的。我们提出了获得新颖度和宽度搜索的多元近似新颖度的新颖方法。首先, 我们通过随机抽样和闪烁过滤器近似新颖计算, 减少运行时间和记忆足迹。其次, 我们使用适应性政策来比较最佳的首选搜索, 该政策决定是否放弃开放列表中节点的扩展。这两种技术被整合到现有的宽度算法中, 导致新的规划者比其他国际规划竞赛中最先进的规划者表现得要好得多。