Timezone: »

 
Poster
Subgoal Search For Complex Reasoning Tasks
Konrad Czechowski · Tomasz Odrzygóźdź · Marek Zbysiński · Michał Zawalski · Krzysztof Olejnik · Yuhuai Wu · Łukasz Kuciński · Piotr Miłoś

Thu Dec 09 12:30 AM -- 02:00 AM (PST) @
in Poster Session 5 »
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.
Keywords: Deep Learning · Transformers · Graph Learning

Author Information

Konrad Czechowski (Uniwersytet Warszawski, ul. Krakowskie Przedmieście 26/28, 00-927 Warszawa, NIP 525-001-12-66)
Tomasz Odrzygóźdź (Uniwersytet Warszawski, ul. Krakowskie Przedmieście 26/28, 00-927 Warszawa, NIP 525-001-12-66)
Marek Zbysiński (University of Warsaw)
Michał Zawalski (University of Warsaw)
Krzysztof Olejnik (University of Warsaw)
Yuhuai Wu (Stanford University / Google)
Łukasz Kuciński (Polish Academy of Sciences)
Piotr Miłoś (Polish Academy of Sciences, University of Oxford)

More from the Same Authors