AAAI Publications, Twenty-First International Conference on Automated Planning and Scheduling

Font Size: 
A Complete Algorithm for Generating Landmarks
Blai Bonet, Julio Castillo

Last modified: 2011-03-22


A collection of landmarks is complete if the cost of a minimum-cost hitting set equals h+ and there is a minimum-cost hitting set that is an optimal relaxed plan. We present an algorithm for generating a complete collection of landmarks and we show that this algorithm can be extended into effective polytime heuristics for optimal and satisficing planning. The new admissible heuristics are compared with current state-of-the-art heuristics for optimal planning on benchmark problems from the IPC.

Full Text: PDF