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

Font Size: 
Optimal Planning for Delete-Free Tasks with Incremental LM-Cut
Florian Pommerening, Malte Helmert

Last modified: 2012-05-14


Optimal plans of delete-free planning tasks are interesting both in domains that have no delete effects and as the relaxation heuristic h+ in general planning. Many heuristics for optimal and satisficing planning approximate the h+ heuristic, which is well-informed and admissible but intractable to compute. In this work, branch-and-bound and IDA* search are used in a search space tailored to delete-free planning together with an incrementally computed version of the LM-cut heuristic. The resulting algorithm for optimal delete-free planning exceeds the performance of A* with the LM-cut heuristic in the state-of-the-art planner Fast Downward.


delete-free planning; optimal planning; heuristic search; branch-and-bound

Full Text: PDF