Bibliographic Details
| Title: |
Subgoal Search For Complex Reasoning Tasks |
| Authors: |
Czechowski, Konrad, Odrzygóźdź, Tomasz, Zbysiński, Marek, Zawalski, Michał, Olejnik, Krzysztof, Wu, Yuhuai, Kuciński, Łukasz, Miłoś, Piotr |
| Publication Year: |
2021 |
| Collection: |
Computer Science |
| Subject Terms: |
Computer Science - Artificial Intelligence, Computer Science - Machine Learning |
| More Details: |
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.
Comment: NeurIPS 2021 |
| Document Type: |
Working Paper |
| Access URL: |
http://arxiv.org/abs/2108.11204 |
| Accession Number: |
edsarx.2108.11204 |
| Database: |
arXiv |
