学习搜索策略仅需多项式空间，1秒解1709个规划任务，超越LAMA和Levitron！
Learning How to Search for Plans with Exponentially Less Space
📖 AI 总结
本文提出一种新的规划搜索方法，通过学习“索引式策略”来控制搜索过程，从而大幅降低空间开销。传统启发式搜索即使启发函数近乎完美，仍可能存储指数级状态；而该策略为每个领域学习一份通用规范，借助寄存器保存对象、模式排列规则，并引入choose规则标记回溯点，使每次只需考虑一个候选。作者证明，结构终止性不仅能排除无限执行，还能将每次执行限制在对象数的多项式范围内，因此深度优先过程可在多项式空间内找到规划，无需访问状态列表，代价仅是时间在“选择深度”上呈指数增长。由此，该方法所求解的问题类属于NP，在常数选择深度下属于P。研究团队用语言模型在反例引导循环中学习此类策略，并验证终止性与训练任务。在IPC 2023学习赛道和Autoscale Agile套件的1890个测试任务中，该方法成功求解1709个，超过LAMA、BFWS和Levitron，且多数任务在一秒和100 MiB内存内完成。
🔑 关键词速览
| 索引式策略 | 一种带有寄存器和模式的广义策略，用于指导搜索过程。 |
| 选择规则 | 一种规则，将对象加载到寄存器并标记回溯点，其中一个候选就足够。 |
| 结构终止性 | 排除无限执行的性质，确保每次执行在多项式时间内终止。 |
| 选择深度 | 执行过程中真实选择的次数，影响算法的时间复杂度。 |
| 反例引导循环 | 一种学习循环，使用反例来指导策略学习，并验证终止性和任务。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅