Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914810524860416 |
|---|---|
| author | Zawalski, Michał Tyrolski, Michał Czechowski, Konrad Odrzygóźdź, Tomasz Stachura, Damian Piękos, Piotr Wu, Yuhuai Kuciński, Łukasz Miłoś, Piotr |
| author_facet | Zawalski, Michał Tyrolski, Michał Czechowski, Konrad Odrzygóźdź, Tomasz Stachura, Damian Piękos, Piotr Wu, Yuhuai Kuciński, Łukasz Miłoś, Piotr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_00702 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search Zawalski, Michał Tyrolski, Michał Czechowski, Konrad Odrzygóźdź, Tomasz Stachura, Damian Piękos, Piotr Wu, Yuhuai Kuciński, Łukasz Miłoś, Piotr Artificial Intelligence Machine Learning I.2.8; I.2.6 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. |
| title | Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search |
| topic | Artificial Intelligence Machine Learning I.2.8; I.2.6 |
| url | https://arxiv.org/abs/2206.00702 |