Landmark Progression in Heuristic Search

Büchner, Clemens and Keller, Thomas and Eriksson, Salomé and Helmert, Malte. (2023) Landmark Progression in Heuristic Search. In: Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023), 33. pp. 70-79.

[img] PDF - Accepted Version

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

Downloads: Statistics Overview


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.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Büchner, Clemens and Keller, Thomas and Eriksson, Salomé and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Series Name:Proceedings of the International Conference on Automated Planning and Scheduling
Issue Number:1
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:25 Sep 2023 08:15
Deposited On:22 Sep 2023 12:35

Repository Staff Only: item control page