Subgoal Search For Complex Reasoning Tasks

• URL: http://arxiv.org/abs/2108.11204v3
• Date: Wed, 3 Apr 2024 15:35:04 GMT
• Title: Subgoal Search For Complex Reasoning Tasks
• Authors: Konrad Czechowski, Tomasz Odrzygóźdź, Marek Zbysiński, Michał Zawalski, Krzysztof Olejnik, Yuhuai Wu, Łukasz Kuciński, Piotr Miłoś,
• Abstract summary: 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.
• Score: 15.152111664776259
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Humans excel in solving complex reasoning tasks through a mental process of moving from one idea to a related one. Inspired by this, we propose Subgoal Search (kSubS) method. Its key component is a learned subgoal generator that produces a diversity of subgoals that are both achievable and closer to the solution. Using subgoals reduces the search space and induces a high-level search graph suitable for efficient planning. In this paper, we implement kSubS using a transformer-based subgoal module coupled with the classical best-first search framework. We show that a simple approach of generating $k$-th step ahead subgoals is surprisingly efficient on three challenging domains: two popular puzzle games, Sokoban and the Rubik's Cube, and an inequality proving benchmark INT. kSubS achieves strong results including state-of-the-art on INT within a modest computational budget.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solving [64.38649623473626]
  Large Language Models (LLMs) have driven substantial progress in artificial intelligence. We propose a novel framework called textbfSEquential subtextbfGoal textbfOptimization (SEGO) to enhance LLMs' ability to solve mathematical problems.
  arXiv  Detail & Related papers  (2023-10-19T17:56:40Z)
• Hybrid Search for Efficient Planning with Completeness Guarantees [63.02803974708516]
  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.
  arXiv  Detail & Related papers  (2023-10-19T15:16:43Z)
• Take a Break in the Middle: Investigating Subgoals towards Hierarchical Script Generation [41.79944184861954]
  Goal-oriented Script Generation is a new task of generating a list of steps that can fulfill the given goal. In this paper, we propose to extend the task from the perspective of cognitive theory.
  arXiv  Detail & Related papers  (2023-05-18T12:10:06Z)
• Learning Rational Subgoals from Demonstrations and Instructions [71.86713748450363]
  We present a framework for learning useful subgoals that support efficient long-term planning to achieve novel goals. At the core of our framework is a collection of rational subgoals (RSGs), which are essentially binary classifiers over the environmental states. Given a goal description, the learned subgoals and the derived dependencies facilitate off-the-shelf planning algorithms, such as A* and RRT.
  arXiv  Detail & Related papers  (2023-03-09T18:39:22Z)
• Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search [15.157605648149685]
  We propose Adaptive Subgoal Search (AdaSubS), a search method that adaptively adjusts the planning horizon. A verification mechanism is employed to filter out unreachable subgoals swiftly. We show that AdaSubS significantly surpasses hierarchical planning algorithms on three complex reasoning tasks.
  arXiv  Detail & Related papers  (2022-06-01T18:28:23Z)
• Adaptive Multi-Goal Exploration [118.40427257364729]
  We show how AdaGoal can be used to tackle the objective of learning an $epsilon$-optimal goal-conditioned policy. AdaGoal is anchored in the high-level algorithmic structure of existing methods for goal-conditioned deep reinforcement learning.
  arXiv  Detail & Related papers  (2021-11-23T17:59:50Z)
• Visual scoping operations for physical assembly [0.0]
  We propose visual scoping, a strategy that interleaves planning and acting by alternately defining a spatial region as the next subgoal. We find that visual scoping achieves comparable task performance to the subgoal planner while requiring only a fraction of the total computational cost.
  arXiv  Detail & Related papers  (2021-06-10T10:50:35Z)
• GOLD-NAS: Gradual, One-Level, Differentiable [100.12492801459105]
  We propose a novel algorithm named Gradual One-Level Differentiable Neural Architecture Search (GOLD-NAS) It introduces a variable resource constraint to one-level optimization so that the weak operators are gradually pruned out from the super-network.
  arXiv  Detail & Related papers  (2020-07-07T10:37:49Z)

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.