Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?

By Malte Helmert, Carmel Domshlak. International Conference on Automated Planning and Scheduling, 2009

569 citations recorded by the source corpus.

Current heuristic estimators for classical domain-independent planning are usually based on one of four ideas: delete relaxations, critical paths, abstractions, and, most recently, landmarks. Previously, these different ideas for deriving heuristic functions were largely unconnected.We prove that admissible heuristics based on these ideas are in fact very closely related. Exploiting this relationship, we introduce a new admissible heuristic called the landmark cut heuristic, which compares favourably with the state of the art in terms of heuristic accuracy and overall performance.

Subfields: Artificial Intelligence, Ocean Engineering

View Paper: https://www.semanticscholar.org/paper/e5baf9a1c0b60a2600cff176d40ef3ff6ec40a4e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Ocean Engineering

Citations in the corpus

Inventing Relational State and Action Abstractions for Effective and Efficient Bilevel Planning (2022, methodology): “1, Line 2), we leverage the STRIPS-style operators and predicates [11] to automatically derive a domain-independent heuristic popularized by the AI planning community, such as LMCut [22].”
Coming up With Good Excuses: What to do When no Plan Can be Found (2010, methodology): “Because this heuristic is not admissible, the results are not guaranteed to be optimal, so we additionally ran tests using A and the (admissible) landmark cut heuristics (Helmert and Domshlak 2009).”
Fast Detection of Unsolvable Planning Instances Using Local Consistency (2013, background): “See, for instance, Helmert and Domshlak (2009) for a survey and comparison of the most popular heuristics.”
"Distance"? Who Cares? Tailoring Merge-and-Shrink Heuristics to Detect Unsolvability (2014, unknown): “cut (Helmert and Domshlak 2009).”
Automated Planning and Acting (2016, background): “Most of them can be classified roughly as delete-relaxation heuristics, landmark heuristics, critical-path heuristics, and abstraction heuristics [269].”