Delete-Relaxation Heuristics for Lifted Classical Planning


  • Augusto B. Corrêa University of Basel, Switzerland
  • Guillem Francès Universitat Pompeu Fabra, Spain
  • Florian Pommerening University of Basel, Switzerland
  • Malte Helmert University of Basel, Switzerland


Classical Planning Techniques And Analysis


Recent research in classical planning has shown the importance of search techniques that operate directly on the lifted representation of the problem, particularly in domains where the ground representation is prohibitively large. In this paper, we show how to compute the additive and maximum heuristics from the lifted representation of a problem. We do this by adapting well-known reachability analysis techniques based on a Datalog formulation of the delete relaxation of the problem. Our adaptation allows us to obtain not only the desired heuristic value, but also other useful heuristic information such as helpful actions. Our empirical evaluation shows that our lifted version of the additive heuristic is competitive with its ground counterpart on most of the standard international competition benchmarks, and significantly outperforms other state-of-the-art lifted heuristic methods in the literature.




How to Cite

Corrêa, A. B., Francès, G., Pommerening, F., & Helmert, M. (2021). Delete-Relaxation Heuristics for Lifted Classical Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 94-102. Retrieved from