  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.
