# Approximate Novelty Search

arXiv: https://arxiv.org/abs/2105.07691 · HTML: https://mlsanity.com/paper/2105.07691/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 26 references that are in the map.
- First posted on arXiv 17 May 2021.

## Builds on (most cited first, 1 of 1)

- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)

## Built on by (most cited first, 4 of 4)

- [Novelty and Lifted Helpful Actions in Generalized Planning](https://mlsanity.com/paper/2307.00735/) (2023)
- [Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning](https://mlsanity.com/paper/2106.04866/) (2021)
- [Count-based Novelty Exploration in Classical Planning](https://mlsanity.com/paper/2408.13719/) (2024)
- [Bilevel MCTS for Amortized O(1) Node Selection in Classical Planning](https://mlsanity.com/paper/2508.08385/) (2025)

## Abstract (arXiv)

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.