Landmark Progression in Heuristic Search

Authors

  • Clemens Büchner University of Basel
  • Thomas Keller University of Basel University of Zürich
  • Salomé Eriksson University of Basel
  • Malte Helmert University of Basel

DOI:

https://doi.org/10.1609/icaps.v33i1.27180

Keywords:

Classical planning techniques and analysis, Heuristic search

Abstract

The computation of high-quality landmarks and orderings for heuristic state-space search is often prohibitively expensive to be performed in every generated state. Computing information only for the initial state and progressing it from every state to its successors is a successful alternative, exploited for example in classical planning by the LAMA planner. We propose a general framework for using landmarks in any kind of best-first search. Its core component, the progression function, uses orderings and search history to determine which landmarks must still be achieved. We show that the progression function that is used in LAMA infers invalid information in the presence of reasonable orderings. We define a sound progression function that allows to exploit reasonable orderings in cost-optimal planning and show empirically that our new progression function is beneficial both in satisficing and optimal planning.

Downloads

Published

2023-07-01

How to Cite

Büchner, C., Keller, T., Eriksson, S., & Helmert, M. (2023). Landmark Progression in Heuristic Search. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 70-79. https://doi.org/10.1609/icaps.v33i1.27180