# Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 9 Jun 2021.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches: Extended Version](https://mlsanity.com/paper/2105.04250/) (2021)
- [Deep Policies for Width-Based Planning in Pixel Domains](https://mlsanity.com/paper/1904.07091/) (2019)
- [Hierarchical Width-Based Planning and Learning](https://mlsanity.com/paper/2101.06177/) (2021)
- [Planning with Pixels in (Almost) Real Time](https://mlsanity.com/paper/1801.03354/) (2018)
- [Combined Task and Motion Planning as Classical AI Planning](https://mlsanity.com/paper/1706.06927/) (2017)
- [Approximate Novelty Search](https://mlsanity.com/paper/2105.07691/) (2021)
- [General Policies, Serializations, and Planning Width](https://mlsanity.com/paper/2012.08033/) (2020)
- [What you get is what you see: Decomposing Epistemic Planning using Functional STRIPS](https://mlsanity.com/paper/1903.11777/) (2019)
- [Best-First Width Search for Multi Agent Privacy-preserving Planning](https://mlsanity.com/paper/1906.03955/) (2019)

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

- [General Policies, Subgoal Structure, and Planning Width](https://mlsanity.com/paper/2311.05490/) (2023)
- [Count-based Novelty Exploration in Classical Planning](https://mlsanity.com/paper/2408.13719/) (2024)

## Abstract (arXiv)

Width-based algorithms search for solutions through a general definition of state novelty. These algorithms have been shown to result in state-of-the-art performance in classical planning, and have been successfully applied to model-based and model-free settings where the dynamics of the problem are given through simulation engines. Width-based algorithms performance is understood theoretically through the notion of planning width, providing polynomial guarantees on their runtime and memory consumption. To facilitate synergies across research communities, this paper summarizes the area of width-based planning, and surveys current and future research directions.