arXiv：cs.AI· Dominik Drexler, Simon St{\aa}hlberg, Markus Fritzsche, Blai Bonet·· 3 小时前
用语言模型学习搜索控制策略，以多项式空间求解规划任务
Learning How to Search for Plans with Exponentially Less Space
AI 导读
研究者提出一种按域编写的索引式策略来学习搜索控制，新增 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