Exploiting Cyclic Dependencies in Landmark Heuristics

Büchner, Clemens and Keller, Thomas and Helmert, Malte. (2021) Exploiting Cyclic Dependencies in Landmark Heuristics. In: Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), 31. pp. 65-73.

[img] PDF - Accepted Version

Official URL: https://edoc.unibas.ch/84308/

Downloads: Statistics Overview


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.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Büchner, Clemens and Keller, Thomas and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
edoc DOI:
Last Modified:24 Feb 2022 09:29
Deposited On:30 Aug 2021 09:24

Repository Staff Only: item control page