Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms

• URL: http://arxiv.org/abs/2104.04768v1
• Date: Sat, 10 Apr 2021 13:52:27 GMT
• Title: Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms
• Authors: Alexandre Chenu, Nicolas Perrin-Gilbert, St\'ephane Doncieux, Olivier Sigaud
• Abstract summary: We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
• Score: 69.87173070473717
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reinforcement learning agents need a reward signal to learn successful policies. When this signal is sparse or the corresponding gradient is deceptive, such agents need a dedicated mechanism to efficiently explore their search space without relying on the reward. Looking for a large diversity of behaviors or using Motion Planning (MP) algorithms are two options in this context. In this paper, we build on the common roots between these two options to investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. These algorithms look for diversity in an outcome space or behavioral space which is generally hand-designed to represent what matters for a given task. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency. In particular, we show empirically that, if the mapping is smooth enough, i.e. if two close policies in the parameter space lead to similar outcomes, then diversity algorithms tend to inherit exploration properties of MP algorithms. By contrast, if it is not, diversity algorithms lose these properties and their performance strongly depends on specific heuristics, notably filtering mechanisms that discard some of the explored policies.

Related papers

• A Multi-Heuristic Search-based Motion Planning for Automated Parking [0.0]
  In unstructured environments like parking lots or construction sites, it is challenging to achieve real-time planning. We are adopting a Multi-Heuristic Search approach, that enables the use of multiple functions and their individual advantages. The Multi-Heuristic A* algorithm is benchmarked against a very popular search-based algorithm, Hybrid A*.
  arXiv  Detail & Related papers  (2023-07-15T17:33:06Z)
• A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Process [53.86223883060367]
  We show that diversity and coverage in unsupervised option discovery can indeed be unified under the same mathematical framework. Our proposed algorithm, ODPP, has undergone extensive evaluation on challenging tasks created with Mujoco and Atari.
  arXiv  Detail & Related papers  (2022-12-01T01:40:03Z)
• Relevance-guided Unsupervised Discovery of Abilities with Quality-Diversity Algorithms [1.827510863075184]
  We introduce Relevance-guided Unsupervised Discovery of Abilities; a Quality-Diversity algorithm that autonomously finds a behavioural characterisation tailored to the task at hand. We evaluate our approach on a simulated robotic environment, where the robot has to autonomously discover its abilities based on its full sensory data.
  arXiv  Detail & Related papers  (2022-04-21T00:29:38Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem. We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
  arXiv  Detail & Related papers  (2021-12-06T20:34:55Z)
• Discovering and Exploiting Sparse Rewards in a Learned Behavior Space [0.46736439782713946]
  Learning optimal policies in sparse rewards settings is difficult as the learning agent has little to no feedback on the quality of its actions. We introduce STAX, an algorithm designed to learn a behavior space on-the-fly and to explore it while efficiently optimizing any reward discovered.
  arXiv  Detail & Related papers  (2021-11-02T22:21:11Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
  arXiv  Detail & Related papers  (2021-10-18T14:00:22Z)
• A binary variant of gravitational search algorithm and its application to windfarm layout optimization problem [0.7734726150561088]
  A novel binary variant of GSA called A novel neighbourhood archives embedded gravitational constant in GSA for binary search space (BNAGGSA)' is proposed in this paper. The proposed algorithm produces a self-adaptive step size mechanism through which the agent moves towards the optimal direction with the optimal step size. To check the applicability of the proposed algorithm in solving real-world applications, a windfarm layout optimization problem is considered.
  arXiv  Detail & Related papers  (2021-07-25T16:56:19Z)
• Expressivity of Parameterized and Data-driven Representations in Quality Diversity Search [111.06379262544911]
  We compare the output diversity of a quality diversity evolutionary search performed in two different search spaces. A learned model is better at interpolating between known data points than at extrapolating or expanding towards unseen examples.
  arXiv  Detail & Related papers  (2021-05-10T10:27:43Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)
• Multi-Resolution A* [19.562565022582785]
  Heuristic search-based planning techniques are commonly used for motion planning on discretized spaces. We propose Multi-Resolution A* algorithm, that runs multiple weighted-A*(WA*) searches having different resolution levels simultaneously. We show that MRA* is bounded suboptimal with respect to the anchor resolution search space and resolution complete.
  arXiv  Detail & Related papers  (2020-04-14T17:38:11Z)

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.