通过目标回溯生成通用规划规则，提升规划效率与覆盖范围。
Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version)
- 按目标原子顺序求解训练问题，再通过目标回溯提取通用规则。
- 在经典与数值规划域上，合成成本、覆盖率和解质量均优于现有方法。
- 适合需要高效通用规划的复杂任务场景，尤其适用于搜索空间剪枝。
通用规划（GP）旨在合成可解决一系列相关规划问题的程序。本文提出一种新颖且简洁的GP方法：给定一组训练问题，对每个问题按顺序计算各目标原子的最优解，对所得计划执行目标回溯，并将结果提升为一阶条件→动作规则集。这些规则共同构成一个可直接执行或用于剪枝规划搜索空间的通用计划。我们形式化并证明了该方法在特定条件下能保证生成有效通用计划，并给出了状态空间剪枝公理。实验表明，在多个经典与数值规划领域中，该方法在合成成本、规划覆盖率和解质量三个指标上均显著优于当前最先进（通用）规划器。
原文摘要 · Abstract (English)
Generalised planning (GP) refers to the task of synthesising programs that solve families of related planning problems. We introduce a novel, yet simple method for GP: given a set of training problems, for each problem, compute an optimal plan for each goal atom in some order, perform goal regression on the resulting plans, and lift the corresponding outputs to obtain a set of first-order $\textit{Condition} \rightarrow \textit{Actions}$ rules. The rules collectively constitute a generalised plan that can be executed as is or alternatively be used to prune the planning search space. We formalise and prove the conditions under which our method is guaranteed to learn valid generalised plans and state space pruning axioms for search. Experiments demonstrate significant improvements over state-of-the-art (generalised) planners with respect to the 3 metrics of synthesis cost, planning coverage, and solution quality on various classical and numeric planning domains.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。