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

Vol. 19 (2009): Nineteenth International Conference on Automated Planning and Scheduling

Volume

Vol. 19 (2009): Nineteenth International Conference on Automated Planning and Scheduling

Long Papers

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.

10.1609/icaps.v19i1.13370