快进和pddl：是最好的计算解决方案？

Question

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

是否存在一个自动工具来解决这个问题？

非常感谢！

Answer 1

如果我不记得它错了FF不是一个最佳规划者，所以你不能确定生成的规划是否是最优的。另一方面，FF在产生“足够好”的解决方案方面很快，与最佳规划人员（cpt4，bjolp，ecc ...）相比，他们提供了最优方案，但比满足规划人员要慢得多。

您可以在这里找到这些策划者的名单：IPC2011 Planners

这是我能想象到的写下来全搜索空间以及A *上，它除了获得最佳的计划的唯一途径。

Answer 2

正如Demplo已经指出的那样，FF并不能保证找到最佳解决方案。其中的原因是很重要的情况下，知道你真的想找到最佳的解决方案：

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

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

我建议安装着名的Fast Downward Planning System（www.fast-downward.org/），因为它支持大量不同的算法和启发式算法。正如所说的那样，算法应该选择A *，并且任何可接受的都是启发式的。有了这样的组合，任何找到的计划都是针对给定问题的最佳解决方案。 （只针对搜索/规划专家）：如果实现树搜索而不是图搜索（即，如果副本重复展开），则A *只能保证找到最佳解决方案。如果它实现图搜索，启发式是不够的，它也需要单调（也称为一致）。但是，根据http://www.fast-downward.org/Doc/SearchEngine，它实现了树搜索（我认为）。此外，也有一致的启发式方法。