Bootstrap Learning of Heuristic Functions
Bootstrap Learning of Heuristic Functions
复制标题
启发式函数的引导学习
DOI：
10.1609/socs.v1i1.18159
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
R. Holte
中科院分区：
文献类型：
--
作者：
Shahab Jabbari Arfaee;Sandra Zilles;R. Holte
搜索算法，如IDA* 或搜索规划器。我们的方法旨在通过自举从给定的弱启发式h 0生成强启发式。可以使用h 0解决的“简单”问题实例为学习算法提供了训练示例，该学习算法产生的启发式h1预计比h 0更强。如果h 0太弱而不能解决任何给定的实例，我们使用随机游走技术来创建一系列连续的更困难的实例，从h 0可解决的实例开始。然后使用hi代替hi-1重复引导过程，直到产生足够强的启发式。我们测试我们的方法上的15和24滑动瓷砖拼图，17和24煎饼拼图，和15和20块的世界。在每一种情况下，我们的方法都会产生一个启发式算法，使IDA* 能够非常快速地解决随机生成的问题实例，并获得非常接近最优的解决方案。
search algorithms such as IDA* or heuristic-search planners. Our method aims to generate a strong heuristic from a given weak heuristic h0 through bootstrapping. The "easy" problem instances that can be solved using h0 provide training examples for a learning algorithm that produces a heuristic h1 that is expected to be stronger than h0. If h0 is too weak to solve any of the given instances we use a random walk technique to create a sequence of successively more difficult instances starting with ones that are solvable by h0. The bootstrap process is then repeated using hi in lieu of hi–1 until a sufficiently strong heuristic is produced. We test our method on the 15- and 24-sliding tile puzzles, the 17- and 24-pancake puzzles, and the 15- and 20-blocks world. In every case our method produces a heuristic that allows IDA* to solve randomly generated problem instances extremely quickly with solutions very close to optimal.