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

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.