Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Approximate Novelty Search
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 i…
Width-based Lookaheads with Learnt Base Policies and Heuristics Over the Atari-2600 Benchmark
We propose new width-based planning and learning algorithms inspired from a careful analysis of the design decisions made by previous width-based planners. The algorithms are applied over the Atari-2600 games and our bes…
Atari GamesConsolidating LAMA with Best-First Width Search
One key decision for heuristic search algorithms is how to balance exploration and exploitation. In classical planning, novelty search has come out as the most successful approach in this respect. The idea is to favor st…
Heuristic SearchNovelty and Lifted Helpful Actions in Generalized Planning
It has been shown recently that successful techniques in classical planning, such as goal-oriented heuristics and landmarks, can improve the ability to compute planning programs for generalized planning (GP) problems. In…
Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches: Extended Version
Width-based planning methods deal with conjunctive goals by decomposing problems into subproblems of low width. Algorithms like SIW thus fail when the goal is not easily serializable in this way or when some of the subpr…