Timezone: »

 
Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Michał Zawalski · Michał Tyrolski · Konrad Czechowski · Damian Stachura · Piotr Piękos · Tomasz Odrzygóźdź · Yuhuai Wu · Łukasz Kuciński · Piotr Miłoś

@
in Deep Reinforcement Learning Workshop »
Event URL: https://openreview.net/forum?id=EBs8S_7MJn »

Complex reasoning problems contain states that vary in the computational cost required to determine a good action plan. Taking advantage of this property, we propose Adaptive Subgoal Search (AdaSubS), a search method that adaptively adjusts the planning horizon. To this end, AdaSubS generates diverse sets of subgoals at different distances. A verification mechanism is employed to filter out unreachable subgoals swiftly, allowing to focus on feasible further subgoals. In this way, AdaSubS benefits from the efficiency of planning with longer subgoals and the fine control with the shorter ones, and thus scales well to difficult planning problems. We show that AdaSubS significantly surpasses hierarchical planning algorithms on three complex reasoning tasks: Sokoban, the Rubik's Cube, and inequality proving benchmark INT.

[ Poster]  [ OpenReview]  [ Topia] 

Author Information

Michał Zawalski (University of Warsaw)
Michał Tyrolski (University of Warsaw)
Konrad Czechowski (Uniwersytet Warszawski, ul. Krakowskie Przedmieście 26/28, 00-927 Warszawa, NIP 525-001-12-66)
Damian Stachura (Jagiellonian University)
Piotr Piękos (King Abdullah University of Science and Technology)
Tomasz Odrzygóźdź (IDEAS NCBR Sp. z o.o. ul. Nowogrodzka 47A 00-695 Warszawa VAT Number: PL 7011017605)
Yuhuai Wu (Google)
Łukasz Kuciński (Polish Academy of Sciences)
Piotr Miłoś (Ideas NCBR, Polish Academy of Sciences)

More from the Same Authors