问题描述
我如何确定由快速前瞻计划者计算出的计划是所有可能计划中最好的?！
how can i be sure that the plan, computed by the fast forward planner, is the best of all the possible plans?!
是否存在解决此问题的自动工具?！
Does exist an automatic tool to solve this problem?!
非常感谢！
推荐答案
正如Demplo所指出的，FF无法保证找到最佳解决方案.重要的是要知道，以防您真的想找到最佳解决方案:
As Demplo already pointed out, FF does not guarantee to find optimal solutions. The reason for it is important to know in case you really want to find optimal solutions:
- 它使用的算法(强制爬山)不能提供最优性保证
- 它使用的启发式(FF启发式)也不适用于寻找最佳解决方案.
要修复"这两个问题，需要结合使用A *算法和可允许的启发式方法.
To "fix" both, one needs to use the A* algorithm in combination with an admissible heuristic.
我建议安装著名的快速向下计划系统(www.fast-downward.org/)，因为它支持大量不同的算法和启发式算法.正如algithm所述，应该选择A *，并且可以选择任何启发式.通过这种组合，找到的任何计划都是解决给定问题的最佳方案.
I recommend to install the well-known Fast Downward Planning System (www.fast-downward.org/), as it supports a large number of different algorithms and heuristics. As algithm, as said, A* should be chosen, and as heuristic any that is admissible. With such a combination, any found plan is an optimal solution to the given problem.
仅作说明(主要针对搜索/计划专家):A *仅在实现树搜索而不是图形搜索(即重复重复复制副本)的情况下，才能保证找到最佳解决方案.如果它实现了图搜索，那么仅凭启发式就不能接受，它还必须是单调的(也称为一致性).但是，根据 http://www.fast-downward.org/Doc/SearchEngine ，它实现了树搜索(我认为).另外，也有一致的启发式方法.
Just a remark (mainly for the search/planning experts): A* is only guaranteed to find optimal solutions if it implements tree search, rather than graph search (i.e., if duplicates are repeatedly expanded). If it implements graph search, it's not sufficient for the heuristic to be admissible, it also needs to be monotone (also called consistent). However, according to http://www.fast-downward.org/Doc/SearchEngine, it implements tree search (I think). Also, there are consistent heuristics, too.
这篇关于快进和pddl:计算出的解决方案是最好的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！