The*_*dor 7 planning heuristics
我正在研究前瞻性规划启发式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撰写的一篇科学论文,发表在德国Converence的AI 2009上,标题为"计划与理论中的h +"练习",这与其他三个密切相关."
https://cw.felk.cvut.cz/wiki/_media/courses/a4m36pah/07_relaxation.pdf
(另一个教程(未知来源),也是关于启发式hmax,hadd,hff.)
你能用更简单的方式解释它们的工作原理吗？谢谢
Mar*_*her 16
我假设你已经理解了规划的基本思想.的HMAX,HADD和hFF的hESC算法被用来计算用于在规划图给定的状态,相对于当前占用状态启发式值.
所有三种算法都通过考虑问题的宽松版本来工作; 具体而言,通过删除每个适用操作的删除列表来放宽的版本.这种效果可以概括为一旦原子实现(变为真实),就可以实现.
hMax和hAdd的工作方式非常相似.这两种算法的工作原理是考虑规划图中的状态,并使用所有适用的动作使该状态中的每个原子都成立.使所有原子成为真的所需动作的成本是它们产生的启发式值的基础.
对于hAdd,给定状态的启发式是实现该状态中每个原子的组合成本.
对于hMax,给定状态的启发式是该状态中最昂贵原子的成本.
请注意,两种算法实际上都不能解决松弛问题,它们只计算相对于当前状态的给定状态实现难度的估计.
hMax是可以接受的,而hAdd则不允许.
hFF是不同的,因为它实际上解决了轻松的问题.它并不试图找到最佳解决方案(参见下面的†),而是寻求合理的解决方案.
为了确定给定状态的启发式(让我们称之为s),hFF在松弛计划中找到从当前状态到给定状态的解,通常称为π(s).一旦找到该解决方案,给予状态s的启发式值是松弛解决方案中的动作的数量.这可以写成:
h(s)= |π(s)|
hFF有时被称为放松计划h.这是不可接受的,但它提供了丰富的信息.
用于在松弛计划中找到解决方案的方法取决于hFF算法的实现.
† hFF并不试图找到最佳解决方案,因为虽然比计划原始问题更容易,但计算最优解仍然太难以作为启发式使用,因为它必须针对每个状态进行计算.相反,它试图找到一个合理的计划,这在计算上要便宜得多.
我真的希望这有所帮助,而且我没有进一步困惑你.
我也非常希望自己是对的 - 我对自己很有信心,但我完全愿意接受纠正. 经过AI讲师检查后,我现在确信这是正确的.