Exploiting Cyclic Dependencies in Landmark Heuristics


  • Clemens Büchner University of Basel
  • Thomas Keller University of Basel
  • Malte Helmert University of Basel




Classical Planning Techniques And Analysis


Landmarks of a planning task denote properties that must be satisfied by all plans. Existing landmark heuristics exploit that each landmark must be achieved at least once. However, if the orderings between the landmarks induce cyclic dependencies, one of the landmarks in each cycle must be achieved an additional time. We propose two novel heuristics for cost-optimal planning that consider cyclic dependencies between landmarks in addition to the cost for achieving all landmarks once. We show that our heuristics dominate the minimum hitting set solution over any set of landmarks as well as h+ if all delete-relaxation landmarks are considered. An experimental evaluation on benchmarks from the International Planning Competition shows that exploiting cyclic dependencies can lead to improved heuristics.




How to Cite

Büchner, C., Keller, T., & Helmert, M. (2021). Exploiting Cyclic Dependencies in Landmark Heuristics. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 65-73. https://doi.org/10.1609/icaps.v31i1.15948