Subgoal Search For Complex Reasoning Tasks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911824721477632 |
|---|---|
| author | Czechowski, Konrad Odrzygóźdź, Tomasz Zbysiński, Marek Zawalski, Michał Olejnik, Krzysztof Wu, Yuhuai Kuciński, Łukasz Miłoś, Piotr |
| author_facet | Czechowski, Konrad Odrzygóźdź, Tomasz Zbysiński, Marek Zawalski, Michał Olejnik, Krzysztof Wu, Yuhuai Kuciński, Łukasz Miłoś, Piotr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_11204 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Subgoal Search For Complex Reasoning Tasks Czechowski, Konrad Odrzygóźdź, Tomasz Zbysiński, Marek Zawalski, Michał Olejnik, Krzysztof Wu, Yuhuai Kuciński, Łukasz Miłoś, Piotr Artificial Intelligence Machine Learning 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. |
| title | Subgoal Search For Complex Reasoning Tasks |
| topic | Artificial Intelligence Machine Learning |
| url | https://arxiv.org/abs/2108.11204 |