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

No. 9: AAAI-22 Technical Tracks 9

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 36

AAAI Technical Track on Planning, Routing, and Scheduling

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.

10.1609/aaai.v36i9.21212