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

• URL: http://arxiv.org/abs/2106.04866v1
• Date: Wed, 9 Jun 2021 07:46:19 GMT
• Title: Planning for Novelty: Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning
• Authors: Nir Lipovetzky
• Abstract summary: 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.
• Score: 6.053629733936546
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Parallel Strategies for Best-First Generalized Planning [51.713634067802104]
  Generalized planning (GP) is a research area of AI that studies the automated synthesis of algorithmic-like solutions capable of solving multiple classical planning instances. One of the current advancements has been the introduction of Best-First Generalized Planning (BFGP), a GP algorithm based on a novel solution space that can be explored with search. This paper evaluates the application of parallel search techniques to BFGP, another critical component in closing the performance gap.
  arXiv  Detail & Related papers  (2024-07-31T09:50:22Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  Task planning for embodied AI has been one of the most challenging problems. We propose a task-agnostic method named 'planning as in-painting' The proposed framework achieves promising performances in various embodied AI tasks.
  arXiv  Detail & Related papers  (2023-12-02T10:07:17Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches. In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
  arXiv  Detail & Related papers  (2022-10-23T22:21:10Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Neural Motion Planning for Autonomous Parking [6.1805402105389895]
  This paper presents a hybrid motion planning strategy that combines a deep generative network with a conventional motion planning method. The proposed method effectively learns the representations of a given state, and shows improvement in terms of algorithm performance.
  arXiv  Detail & Related papers  (2021-11-12T14:29:38Z)
• Goal Agnostic Planning using Maximum Likelihood Paths in Hypergraph World Models [1.370633147306388]
  We present a hypergraph-based machine learning algorithm, a datastructure--driven maintenance method, and a planning algorithm based on a probabilistic application of Dijkstra's algorithm. We prove that the algorithm determines optimal solutions within the problem space, mathematically bound learning performance, and supply a mathematical model analyzing system state progression through time.
  arXiv  Detail & Related papers  (2021-10-18T16:22:33Z)
• A Unified View of Algorithms for Path Planning Using Probabilistic Inference on Factor Graphs [2.4874504720536317]
  This work looks at the specific recursions that arise from various cost functions that, although they may appear similar in scope, bear differences, at least when applied to typical path planning problems. We show how this unified approach, presented both in probability space and in log space, provides a very general framework that includes the Sum-product, the Max-product, Dynamic programming and mixed Reward/Entropy criteria-based algorithms.
  arXiv  Detail & Related papers  (2021-06-19T07:13:15Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• A Unifying Framework for Reinforcement Learning and Planning [2.564530030795554]
  This paper presents a unifying algorithmic framework for reinforcement learning and planning (FRAP) At the end of the paper, we compare a variety of well-known planning, model-free and model-based RL algorithms along these dimensions.
  arXiv  Detail & Related papers  (2020-06-26T14:30:41Z)
• Reinforcement Learning as Iterative and Amortised Inference [62.997667081978825]
  We use the control as inference framework to outline a novel classification scheme based on amortised and iterative inference. We show that taking this perspective allows us to identify parts of the algorithmic design space which have been relatively unexplored.
  arXiv  Detail & Related papers  (2020-06-13T16:10:03Z)
• Continuous Control for Searching and Planning with a Learned Model [5.196149362684628]
  Decision-making agents with planning capabilities have achieved huge success in the challenging domain like Chess, Shogi, and Go. Researchers proposed the MuZero algorithm that can learn the dynamical model through the interactions with the environment. We show the proposed algorithm outperforms the soft actor-critic (SAC) algorithm, a state-of-the-art model-free deep reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2020-06-12T19:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.