Subgoal Search For Complex Reasoning Tasks

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, an analog of human intuition, 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-the 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.

Publication
NeurIPS 2021
Konrad Czechowski
Konrad Czechowski
Ph.D. Student
Tomasz Odrzygóźdź
Tomasz Odrzygóźdź
Postdoctoral researcher

My research interests include distributed robotics, mobile computing and programmable matter.

Michał Zawalski
Michał Zawalski
Ph.D. Student

My research interests include TODO

Łukasz Kuciński
Łukasz Kuciński
Principal Investigator

My research interests include reinforcement learning, decision-making under uncertainty and optimization.

Piotr Miłoś
Piotr Miłoś
Principal Investigator

My research interests include distributed robotics, mobile computing and programmable matter.

Related