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 规则将对象载入寄存器并标记回溯点，使结构终止性同时将每次执行限制为对象数的多项式。
正文 · AI 翻译
摘要：对规划进行启发式搜索可能存储指数级数量的状态，即使其启发式几乎完美。我们改为学习搜索控制，每个领域一份规范，写成一种索引式策略：一种广义策略，带有保存对象的寄存器和对其规则进行排序的模式。我们添加 choose 规则，它将一个对象加载到寄存器中并标记一个回溯点，在该点一个候选就足够；其他每条规则必须对其所有结果都有效，且无需搜索。我们的主要结果是，结构终止性——它排除了无限执行——也将每次执行限制在对象数量的多项式范围内。于是，一种深度优先过程可在多项式空间内找到规划，无论状态空间多大，且无需已访问状态列表。代价是时间，仅在选择深度上呈指数级，即一次执行中真实选择的次数。因此，这种策略可求解的任何类都属于 NP，且在常数选择深度下属于 P。我们使用语言模型在反例引导的循环中学习这些策略，该循环证明终止性、验证训练任务，并保持选择深度较小。借助学到的策略，该过程求解了 IPC 2023 Learning Track 和 Autoscale Agile 套件的 1,890 个测试任务中的 1,709 个，多于 LAMA、BFWS 和 Levitron，且其中大多数在一秒和 100 MiB 内完成。
| 主题： | 人工智能（cs.AI） |
| 引用为： | arXiv:2610.10954 [cs.AI] |
| （或 arXiv:2610.10954v1 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.10954 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Dominik Drexler [查看电子邮件]
[v1]
2026年10月7日星期三 22:14:01 UTC（157 KB）
来源：arXiv cs.AI · arxiv.org