Presentation of the subgoal search method for complex reasoning tasks

Speaker and affiliation: 
Tomasz Odrzygóźdź PhD (AWARElab, postdoc researcher at the University of Warsaw)
Tue, 2021-09-21 13:00 to 14:30

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. 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. The method achieves strong results including state-of-the-art on INT within a modest computational budget.