Minimal Landmarks for Optimal Delete-Free Planning

Authors

  • Patrik Haslum Australian National University and National ICT Australia
  • John Slaney Australian National University and National ICT Australia
  • Sylvie Thiebaux Australian National University and National ICT Australia

DOI:

https://doi.org/10.1609/icaps.v22i1.13534

Keywords:

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

Abstract

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.

Downloads

Published

2012-05-14

How to Cite

Haslum, P., Slaney, J., & Thiebaux, S. (2012). Minimal Landmarks for Optimal Delete-Free Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 22(1), 353-357. https://doi.org/10.1609/icaps.v22i1.13534

Issue

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Section

Short Papers