TL;DR
This paper introduces a novel relaxation technique for PDDL planning that allows heuristic functions to run in polynomial time with respect to the PDDL input size, rather than the exponentially larger grounded representation. This is achieved by splitting predicates into smaller, fixed-arity ones, enabling efficient planning for complex problems that were previously intractable.
What Problem Does This Paper Address?
Classical AI planning systems often rely on heuristic search to find solutions. A cornerstone of many successful heuristics is the "delete relaxation," which simplifies planning by ignoring negative effects of actions. However, a major bottleneck is that these heuristics are typically computed on a grounded representation of the planning problem, where all variables are replaced by specific objects. This grounded representation can be exponentially larger than the original lifted PDDL input, making planning infeasible for many real-world scenarios with large object universes or complex predicates/actions. Existing approaches to tackle this "grounding blow-up" have had limited success. This paper aims to bridge this gap by developing a heuristic that is efficient with respect to the PDDL input size itself.
Methods
The core contribution is a new relaxation strategy that splits predicates into smaller ones of a fixed arity, denoted by $K$. For a predicate $P(x_1, \dots, x_n)$, it's replaced by predicates of the form $P_i(x_{i_1}, \dots, x_{i_K})$ for all $K$-element subsets of the original parameters. This "K-ary predicate splitting" results in a new planning task $\Pi|_K$ where the complexity is exponential only in $K$, making it polynomial for a fixed $K$.
The authors prove that while computing a delete-relaxed plan for $\Pi|_K$ remains NP-hard for $K \ge 2$, it becomes polynomial for $K=1$ (unary relaxation). They then implement a polynomial-time heuristic function, hur, based on this unary relaxation. Additionally, they propose an optimization, hur-d, that leverages static predicates to improve heuristic accuracy by considering their constraints during action selection.
Datasets
The paper evaluates their approach on several benchmarks:
- Existing benchmarks for hard-to-ground planning: These include domains like Genome Edit Distance (GED), Organic Synthesis, and Pipesworld-Tankage, which were previously used to test lifted planning.
- Newly designed benchmarks: To specifically address challenges related to large predicate arity and large object universes, the authors created new instances of standard IPC domains like Visitall and Childsnack. They also generated large instances of Blocksworld, Logistics, and Rovers. These new benchmarks are designed to be hard to ground but solvable by lifted planners, allowing for a focused evaluation of lifted heuristic performance.
Key Insights and Ideas
- The "grounding blow-up" is a fundamental barrier: The paper clearly articulates why the exponential difference between lifted PDDL and grounded representations is a critical problem for practical AI planning.
- K-ary splitting as a path to polynomial time: The insight that splitting predicates into a fixed, small arity ($K$) can drastically reduce the complexity, making it polynomial in the PDDL input size for fixed $K$, is the central technical innovation.
- Unary relaxation ($K=1$) is the sweet spot for polynomial-time computation: The theoretical result that $K=1$ allows for polynomial-time computation of delete-relaxed plans is crucial. This is the basis for their efficient heuristic.
- Static predicates offer a practical way to improve heuristic accuracy without sacrificing polynomial time: The
hur-doptimization demonstrates that incorporating information from static predicates can significantly enhance heuristic performance by better constraining action applicability, even within the polynomial-time framework. - New benchmarks are essential for evaluating lifted planning: The paper highlights the limitations of existing benchmarks and introduces new ones specifically designed to test the challenges of lifted planning, particularly concerning predicate and object arity.
Key Results
- The proposed unary relaxation heuristic (
hur) runs in time polynomial to the PDDL input size. - The
hur-dheuristic, which incorporates static predicate information, further improves performance, especially on domains with large predicate arity. - On the newly designed benchmarks (which are hard to ground), the new heuristics significantly outperform existing lifted planners and achieve competitive results with grounded planners, despite the latter's much larger computational cost.
- The paper reports that their heuristics are very fast, with node generation rates comparable to goal-counting heuristics.
Limitations and Future Work
- Information loss in splitting: The paper acknowledges that predicate splitting, especially for $K>1$, can lead to information loss. The delete relaxation combined with splitting is an over-approximation, meaning plans for the relaxed task are not necessarily valid for the original task.
- Heuristic informativeness: While the heuristics are fast, they are not always informative. For instance, in the Logistics domain, they fall behind goal-counting heuristics. The authors suggest that this might be due to the information loss in unary splitting.
- Future work directions: The authors suggest exploring larger tractable fragments of predicate splitting, flexible splitting onto arbitrary sets of parameter tuples, and developing clever methods for choosing these sets. They also mention that the disambiguation technique could potentially be applied to non-static predicates, though this would increase computational cost.
Summary updated