学习计划搜索控制：以多项式空间完成大状态空间规划

对计划的启发式搜索可以存储指数级的多个状态，即使其启发式几乎是完美的。相反，我们学习搜索控制，每个域一个规范，编写为索引策略：一种通用策略，其寄存器保存对象和对其规则进行排序的模式。我们添加了选择规则，该规则将一个对象加载到寄存器中并标记一个回溯点，其中一个候选就足够了；其他所有规则都必须适用于其所有结果，并且无需搜索。我们的主要结果是结构终止，它排除了无限执行，也通过对象数量的多项式来限制每次执行。然后，深度优先过程在多项式空间中找到一个计划，无论状态空间有多大，并且没有访问过的状态列表。成本是时间，仅在选择深度（执行过程中实际选择的数量）上呈指数级增长。因此，这种策略解决的任何类别都位于 NP 中，并且位于恒定选择深度的 P 中。我们在反例引导的循环中使用语言模型来学习这些策略，该循环证明终止，验证训练任务， 并保持选择深度较小。通过学习的策略，该过程解决了 IPC 2023 Learning Track 和 Autoscale Agile 套件的 1,890 个测试任务中的 1,709 个，超过了 LAMA、BFWS 和 Levitron，并且大多数任务在一秒和 100 MiB 内完成。