用SAT做探针，贪心搜索高效求解规划问题
SibylSat: Using SAT as an Oracle to Perform a Greedy Search on TOHTN Planning
- 以求解松弛问题的SAT解作为启发，贪心选择分解方向
- 在多数IPC基准上运行更快，且成功率更高
- 适合需要快速生成高质量计划的场景
本文提出SibylSat，一种基于SAT的新型方法，用于高效求解完全有序的HTN规划问题（TOHTN）。与以往采用广度优先搜索的SAT-based规划器不同，SibylSat采用贪心搜索策略，通过求解一个松弛后的、同样表达为SAT问题的子问题来获取启发式信息，指导更有希望的分解路径选择。实验表明，在多数IPC基准上，SibylSat不仅运行时间更短，且生成的计划质量更高，同时能求解更多问题。
原文摘要 · Abstract (English)
This paper presents SibylSat, a novel SAT-based method designed to efficiently solve totally-ordered HTN problems (TOHTN). In contrast to prevailing SAT-based HTN planners that employ a breadth-first search strategy, SibylSat adopts a greedy search approach, enabling it to identify promising decompositions for expansion. The selection process is facilitated by a heuristic derived from solving a relaxed problem, which is also expressed as a SAT problem. Our experimental evaluations demonstrate that SibylSat outperforms existing SAT-based TOHTN approaches in terms of both runtime and plan quality on most of the IPC benchmarks, while also solving a larger number of problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。