Approximate Novelty Search
This work addresses efficiency bottlenecks in planning algorithms for AI researchers and practitioners, though it is incremental as it builds on existing width-based methods.
The paper tackled the exponential space and time complexity of evaluating state novelty in width-based search algorithms by introducing polynomial approximations using random sampling, Bloom filters, and an adaptive policy for node expansion. The result was new planners that performed significantly better than other state-of-the-art planners on International Planning Competition benchmarks.
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.