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.
翻译：复杂的推理问题中，状态的计算成本有所不同，这个特性可以被利用。为此，我们提出了一种自适应子目标搜索（AdaSubS）的搜索方法，该方法自适应地调整规划视野。为此，AdaSubS 生成了不同距离的多样化子目标集合。采用验证机制快速过滤掉不可达的子目标，以便集中精力处理可行的进一步子目标。通过这种方式，AdaSubS 利用长子目标规划的效率和短子目标规划的精细控制，因此可以有效地应对复杂的规划问题。我们展示了 AdaSubS 在三个复杂的推理任务：Sokoban，魔方和不等式证明基准 INT 上明显优于分层规划算法。
相关内容
微信扫码咨询专知VIP会员