TL;DR
This paper introduces a novel family of "landmark" heuristics for lifted classical planning, a more efficient way to represent planning problems. By adapting existing landmark extraction techniques to this lifted setting, the authors demonstrate significant performance improvements, especially when combined with other lifted heuristics in a LAMA-style search.
What Problem Does This Paper Address?
Classical AI planning systems often struggle with the sheer size of "grounded" task representations. While planning problems are typically described in a "lifted" format using predicates and action schemas with variables, these need to be "grounded" into concrete propositions and actions over specific objects for many planning algorithms. This grounding process can lead to an exponential explosion in size, making planning infeasible for many real-world problems.
Existing "lifted" planning approaches aim to avoid this full grounding. While some progress has been made with lifted forward search and delete relaxation heuristics, a powerful class of heuristics based on "landmarks" has remained largely inaccessible in the lifted domain. Landmarks are facts or actions that must be true or executed at some point in every valid plan. This paper bridges this gap by developing methods to extract and utilize these valuable landmark heuristics directly in the lifted planning setting.
Methods
The core contribution of this paper is the development of two new methods for extracting lifted landmarks:
- Necessary Subgoals: This method adapts a grounded technique that works by "backchaining" from the goal. It identifies facts that are preconditions for actions that achieve the goal, and recursively continues this process. In the lifted setting, this involves considering partially grounded predicates and action schemas, and carefully intersecting preconditions to derive new, less specific (lifted) subgoals.
- FAM-Cut Landmarks: This approach is inspired by Domain Transition Graphs (DTGs) used in grounded planning. It leverages "Lifted Fact-Alternating Mutex (FAM) groups," which represent sets of mutually exclusive predicates for a given variable assignment. By constructing a graph of possible transitions within these FAM groups and identifying "cuts" that are necessary to reach the goal from the initial state, the method derives lifted landmarks.
The paper also proposes a heuristic function, hLM, based on these lifted landmarks, which counts the number of landmarks that still need to be fulfilled. This heuristic is designed to be admissible and dominates simple goal counting. Crucially, the authors integrate this hLM heuristic with lifted delete relaxation heuristics (hLadd) within a LAMA-style search framework, which uses multiple open lists and preferred operators to guide the search more effectively.
Datasets
The experiments were conducted using a benchmark set previously introduced by Lauer et al. [2021]. This benchmark suite is designed to evaluate lifted planners by exploring problems that are difficult to ground due to:
- Large action-schema arity
- Large predicate arity
- Large object universes
Key Insights and Ideas
- Landmarks are valuable in the lifted setting: Despite the challenges of adapting landmark extraction, the paper demonstrates that these heuristics are indeed effective and can significantly improve planning performance.
- Two distinct landmark extraction methods offer complementary strengths: The "necessary subgoals" and "FAM-cut" methods provide different ways to identify critical facts, catering to various problem structures.
- Combining heuristics is key: While lifted landmark heuristics alone show promise, their true power is unleashed when combined with other lifted heuristics (like delete relaxation) within a sophisticated search strategy (LAMA-style).
- Lifted planning is a rapidly advancing field: The paper highlights the growing importance of lifted planning and the need for efficient heuristic methods to tackle complex problems.
Key Results
The paper reports significant improvements in planning performance:
- The proposed lifted landmark heuristics, especially when combined with lifted delete relaxation heuristics in a LAMA-style search, outperform the state-of-the-art in lifted planning.
- The LAMA-style search configurations using landmarks (
hLNS→andhLFAM→) achieved the highest overall coverage across the tested benchmarks. - The ordering constraints derived from landmark extraction provided only minor improvements, which the authors attribute to the overhead of tracking them and their basic nature.
- The FAM-cut landmarks performed slightly worse than necessary subgoals when used in simpler search configurations, but both benefited greatly from the LAMA-style search.
- Landmark generation time was found to be relatively small compared to the overall planning time.
Limitations and Future Work
- Ordering constraints: The current ordering constraints derived from landmark extraction are basic and do not significantly improve performance, suggesting potential for more sophisticated ordering techniques.
- Heuristic combination: While the combination with lifted delete relaxation is effective, further exploration of combining different lifted heuristics could yield even better results.
- Landmark extraction completeness: The paper acknowledges that the landmark extraction methods are based on sufficient criteria and may not find all possible landmarks, leaving room for more complete extraction algorithms.
- Future work: The authors suggest exploring more complex landmark extraction methods and investigating the potential for combining different types of lifted heuristics. They also note the possibility of constructing multiple lifted landmarks from a single precondition if a predicate appears multiple times.
Summary updated