Abstract
Lifted planning is defined as planning directly over a first-order representation, avoiding the "grounding bottleneck" that plagues propositional planners. While historically sidelined, recent advances in search-based and satisfiability-based techniques have enabled lifted planners to scale to complex problems. This survey explores how modern methods from database theory and constraint satisfaction are making lifted planning competitive with state-of-the-art grounded systems.
Introduction: The Grounding Bottleneck
In classical automated planning, worlds are described using first-order (FO) logic. For example, a "move" action schema might describe how any truck can move between any two locations. Most modern planners are "grounded": they instantiate every possible combination of objects and actions before searching for a solution. While effective for small tasks, this approach leads to a "grounding explosion" in large domains. If a task involves 10 trucks and 100 locations, a single schema generates 1,000 concrete actions. In many-object domains, planners often run out of memory during this preprocessing phase.
Lifted planning addresses this by reasoning directly over the abstract FO schemas. Recent breakthroughs have revitalized this field, offering solutions for problems where grounding is infeasible.
Architectural Advances
Recent progress in lifted planning can be categorized into two main approaches:
1. Lifted Heuristic Search
These planners perform state-space search while keeping actions lifted. Two critical components have seen major improvements:
- Successor Generation: Finding applicable actions in a state is now treated as a Conjunctive Query (CQ) problem. Planners like Powerlifted use database join optimization techniques to efficiently find valid variable assignments.
- Heuristic Computation: Estimating the distance to the goal is done using Datalog-based heuristics. By modeling delete-relaxation as a Datalog program, planners compute reachability and cost estimates (e.g., $h^{add}$, $h^{FF}$) directly on the lifted representation.
2. Lifted Planning as Satisfiability
These planners encode the entire task into a logical formula rather than searching states.
- SAT Encodings: Planners like LiSAT create propositional formulas where variables represent action schemas and their parameters at each step, resulting in much smaller formulas than grounded counterparts.
- QBF Encodings: Quantified Boolean Formulas (QBF) provide even more compact representations, scaling linearly with the number of action schemas.
Key Insights and Scalability
The "new generation" of lifted planners leverages several cross-disciplinary insights:
- Database Integration: Realizing that finding applicable actions is isomorphic to database querying allows planners to adopt highly optimized query engines.
- Homomorphisms and Symmetry: Graph-theoretic techniques (like Gaifman graphs) are used to identify homomorphisms that simplify large problems by collapsing similar objects while preserving solvability.
- Grounding On-Demand: Rather than grounding everything upfront, modern planners ground only the specific variables necessary to validate a search node, combining propositional efficiency with FO memory savings.
Results and Future Outlook
Empirical results show that lifted planners now achieve performance parity with state-of-the-art grounded planners on standard benchmarks. More importantly, they excel in "many-object" variants of International Planning Competition (IPC) tasks where grounded planners fail.
Future research aims to bridge the "heuristic gap" by lifting more complex grounded heuristics (e.g., operator-counting) and extending these techniques to more expressive languages involving numeric fluents or non-determinism. Lifted planning also serves as a gateway to handling domains with infinite objects, representing a significant frontier for automated reasoning.
Summary updated