通过半朴素Datalog实现规划并行化，显著提升求解效率。
Parallel Lifted Planning via Semi-Naive Datalog Evaluation
- 采用规则级与实例级双层并行，结合团枚举加速地面化。
- 在8核上对难实例实现6倍加速，92.4%的并行度。
- 适合需要高效求解的复杂规划任务，尤其适用于大规模地面化场景。
提升式经典规划器直接在一阶规划任务上操作，避免耗时的地面化步骤。然而，提升式规划通常较慢，因规划器需在搜索中反复实例化底层结构。此前，继承生成、公理评估、任务地面化及删除松弛启发式等核心组件已被视为Datalog评估问题。本文在此基础上，提出一种双层并行执行模型：规则级并行与地面化并行，并针对规划负载优化，设计基于团枚举的地面化器，支持半朴素Datalog评估。实验使用贪心最佳优先搜索结合FF启发式，结果表明：单核下已超越基线求解更多任务，多核时优势扩大。在平均97.6%时间消耗于Datalog执行的困难任务上，该模型平均并行度达92.4%，8核实测最高提速6倍。
原文摘要 · Abstract (English)
Lifted classical planners operate directly on first-order planning tasks to avoid the computationally demanding grounding step. However, lifted planning is typically slower, as planners must repeatedly instantiate ground structures during search. Many core components of lifted classical planning, such as successor generation, axiom evaluation, task grounding, and delete-relaxed heuristics, have previously been studied through the lens of Datalog evaluation. We build upon this line of work and extend it by developing and analyzing an execution model with two levels of parallelism: rule-level parallelism and grounding parallelism. We further specialize this solver for planning-specific workloads with a grounder based on clique enumeration, which we extend to support semi-naive Datalog evaluation. Our experimental evaluation using greedy best-first search with the FF heuristic shows that our implementation already solves more tasks than the baselines on a single core, and the gap widens as additional cores are used. Moreover, on hard-to-ground tasks where on average 97.6% of the total runtime is spent in Datalog execution, the proposed execution model exhibits an average parallel fraction of 92.4%, while achieving up to a 6-fold speedup on 8 cores in practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。