@Misc{Lauer2025Code,
  author    = {Pascal Lauer and {\'A}lvaro Torralba and Daniel H{\"o}ller and J{\"o}rg Hoffmann},
	title     = {Code and Appendix for paper:  ``Continuing the Quest for Polynomial Time Heuristics in PDDL Input Size: Tractable Cases for Lifted hAdd"},
	year      = {2025},
	doi       = {10.5281/zenodo.15323404},
	publisher = {Zenodo}
}

@inproceedings{Lauer2025PotentialHeuristics,
  author    = {Pascal Lauer and Daniel Fi{\v{s}}er},
  booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling (ICAPS 2025)},
  publisher = {AAAI Press},
  title     = {Potential Heuristics: Weakening Consistency Constraints},
  year      = {2025},
  publisher = {AAAI Press}
}

@inproceedings{Lauer2025LiftedHeuristics,
    author    = {Pascal Lauer and {\'A}lvaro Torralba and Daniel H{\"o}ller and J{\"o}rg Hoffmann},
    booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling (ICAPS 2025)},
    publisher = {AAAI Press},
    title     = {Continuing the Quest for Polynomial Time Heuristics in PDDL Input Size: Tractable Cases for Lifted},
    year      = {2025}
}

@InProceedings{Lauer2025LiftedHTNVerification,
  author    = {Pascal Lauer and Songtuan Lin and Pascal Bercher},
  booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling ({ICAPS 2025})},
  title     = {Tight Bounds for Lifted HTN Plan Verification and Bounded Plan Existence},
  year      = {2025},
  publisher = {AAAI Press},
  abstract  = {Plan verification is a canonical problem within any planning setting, to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation.},
  keywords  = {conference,DECRA}
}

Plan verification is a canonical problem within any planning setting, to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation.

@inproceedings{Lauer2024LiftedhAdd,
    author               = {Pascal Lauer and {\'{A}}lvaro Torralba and Daniel H{\"{o}}ller and J{\"{o}}rg Hoffmann},
    booktitle            = {Proceedings of the 16th Workshop on Heuristic Search for Domain-Independent Planning (HSDIP 2024)},
    note                 = {<i>This paper is the workshop version of Lauer et al. in ICAPS 2025. Please refer to the conference version instead.</i>},
    title                = {A Lifted Backward Computation of hAdd},
    url_Paper            = {https://icaps24.icaps-conference.org/program/workshops/hsdip-papers/paper_9.pdf},
   Xurl_Slides           = {talks/hsdip-2024.pdf},
   Xurl_Technical_Report = {manuscripts/hsdip2024-tr.pdf},
    year                 = {2024},
    abstract             = {Recent interest in solving planning tasks where full grounding is infeasible has brought attention to how to compute heuristics to guide the search at a lifted level. h add is a well understood heuristic for classical planning. Methods to compute h add perform a forward fix-point computation, as this takes polynomial time with respect to the grounded representation. However, this computational efficiency does not carry over to lifted planning tasks, where it is EXPTIME-complete to compute hadd. In this paper, we introduce a novel approach for computing h add on lifted planning tasks. Our approach proceeds backwards, constructing a fully lifted regression graph whose nodes are assessed using conjunctive query evaluation. We provide a complexity analysis and show that our backward computation is complementary to the traditional forward computation. Our empirical evaluation confirms that there are significant differences in the performance of both methods in each domain. Overall, both methods are very complementary, and their combination advances the state-of-the-art in lifted h add computations.}
}

Recent interest in solving planning tasks where full grounding is infeasible has brought attention to how to compute heuristics to guide the search at a lifted level. h add is a well understood heuristic for classical planning. Methods to compute h add perform a forward fix-point computation, as this takes polynomial time with respect to the grounded representation. However, this computational efficiency does not carry over to lifted planning tasks, where it is EXPTIME-complete to compute hadd. In this paper, we introduce a novel approach for computing h add on lifted planning tasks. Our approach proceeds backwards, constructing a fully lifted regression graph whose nodes are assessed using conjunctive query evaluation. We provide a complexity analysis and show that our backward computation is complementary to the traditional forward computation. Our empirical evaluation confirms that there are significant differences in the performance of both methods in each domain. Overall, both methods are very complementary, and their combination advances the state-of-the-art in lifted h add computations.

@inproceedings{Lauer2021FeasibleDelRelax,
   title     = {Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning},
   author    = {Pascal Lauer and Alvaro Torralba and Daniel Fiser and Daniel H\"{o}ller and Julia Wichlacz and Joerg Hoffmann},
   year      = {2021},
   booktitle = {Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)},
   pages     = {4119--4126},
   doi       = {10.24963/ijcai.2021/567},
   publisher = {IJCAI},
   url_Paper = {https://fai.cs.uni-saarland.de/wichlacz/papers/polynomial_time_in_pddl_input.pdf},
   url_video_of_presentation = {https://www.youtube.com/watch?v=ZqjXqMBM7KEI},
   url_Code  = {https://zenodo.org/record/4768791#.Y2qxmuzMLuU},
   abstract = {Polynomial-time heuristic functions for planning are commonplace since 20 years. But polynomial-time in which input? Almost all existing approaches are based on a grounded task representation, not on the actual PDDL input which is exponentially smaller. This limits practical applicability to cases where the grounded representation is “small enough”. Previous attempts to tackle this problem for the delete relaxation leveraged symmetries to reduce the blow-up. Here we take a more radical approach, applying an additional relaxation to obtain a heuristic function that runs in time polynomial in the size of the PDDL input. Our relaxation splits the predicates into smaller predicates of fixed arity K. We show that computing a relaxed plan is still NP-hard (in PDDL input size) for K ≥ 2, but is polynomial-time for K = 1. We implement a heuristic function for K = 1 and show that it can improve the state of the art on benchmarks whose grounded representation is large.}
}

Polynomial-time heuristic functions for planning are commonplace since 20 years. But polynomial-time in which input? Almost all existing approaches are based on a grounded task representation, not on the actual PDDL input which is exponentially smaller. This limits practical applicability to cases where the grounded representation is “small enough”. Previous attempts to tackle this problem for the delete relaxation leveraged symmetries to reduce the blow-up. Here we take a more radical approach, applying an additional relaxation to obtain a heuristic function that runs in time polynomial in the size of the PDDL input. Our relaxation splits the predicates into smaller predicates of fixed arity K. We show that computing a relaxed plan is still NP-hard (in PDDL input size) for K ≥ 2, but is polynomial-time for K = 1. We implement a heuristic function for K = 1 and show that it can improve the state of the art on benchmarks whose grounded representation is large.

@Misc{Lauer2021FeasibleDelRelaxCode,
   author    = {Pascal Lauer and {\'A}lvaro Torralba and Daniel Fi\v{s}er and Daniel H{\"o}ller and Julia Wichlacz and J{\"o}rg Hoffmann},
   title     = {Code and benchmarks from the paper ``Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning''},
   year      = {2021},
   doi       = {10.5281/zenodo.4768790},
   publisher = {Zenodo}
}

@inproceedings{Lauer2020LMCut,
  title     = {Beating LM-cut with LM-cut: Quick Cutting and Practical Tie Breaking for the Precondition Choice Function},
  author    = {Pascal Lauer and Maximilian Fickert},
  booktitle = {Proceedings of the 12th Workshop on Heuristics and Search for Domain-independent Planning (HSDIP 2020)},
  year      = {2020},
  url_Paper_PDF = {https://icaps20subpages.icaps-conference.org/wp-content/uploads/2020/10/proceedings.pdf#page=13},
  url_Video_of_Presentation = {https://www.youtube.com/watch?v=n03g6Y6zJWI},
  pages      = {9--15},
  abstract   = {LM-cut is one of the most popular heuristics in optimal planning that computes strong admissible estimates of the perfect delete relaxation heuristic h+. The heuristic iteratively computes disjunctive action landmarks for the current state, reducing their action costs until no more landmarks with remaining action costs can be found. These landmarks are generated by finding cuts in the justification graph, which depends on a precondition choice function mapping each action to its most expensive precondition according to hmax. This precondition is not necessarily unique, yet the performance of the heuristic heavily depends on this choice. We introduce and analyze several new tie breaking strategies for the precondition choice function, and evaluate their effectiveness on the IPC benchmarks. Furthermore, we suggest a modification to the computation of the cut, which trades a negligible loss in heuristic accuracy for a significant speedup of the LM-cut computation.}
}

LM-cut is one of the most popular heuristics in optimal planning that computes strong admissible estimates of the perfect delete relaxation heuristic h+. The heuristic iteratively computes disjunctive action landmarks for the current state, reducing their action costs until no more landmarks with remaining action costs can be found. These landmarks are generated by finding cuts in the justification graph, which depends on a precondition choice function mapping each action to its most expensive precondition according to hmax. This precondition is not necessarily unique, yet the performance of the heuristic heavily depends on this choice. We introduce and analyze several new tie breaking strategies for the precondition choice function, and evaluate their effectiveness on the IPC benchmarks. Furthermore, we suggest a modification to the computation of the cut, which trades a negligible loss in heuristic accuracy for a significant speedup of the LM-cut computation.

@article{Gros2019Amazeing,
  title     = {aMAZEing Programming-Providing SKILLs to Fellow Students},
  author    = {Timo P. Gros and Pascal L. Held and Pascal Lauer and Niklas O. Metzger and Kallistos Weis},
  journal   = {SKILL 2019-Studierendenkonferenz Informatik},
  year      = {2019},
  publisher = {Gesellschaft f{\"u}r Informatik e.V.}
}