Researchers have developed a parallel lifted planning algorithm using semi-naive Datalog evaluation that significantly accelerates classical AI planning by combining rule-level and grounding-level parallelism. The approach achieves up to 6-fold speedup on 8 cores and solves more planning tasks than existing baselines, particularly on computationally intensive grounding operations.
This research addresses a fundamental computational bottleneck in lifted classical planning, where planners traditionally struggle with the grounding step—converting first-order logic representations into ground structures. The authors leverage Datalog evaluation as a unifying framework for planning operations, building on prior work that recognized connections between Datalog and planning components like heuristic computation and successor generation. The innovation centers on introducing two-level parallelism: rule-level parallelism optimizes the evaluation of multiple inference rules simultaneously, while grounding parallelism accelerates the instantiation of logical structures.
The semi-naive Datalog evaluation strategy, enhanced with clique enumeration-based grounding, represents a meaningful engineering advance for planning systems. Traditional lifted planners avoid full grounding to save time, yet still perform repeated instantiation during search—creating a performance paradox. This work effectively bridges that gap through parallelization, achieving 92.4% average parallel efficiency on hard-to-ground tasks where 97.6% of runtime occurs in Datalog evaluation. The 6-fold speedup on 8 cores demonstrates practical scalability.
For the AI planning and automated reasoning communities, this development has implications for scaling planning algorithms to larger problem domains. Planning applications span robotics, logistics, and game AI—domains where faster grounding directly improves deployment feasibility. While the research is academically rigorous rather than commercially disruptive, it contributes to the broader trend of making symbolic AI systems more computationally tractable through parallelization and algorithmic optimization. The work particularly benefits problems with large first-order state spaces where traditional grounding becomes prohibitive.
- →Parallel Datalog evaluation with two-level parallelism accelerates lifted classical planning by up to 6x on 8 cores.
- →Semi-naive Datalog evaluation combined with clique enumeration improves grounding performance on hard-to-ground planning tasks.
- →The approach solves more benchmark tasks than existing baselines while maintaining single-core efficiency improvements.
- →Average parallel efficiency of 92.4% on grounding-intensive workloads demonstrates strong scalability characteristics.
- →This research makes lifted planning more practical for large-scale applications in robotics and automated reasoning domains.