Planning as satisfiability: Heuristics
Planning as satisfiability: Heuristics
复制标题
DOI：
10.1016/j.artint.2012.08.001
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
J. Rintanen
中科院分区：
文献类型：
--
作者：
J. Rintanen
约简SAT是解决人工智能和计算机科学中困难组合问题的一种非常成功的方法。最常见的是，简化为SAT的问题实例使用通用SAT求解器来解决。虽然有明显的可能性，改善SAT解决过程与应用程序特定的算法，这是很少成功地做到了。在这项工作中，我们提出了一个规划特定的变量选择策略SAT解决。该策略是基于一般原则的属性的计划，其性能与标准的规划基准往往大大提高通用变量选择算法，如VSIDS，并经常提升到与其他搜索方法，如显式状态空间搜索与启发式搜索算法相同的水平。
Reduction to SAT is a very successful approach to solving hard combinatorial problems in Artificial Intelligence and computer science in general. Most commonly, problem instances reduced to SAT are solved with a general-purpose SAT solver. Although there is the obvious possibility of improving the SAT solving process with application-specific heuristics, this has rarely been done successfully. In this work we propose a planning-specific variable selection strategy for SAT solving. The strategy is based on generic principles about properties of plans, and its performance with standard planning benchmarks often substantially improves on generic variable selection heuristics, such as VSIDS, and often lifts it to the same level with other search methods such as explicit state-space search with heuristic search algorithms.