Title:	Formulating PDB heuristics for lifted optimal planning
DNr:	NAISS 2026/4-697
Project Type:	NAISS Small
Principal Investigator:	Mika Skjelnes <mika.skjelnes@liu.se>
Affiliation:	Linköpings universitet
Duration:	2026-04-13 – 2027-05-01
Classification:	10201
Keywords:

Abstract

Main Supervisor: Jendrik Seipp, Linköping University In this project, we aim to compute high-quality heuristics on lifted optimal planning. Lifted planning, in contrary to grounded planning, does not face the core bottleneck of instantiating all of the objects and actions in he planning task. Consequentially, lifted planners level can in theory solve problems that are out of reach for grounded planners. Planning domain such as those related to organic synthesis and circuit optimization exhibit planning problems where grounded planners fail due to aforementioned bottleneck. Although lifted planning sounds lucrative on paper, working with lifted planning introduces hard challenges that are unseen in grounded planning. For instance, heuristics that are strong in the grounded setting often have no obvious translation to the lifted setting without suffering a signfificant detriment to the heuristic quality. A side effect of this is that the available set of lifted heuristics are either quite uninformative to provide good guidance to search, or are too computationally involved to pay off in search. Our work investigates how state-of-the-art grounded planning heuristics, such as pattern database heuristics (PDB) can be formulated in a lifted setting, such that our resulting heuristics provide strong guidance while being efficient to compute. Enabling good lifted PDB heuristics in particular, is crucial to promote future research in heuristic search for lifted optimal planning.