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

Font Size: 
Minimal Landmarks for Optimal Delete-Free Planning
Patrik Haslum, John Slaney, Sylvie Thiebaux

Last modified: 2012-05-14


We present a simple and efficient algorithm to solve delete-free planning problems optimally and calculate the h+ heuristic. The algorithm efficiently computes a minimum-cost hitting set for a complete set of disjunctive action landmarks generated on the fly. Unlike other recent approaches, the landmarks it generates are guaranteed to be set-inclusion minimal. In almost all delete-relaxed IPC domains, this leads to a significant coverage and runtime improvement.


optimal planning; delete-free problems; landmarks; hitting sets

Full Text: PDF