0

我怎么能确定由快进计划器计算出的计划是所有可能计划中最好的？！

是否存在解决此问题的自动工具？！

多谢！

4

2 回答 2

1

如果我不记得错了，FF 不是最佳计划者，因此您无法确定生成的计划是否是最佳的。另一方面，FF 在生成“足够好”的解决方案方面速度很快，与提供最优计划但比令人满意的计划者慢得多的最优规划器 ( cpt4, , ecc ...) 相比。bjolp

您可以在此处找到这些规划器的列表：IPC2011 规划器

除了写下完整的搜索空间并在其上使用 A* 之外，这是我能想到的获得最佳计划的唯一方法。

于 2014-07-16T09:26:49.070 回答
1

正如 Demlo 已经指出的那样，FF 不保证找到最佳解决方案。如果您真的想找到最佳解决方案，了解其原因很重要：

  1. 它使用的算法（强制爬山）不提供最优性保证
  2. 它使用的启发式（FF 启发式）也不适合找到最佳解决方案。

要“修复”两者，需要将 A* 算法与可接受的启发式算法结合使用。

我建议安装著名的快速向下规划系统 (www.fast-downward.org/)，因为它支持大量不同的算法和启发式算法。如上所述，作为算法，应该选择 A*，并且作为启发式，任何可以接受的。通过这样的组合，任何找到的计划都是给定问题的最佳解决方案。

只是一个评论（主要针对搜索/规划专家）：A* 只有在实现树搜索而不是图搜索时才能保证找到最佳解决方案（即，如果重复扩展重复项）。如果它实现了图搜索，启发式是不够的，它还需要是单调的（也称为一致的）。但是，根据http://www.fast-downward.org/Doc/SearchEngine，它实现了树搜索（我认为）。此外，也有一致的启发式方法。

于 2016-10-15T18:15:58.263 回答