AAAI Publications, Nineteenth International Conference on Automated Planning and Scheduling

Font Size: 
Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?
Malte Helmert, Carmel Domshlak

Last modified: 2009-10-16


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.


optimal sequential planning; heuristic search; relaxation heuristics; abstraction heuristics; landmarks

Full Text: PDF