Exploiting Cyclic Dependencies in Landmark Heuristics
Keywords:Classical Planning Techniques And Analysis
AbstractLandmarks 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. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15948