arXiv cs.AI· Dominik Drexler, Simon St{\aa}hlberg, Markus Fritzsche, Blai Bonet·· 9 天前AI 评分24
用指数级更少空间学习如何搜索规划：基于索引式策略的搜索控制学习
Learning How to Search for Plans with Exponentially Less Space
AI 导读
研究者提出一种索引式策略（indexical policy）来学习搜索控制，每个领域一份规范，新增 choose 规则将对象载入寄存器并标记回溯点，使结构终止性同时将每次执行限制为对象数的多项式。
正文 · 原文
Abstract:Heuristic search for a plan can store exponentially many states, even when its heuristic is almost perfect. We instead learn search control, one specification per domain, written as an indexical policy: a generalized policy with registers that hold objects and modes that sequence its rules. We add the choose rule, which loads an object into a register and marks a backtracking point, where one candidate suffices; every other rule must work for all of its outcomes and needs no search. Our main result is that structural termination, which rules out infinite executions, also bounds every execution by a polynomial in the number of objects. A depth-first procedure then finds a plan in polynomial space, however large the state space, with no list of visited states. The cost is time, exponential only in the choice depth, the number of real choices along an execution. Any class that such a policy solves therefore lies in NP, and in P at constant choice depth. We learn these policies with a language model in a counterexample-guided loop that certifies termination, verifies the training tasks, and keeps the choice depth small. With the learned policies, the procedure solves 1,709 of 1,890 test tasks of the IPC 2023 Learning Track and the Autoscale Agile suite, more than LAMA, BFWS, and Levitron, and most of them within one second and 100 MiB.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.10954 [cs.AI] |
| (or arXiv:2610.10954v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2610.10954 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Dominik Drexler [view email]
[v1]
Wed, 7 Oct 2026 22:14:01 UTC (157 KB)
来源：arXiv cs.AI · arxiv.org