Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search (2022-06-01T00:00:00.000000Z)

TL;DR

Adaptive Subgoal Search (AdaSubS), a search method that adaptively adjusts the planning horizon, significantly surpasses hierarchical planning algorithms on three complex reasoning tasks: Sokoban, the Rubik's Cube and inequality proving benchmark INT.

Abstract

Complex reasoning problems contain states that vary in the computational cost required to determine a good action plan. Taking advantage of this property, we propose Adaptive Subgoal Search (AdaSubS), a search method that adaptively adjusts the planning horizon. To this end, AdaSubS generates diverse sets of subgoals at different distances. A verification mechanism is employed to filter out unreachable subgoals swiftly, allowing to focus on feasible further subgoals. In this way, AdaSubS benefits from the efficiency of planning with longer subgoals and the fine control with the shorter ones, and thus scales well to difficult planning problems. We show that AdaSubS significantly surpasses hierarchical planning algorithms on three complex reasoning tasks: Sokoban, the Rubik's Cube, and inequality proving benchmark INT.

Authors

Yuhuai Wu

7 papers

K. Czechowski

3 papers

Tomasz Odrzyg'o'zd'z

2 papers

TL;DR

Abstract

Authors

References57 items

Do As I Can, Not As I Say: Grounding Language in Robotic Affordances

MuZero with Self-competition for Rate Control in VP9 Video Compression

Training Verifiers to Solve Math Word Problems

Subgoal Search For Complex Reasoning Tasks

World Model as a Graph: Learning Latent Landmarks for Planning

Generative Language Modeling for Automated Theorem Proving

INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving

Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictors

What Matters In On-Policy Reinforcement Learning? A Large-Scale Empirical Study

Efficient Black-Box Planning Using Macro-Actions with Focused Effects

Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning

Hallucinative Topological Memory for Zero-Shot Visual Planning

Sub-Goal Trees - a Framework for Goal-Based Reinforcement Learning

Multilingual Denoising Pre-training for Neural Machine Translation

Mastering Atari, Go, chess and shogi by planning with a learned model

Dynamics Learning with Cascaded Variational Inference for Multi-Step Manipulation

Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning

Variational Temporal Abstraction

Uncertainty-sensitive Learning and Planning with Ensembles

Hierarchical Foresight: Self-Supervised Learning of Long-Horizon Tasks via Visual Subgoal Generation

Solving the Rubik’s cube with deep reinforcement learning and search

Keyframing the Future: Keyframe Discovery for Visual Prediction and Planning

An investigation of model-free planning

Learning over Subgoals for Efficient Navigation of Structured, Unknown Environments

Multi-task Deep Reinforcement Learning with PopArt

Time-Agnostic Prediction: Predicting Predictable Video Frames

Learning Plannable Representations with Causal InfoGAN

Semi-parametric Topological Memory for Navigation

Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm

Intention-Net: Integrating Planning and Deep Learning for Goal-Directed Autonomous Navigation

Hindsight Experience Replay

Attention is All you Need

Learning to reinforcement learn

RL$^2$: Fast Reinforcement Learning via Slow Reinforcement Learning

Width and Serialization of Classical Planning Problems

The first learning track of the international planning competition

The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks

Real-time adaptive A*

The Fast Downward Planning System

SOKOBAN and other motion planning problems

Finding Optimal Solutions to Rubik's Cube Using Pattern Databases

Introduction to algorithms

Heuristics : intelligent search strategies for computer problem solving

A Comparison of Abstraction Heuristics for Rubik’s Cube

Should I Run Offline Reinforcement Learning or Behavioral Cloning?

Adaptive search techniques in AI planning and heuristic search

Planning with goalconditioned policies

Artificial intelligence: A modern approach

Involvement of basal ganglia and orbitofrontal cortex in goal-directed behavior.

PDDL-the planning domain definition language

Rich Caruana

Learning to Achieve Goals

We present a comprehensive study of adaptive methods, showing that they outperform similar algorithms without adaptation

For 7% of boards, AdaSubS found the optimal solution

We propose Adaptive Subgoal Search (AdaSubS), a new algorithm that adjusts the planning horizon to take into account the varying complexity of the state space

Fast and Precise

used nodes equipped with a single Nvidia V100 32 GB card or Nvidia RTX 2080Ti 11 GB card. Each such node had 4 CPU cores and 168GB of RAM

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names