Transition Landmarks from Abstraction Cuts


  • Florian Pommerening University of Basel, Switzerland
  • Clemens Büchner University of Basel, Switzerland
  • Thomas Keller University of Basel, Switzerland



We introduce transition-counting constraints as a principled tool to formalize constraints that must hold in every solution of a transition system. We then show how to obtain transition landmark constraints from abstraction cuts. Transition landmarks dominate operator landmarks in theory but require solving a linear program that is prohibitively large in practice. We compare different constraints that project away transition-counting variables and then further relax the constraint. For one important special case, we provide a lossless projection. We finally discuss efficient data structures to derive cuts from abstractions and store them in a way that avoids repeated computation in every state. We compare the resulting heuristics both theoretically and on benchmarks from the international planning competition.




How to Cite

Pommerening, F., Büchner, C., & Keller, T. (2024). Transition Landmarks from Abstraction Cuts. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 445-454.