Search and Learn: On Dead-End Detectors, the Traps they Set, and Trap Learning
Search and Learn: On Dead-End Detectors, the Traps they Set, and Trap Learning
复制标题
搜索和学习：关于死胡同探测器、它们设置的陷阱以及陷阱学习
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
J. Hoffmann
中科院分区：
文献类型：
--
作者：
Marcel Steinmetz;J. Hoffmann
在经典规划中证明不可解性的一个关键技术是死角检测器（∆：对不可解性足够有效的可测试准则，在搜索过程中修剪（一些）不可解状态）。与此相关，最近的一个建议是在搜索之前识别陷阱，非目标状态集T的紧凑表示，不能逃脱。在这里，我们在这些想法之间创造新的协同作用。我们定义了一个广义的陷阱概念，相对于给定的死角检测器∆，其中T可以逃脱，但只能进入∆检测到的死角状态。我们展示了如何在搜索过程中学习这种T的紧凑表示，从而扩展了∆的范围。我们的实验表明，这是非常有益的。它提高了许多无法解决的基准规划领域和死角检测器（∆）的覆盖率，特别是在资源受限的领域，它优于目前的技术水平。
A key technique for proving unsolvability in classical planning are dead-end detectors ∆: effectively testable criteria sufficient for unsolvability, pruning (some) unsolvable states during search. Related to this, a recent proposal is the identification of traps prior to search, compact representations of non-goal state sets T that cannot be escaped. Here, we create new synergy across these ideas. We define a generalized concept of traps, relative to a given dead-end detector ∆, where T can be escaped, but only into dead-end states detected by ∆. We show how to learn compact representations of such T during search, extending the reach of ∆. Our experiments show that this can be quite beneficial. It improves coverage for many unsolvable benchmark planning domains and dead-end detectors ∆, in particular on resource-constrained domains where it outperforms the state of the art.