Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Abstract
Complex reasoning problems contain states that vary in the computational cost required to determine the right action plan. To take 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, making it possible to focus on feasible further subgoals. In this way, AdaSubS benefits from the efficiency of planning with longer-term subgoals and the fine control with shorter-term 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 the inequality-proving benchmark INT.
Cite
Text
Zawalski et al. "Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search." International Conference on Learning Representations, 2023.Markdown
[Zawalski et al. "Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search." International Conference on Learning Representations, 2023.](https://mlanthology.org/iclr/2023/zawalski2023iclr-fast/)BibTeX
@inproceedings{zawalski2023iclr-fast,
title = {{Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search}},
author = {Zawalski, Michał and Tyrolski, Michał and Czechowski, Konrad and Odrzygóźdź, Tomasz and Stachura, Damian and Piękos, Piotr and Wu, Yuhuai and Kuciński, Łukasz and Miłoś, Piotr},
booktitle = {International Conference on Learning Representations},
year = {2023},
url = {https://mlanthology.org/iclr/2023/zawalski2023iclr-fast/}
}