Hybrid Search for Efficient Planning with Completeness Guarantees

• URL: http://arxiv.org/abs/2310.12819v2
• Date: Tue, 28 Nov 2023 19:23:22 GMT
• Title: Hybrid Search for Efficient Planning with Completeness Guarantees
• Authors: Kalle Kujanp\"a\"a, Joni Pajarinen, Alexander Ilin
• Abstract summary: We propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces. This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search.
• Score: 63.02803974708516
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving complex planning problems has been a long-standing challenge in computer science. Learning-based subgoal search methods have shown promise in tackling these problems, but they often suffer from a lack of completeness guarantees, meaning that they may fail to find a solution even if one exists. In this paper, we propose an efficient approach to augment a subgoal search method to achieve completeness in discrete action spaces. Specifically, we augment the high-level search with low-level actions to execute a multi-level (hybrid) search, which we call complete subgoal search. This solution achieves the best of both worlds: the practical efficiency of high-level search and the completeness of low-level search. We apply the proposed search method to a recently proposed subgoal search algorithm and evaluate the algorithm trained on offline data on complex planning problems. We demonstrate that our complete subgoal search not only guarantees completeness but can even improve performance in terms of search expansions for instances that the high-level could solve without low-level augmentations. Our approach makes it possible to apply subgoal-level planning for systems where completeness is a critical requirement.

Related papers

• Planning In Natural Language Improves LLM Search For Code Generation [5.370466208990696]
  We propose PlanSearch, a novel search algorithm for solving problems in natural language. PlanSearch shows strong results across HumanEval+, MBPP+, and LiveCodeBench. We show that, across all models, search algorithms, and benchmarks analyzed, we can accurately predict performance gains due to search.
  arXiv  Detail & Related papers  (2024-09-05T17:44:49Z)
• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings. In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions. Second, a variant of beam search to find a solution is employed. This method utilizes a newly developed guiding function based on an expected distance score of partial solutions.
  arXiv  Detail & Related papers  (2024-07-17T21:26:27Z)
• What Matters in Hierarchical Search for Combinatorial Reasoning Problems? [0.0]
  Recent efforts have sought to enhance planning by incorporating hierarchical high-level search strategies, known as subgoal methods. While promising, their performance against traditional low-level planners is inconsistent, raising questions about their application contexts. We identify the attributes pivotal for leveraging the advantages of high-level search: hard-to-learn value functions, complex action spaces, presence of dead ends in the environment, or using data collected from diverse experts.
  arXiv  Detail & Related papers  (2024-06-05T15:14:58Z)
• Efficient Line Search Method Based on Regression and Uncertainty Quantification [7.724860428430271]
  Unconstrained optimization problems are typically solved using iterative methods to determine optimal step lengths. This paper introduces a novel line search approach using Bayesian optimization. It demonstrates superior performance compared to existing state-of-the-art methods, solving more problems to optimality with equivalent resource usage.
  arXiv  Detail & Related papers  (2024-05-17T16:35:20Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Fighting the curse of dimensionality: A machine learning approach to finding global optima [77.34726150561087]
  This paper shows how to find global optima in structural optimization problems. By exploiting certain cost functions we either obtain the global at best or obtain superior results at worst when compared to established optimization procedures.
  arXiv  Detail & Related papers  (2021-10-28T09:50:29Z)
• C-Planning: An Automatic Curriculum for Learning Goal-Reaching Tasks [133.40619754674066]
  Goal-conditioned reinforcement learning can solve tasks in a wide range of domains, including navigation and manipulation. We propose the distant goal-reaching task by using search at training time to automatically generate intermediate states. E-step corresponds to planning an optimal sequence of waypoints using graph search, while the M-step aims to learn a goal-conditioned policy to reach those waypoints.
  arXiv  Detail & Related papers  (2021-10-22T22:05:31Z)
• Subgoal Search For Complex Reasoning Tasks [15.152111664776259]
  kSubS is a learned subgoal generator that produces a diversity of subgoals that are both achievable and closer to the solution. We show that a simple approach of generating $k$-th step ahead subgoals is surprisingly efficient on three challenging domains.
  arXiv  Detail & Related papers  (2021-08-25T12:40:04Z)
• 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)
• ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding [86.40042104698792]
  We formulate neural architecture search as a sparse coding problem. In experiments, our two-stage method on CIFAR-10 requires only 0.05 GPU-day for search. Our one-stage method produces state-of-the-art performances on both CIFAR-10 and ImageNet at the cost of only evaluation time.
  arXiv  Detail & Related papers  (2020-10-13T04:34:24Z)

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.