Red-Black Relaxed Plan Heuristics

Authors

  • Michael Katz Saarland University
  • Joerg Hoffmann Saarland University
  • Carmel Domshlak Technion Haifa

DOI:

https://doi.org/10.1609/aaai.v27i1.8644

Keywords:

Classical Planning, Heuristic Search, Delete Relaxation, Red-Black Planning

Abstract

Despite its success, the delete relaxation has significant pitfalls. Recent work has devised the red-black planning framework, where red variables take the relaxed semantics (accumulating their values), while black variables take the regular semantics. Provided the red variables are chosen so that red-black plan generation is tractable, one can generate such a plan for every search state, and take its length as the heuristic distance estimate. Previous results were not suitable for this purpose because they identified tractable fragments for red-black plan existence, as opposed to red-black plan generation. We identify a new fragment of red-black planning, that fixes this issue. We devise machinery to efficiently generate red-black plans, and to automatically select the red variables. Experiments show that the resulting heuristics can significantly improve over standard delete relaxation heuristics.

Downloads

Published

2013-06-30

How to Cite

Katz, M., Hoffmann, J., & Domshlak, C. (2013). Red-Black Relaxed Plan Heuristics. Proceedings of the AAAI Conference on Artificial Intelligence, 27(1), 489-495. https://doi.org/10.1609/aaai.v27i1.8644