Learning Heuristic Selection with Dynamic Algorithm Configuration

• URL: http://arxiv.org/abs/2006.08246v3
• Date: Mon, 12 Apr 2021 14:32:32 GMT
• Title: Learning Heuristic Selection with Dynamic Algorithm Configuration
• Authors: David Speck, Andr\'e Biedenkapp, Frank Hutter, Robert Mattm\"uller, Marius Lindauer
• Abstract summary: We show that dynamic algorithm configuration can be used for dynamic selection dynamics of a planning system. We show that this approach generalizes over existing approaches and that it can exponentially improve performance of the domain search.
• Score: 44.91083687014879
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A key challenge in satisficing planning is to use multiple heuristics within one heuristic search. An aggregation of multiple heuristic estimates, for example by taking the maximum, has the disadvantage that bad estimates of a single heuristic can negatively affect the whole search. Since the performance of a heuristic varies from instance to instance, approaches such as algorithm selection can be successfully applied. In addition, alternating between multiple heuristics during the search makes it possible to use all heuristics equally and improve performance. However, all these approaches ignore the internal search dynamics of a planning system, which can help to select the most useful heuristics for the current expansion step. We show that dynamic algorithm configuration can be used for dynamic heuristic selection which takes into account the internal search dynamics of a planning system. Furthermore, we prove that this approach generalizes over existing approaches and that it can exponentially improve the performance of the heuristic search. To learn dynamic heuristic selection, we propose an approach based on reinforcement learning and show empirically that domain-wise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches.

Related papers

• Deep Memory Search: A Metaheuristic Approach for Optimizing Heuristic Search [0.0]
  We introduce a novel approach called Deep Heuristic Search (DHS), which models metaheuristic search as a memory-driven process. DHS employs multiple search layers and memory-based exploration-exploitation mechanisms to navigate large, dynamic search spaces.
  arXiv  Detail & Related papers  (2024-10-22T14:16:49Z)
• Dynamic operator management in meta-heuristics using reinforcement learning: an application to permutation flowshop scheduling problems [0.3495246564946556]
  This study develops a framework based on reinforcement learning to dynamically manage a large portfolio of search operators within meta-heuristics. A Q-learning-based adaptive operator selection mechanism is used to select the most suitable operator from the dynamically updated portfolio. The performance of the proposed framework is analyzed through an application to the permutation flowshop scheduling problem.
  arXiv  Detail & Related papers  (2024-08-27T08:38:17Z)
• 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)
• Optimistic Active Exploration of Dynamical Systems [52.91573056896633]
  We develop an algorithm for active exploration called OPAX. We show how OPAX can be reduced to an optimal control problem that can be solved at each episode. Our experiments show that OPAX is not only theoretically sound but also performs well for zero-shot planning on novel downstream tasks.
  arXiv  Detail & Related papers  (2023-06-21T16:26:59Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Heuristic Search for Multi-Objective Probabilistic Planning [0.0]
  Heuristic search is a powerful approach that has successfully been applied to a broad class of planning problems. Here, we extend the reach of search to a more class of problems, namely multi-objective shortest paths (MOSSPs) We design new search algorithms MOLAO* and MOLRTDP, which extend well-known SSP algorithms to the multi-objective problem.
  arXiv  Detail & Related papers  (2023-03-25T05:18:22Z)
• Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient [65.08966446962845]
  offline reinforcement learning, which aims at optimizing decision-making strategies with historical data, has been extensively applied in real-life applications. We take a step by considering offline reinforcement learning with differentiable function class approximation (DFA) Most importantly, we show offline differentiable function approximation is provably efficient by analyzing the pessimistic fitted Q-learning algorithm.
  arXiv  Detail & Related papers  (2022-10-03T07:59:42Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles [0.0]
  We study the online optimization of mixable loss functions in a dynamic environment. Our results are guaranteed to hold in a strong deterministic sense in an individual sequence manner.
  arXiv  Detail & Related papers  (2021-08-13T21:48:55Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)

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.