heuristics - 前瞻性规划启发式 - hmax、hadd、hff

Question

我正在研究前瞻性规划启发式 hmax、hadd 和 hff，我在网上找到了一些资源，但我真的不明白它们是如何工作的。

到目前为止，我找到的资源如下:

http://icaps09.uom.gr/tutorials/tut1.pdf
(Emil Keyder 和 Blai Bonet 于 2009 年撰写的关于“规划启发式”的 ICAPS(国际规划与调度 session )教程，其中解释了 hmax、hadd、hff 和 h+。)

http://gki.informatik.uni-freiburg.de/papers/betz-helmert-icaps2009ws.pdf
(Betz 和 Helmert 的一篇科学论文，发表在 German Converence on AI 2009 上，标题为“在理论和实践中使用 h+ 进行规划”，与其他三篇密切相关。)

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

你能用更简单的方式解释它们是如何工作的吗？
谢谢

Answer 1

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

所有三种算法都通过考虑 起作用轻松 问题的版本；具体而言，通过删除每个适用操作的删除列表而放宽的版本。这样的效果可以总结为一旦实现了一个原子(使之成为真)，它就会保持实现 .

hMax 和 hAdd 以非常相似的方式工作。这两种算法的工作原理是考虑规划图中的一个状态，并使用所有适用的 Action 使该状态中的每个原子为真。使所有原子为真所需的操作成本是它们产生的启发式值的基础。

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

对于 hMax ，给定状态的启发式是 的成本最贵的那个状态的原子。

请注意，这两种算法实际上都没有解决松弛问题，它们只是计算相对于当前状态的给定状态实现难度的估计。

hMax 是可接受的 , 而 hAdd 不是 .

hFF 是不同的，因为它实际上解决了放松的问题。它不会尝试找到最佳解决方案(请参阅下面的 †)，而是寻找合理的解决方案。

要确定给定状态的启发式(我们称之为 s)， hFF 在松弛计划中找到从当前状态到给定状态的解，这通常称为 π(s)。一旦找到该解决方案，赋予状态 s 的启发式值为 宽松解决方案中的操作数 .这可以写成:

h(s) = |π(s)|

hFF 有时称为 轻松的计划 h .是不受理 ，但它是 信息 .

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

† hFF 不尝试找到最佳解决方案，因为虽然比规划原始问题更容易，但计算最佳解决方案仍然是 太难了用作启发式方法，因为必须为每个状态计算它。相反，它试图找到一个合理的计划，这在计算上要便宜得多。

我真的希望这有帮助，并且我没有进一步混淆你。

我也真的希望我是对的 - 我相对自信，但我完全愿意接受纠正。经过人工智能讲师的检查，我现在确信这是正确的。