Approximate Novelty Search


  • Anubhav Singh The University of Melbourne
  • Nir Lipovetzky The University of Melbourne
  • Miquel Ramirez The University of Melbourne
  • Javier Segovia-Aguas Universitat Pompeu Fabra


Classical Planning Techniques And Analysis


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.




How to Cite

Singh, A., Lipovetzky, N., Ramirez, M., & Segovia-Aguas, J. (2021). Approximate Novelty Search. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 349-357. Retrieved from