Parallel Lifted Planning via Semi-Naive Datalog Evaluation

2026-05-08 · Source: Artificial Intelligence · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

Lifted classical planners, which operate directly on first-order planning tasks to bypass computationally intensive grounding, are often slower due to repeated instantiation of ground structures during search. This research extends prior work on Datalog evaluation for lifted planning components like successor generation and axiom evaluation. It introduces an execution model featuring two levels of parallelism: rule-level and grounding parallelism. The solver is specialized for planning workloads using a clique enumeration-based grounder, enhanced with semi-naive Datalog evaluation. Experimental results, using greedy best-first search with the FF heuristic, demonstrate that this implementation solves more tasks than baseline methods on a single core, with performance improving further with additional cores. For tasks where Datalog execution accounts for 97.6% of runtime, the model achieves an average parallel fraction of 92.4% and up to a 6-fold speedup on 8 cores.

Key takeaway

For research scientists developing or optimizing classical planners, this work indicates that integrating parallel Datalog evaluation can dramatically improve performance, especially on hard-to-ground tasks. You should explore adopting rule-level and grounding parallelism within your planning systems to achieve substantial speedups, potentially up to 6-fold on multi-core architectures, and solve a broader range of complex problems more efficiently.

Key insights

Parallel Datalog evaluation significantly accelerates lifted classical planning by avoiding costly grounding.

Principles

• Lifted planning avoids grounding overhead.
• Datalog evaluation can parallelize planning components.

Method

The method involves a Datalog-based execution model with rule-level and grounding parallelism, specialized for planning via a clique enumeration grounder extended for semi-naive evaluation.

In practice

• Use Datalog for lifted planning components.
• Employ clique enumeration for grounding.
• Implement semi-naive Datalog evaluation.

Topics

• Lifted Planning
• Datalog Evaluation
• Parallel Execution
• Semi-Naive Datalog
• Clique Enumeration

Best for: Research Scientist, AI Scientist

Related on AIssential

• BLINKG: A Benchmark for LLM-Integrated Knowledge Graph Generation — BLINKG provides a standardized benchmark to evaluate Large Language Models' effectiveness in mapping data schemes to ontology concepts for Knowledge Graph generation.
• Agentic Systems and Their Design Patterns — Part 3: Parallelization — Parallelization in agentic systems executes independent subtasks concurrently to improve speed and output quality.
• Trajectory-Level Data Augmentation for Offline Reinforcement Learning — LIFT augments suboptimal offline RL trajectories by identifying geometric "shortcuts" to improve data quality and learning.
• JetFlow: Breaking the Scaling Ceiling of Speculative Decoding with Parallel Tree Drafting — JetFlow breaks speculative decoding's scaling ceiling by combining parallel drafting efficiency with branch-wise causal conditioning for higher acceptance.
• Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning — Efficient lookahead encoding and relational abstraction significantly improve generalized planning policy performance and scalability.
• Semantic Partial Grounding via LLMs — LLMs can significantly accelerate classical planning by semantically pre-filtering irrelevant PDDL elements before grounding.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Artificial Intelligence.