前向规划启发式算法 - hmax、hadd、hff

Question

前向规划启发式算法 - hmax、hadd、hff

8

我正在学习前向规划启发式算法hmax、hadd和hff，并在网上找到了一些资源，但我真的无法理解它们的实际工作原理。

以下是我目前找到的资源: http://icaps09.uom.gr/tutorials/tut1.pdf （由Emil Keyder和Blai Bonet于2009年举办的ICAPS（国际计划与调度会议）教程，“用于规划的启发式算法”，其中解释了hmax、hadd、hff和h+。） http://gki.informatik.uni-freiburg.de/papers/betz-helmert-icaps2009ws.pdf （Betz和Helmert的科学论文，发表在2009年德国人工智能会议上，题为“理论与实践中的h+规划”，与其他三篇文章密切相关。）

https://cw.felk.cvut.cz/wiki/_media/courses/a4m36pah/07_relaxation.pdf
（另一个来源不明的教程，也是关于启发式算法hmax、hadd、hff的）

你能简单地解释一下它们是如何工作的吗？谢谢

- The Condor

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Ormesher · Accepted Answer

我假设您已经了解规划的基本概念。 hMax、hAdd和hFF算法用于计算规划图上给定状态相对于当前占据状态的启发式值。

这三种算法都是通过考虑问题的松弛版本来工作；具体来说，通过删除每个适用动作的删除列表而放宽了问题的版本。这样做的效果可以概括为一旦实现（变为真），就会保持实现。

hMax和hAdd的工作方式非常相似。两种算法都是通过考虑计划图中的一个状态，并使用所有适用的动作使该状态中的每个原子都成为真。需要实现所有原子的动作的成本是它们产生的启发式值的基础。

对于hAdd，给定状态的启发式值是实现该状态中的每个原子的组合成本。

对于hMax，给定状态的启发式值是该状态中最昂贵的原子的成本。

请注意，两种算法都没有实际解决放宽后的问题，它们只是计算相对于当前状态要实现给定状态的困难程度的估计。

hMax是可接受的，而hAdd不是可接受的。

hFF与众不同，因为它实际上解决了放松后的问题。它不试图找到最佳解（见†），而是找到一个合理的解。

为了确定给定状态（我们称其为s）的启发式值，hFF在放松计划中从当前状态到给定状态找到一个解，通常称为π(s)。一旦找到该解，赋予状态s的启发式值为放松解中的操作数。这可以写成：

h(s) = |π(s)|

hFF有时被称为松弛规划h。它不是可接受的，但它是信息量大的。

用于在松弛计划中找到解决方案的方法因hFF算法的实现而异。

† hFF并没有尝试寻找最优解，因为虽然比原问题的规划容易，但计算出一个最优解仍然过于困难，因为它必须针对每个状态进行计算。相反，它试图找到一个合理的计划，这样计算成本就小得多。

我真的希望这能帮到你，也希望我没有让你更加困惑。

~~我也真心希望我是对的-我相当自信，但我完全可以接受纠正。~~ 经过AI讲师的检查，我现在很有信心这是正确的。