Landmark-enhanced abstraction heuristics

Abstractions and landmarks are two of the key mechanisms for devising admissible heuristics for domain-independent planning. Here we aim at combining them by integrating landmark information into abstractions. We propose a concrete scheme for compiling landmarks into the problem specification. This scheme, which preserves all reachable properties of the original problem, is especially suited to implicit abstraction heuristics. Our formal and empirical analysis shows that landmark information can substantially improve the quality of heuristic estimates.