提出两种无需实例化即可编译约束的新方法,适用于大规模规划问题。
Two Constraint Compilation Methods for Lifted Planning
- 不依赖问题实例化,直接编译约束
- 生成的规划规格比传统方法简洁数十倍
- 适合高基数动作与大量对象的大规模规划任务
我们研究了带有定性状态轨迹约束的PDDL片段中的规划问题,这类约束常见于安全要求、任务顺序和中间子目标。现有编译方法需在编译前对问题进行实例化,导致在对象数量多、高阶动作频繁的问题上难以扩展。为此,我们提出两种无需实例化的约束编译方法,适用于大规模规划。证明了方法正确性并分析了最坏情况时间复杂度。在最新国际规划竞赛使用的多个领域上进行了可复现的实验评估。结果表明,新方法效率高,生成的规划规范比基于实例化编译的方法简洁数十倍,且使用先进规划器时仍保持竞争力。
原文摘要 · Abstract (English)
We study planning in a fragment of PDDL with qualitative state-trajectory constraints, capturing safety requirements, task ordering conditions, and intermediate sub-goals commonly found in real-world problems. A prominent approach to tackle such problems is to compile their constraints away, leading to a problem that is supported by state-of-the-art planners. Unfortunately, existing compilers do not scale on problems with a large number of objects and high-arity actions, as they necessitate grounding the problem before compilation. To address this issue, we propose two methods for compiling away constraints without grounding, making them suitable for large-scale planning problems. We prove the correctness of our compilers and outline their worst-case time complexity. Moreover, we present a reproducible empirical evaluation on the domains used in the latest International Planning Competition. Our results demonstrate that our methods are efficient and produce planning specifications that are orders of magnitude more succinct than the ones produced by compilers that ground the domain, while remaining competitive when used for planning with a state-of-the-art planner.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。