Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning
This work addresses planning and reinforcement learning problems for researchers and practitioners, but it is incremental as it summarizes and surveys existing width-based methods rather than presenting new results.
The paper tackles the problem of efficient planning and control by introducing width-based algorithms that use state novelty to achieve state-of-the-art performance in classical planning, with theoretical guarantees on polynomial runtime and memory consumption.
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.