Homomorphisms of Lifted Planning Tasks: The Case for Delete-Free Relaxation Heuristics


  • Rostislav Horčík Czech Technical University in Prague
  • Daniel Fišer Czech Technical University in Prague Saarland University
  • Álvaro Torralba Aalborg University




Planning, Routing, And Scheduling (PRS)


Classical planning tasks are modelled in PDDL which is a schematic language based on first-order logic. Most of the current planners turn this lifted representation into a propositional one via a grounding process. However, grounding may cause an exponential blowup. Therefore it is important to investigate methods for searching for plans on the lifted level. To build a lifted state-based planner, it is necessary to invent lifted heuristics. We introduce maps between PDDL tasks preserving plans allowing to transform a PDDL task into a smaller one. We propose a novel method for computing lifted (admissible) delete-free relaxed heuristics via grounding of the smaller task and computing the (admissible) delete-free relaxed heuristics there. This allows us to transfer the knowledge about relaxed heuristics from the grounded level to the lifted level.




How to Cite

Horčík, R., Fišer, D., & Torralba, Álvaro. (2022). Homomorphisms of Lifted Planning Tasks: The Case for Delete-Free Relaxation Heuristics. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 9767-9775. https://doi.org/10.1609/aaai.v36i9.21212



AAAI Technical Track on Planning, Routing, and Scheduling