A Complete Algorithm for Generating Landmarks

Vol. 21 (2011): Twenty-First International Conference on Automated Planning and Scheduling

Volume

Vol. 21 (2011): Twenty-First International Conference on Automated Planning and Scheduling

Short Papers

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.

10.1609/icaps.v21i1.13482