Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Helmert, Malte; Domshlak, Carmel License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24324


Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?



Current heuristic estimators for classical domain-independent planning are usually based on one of four ideas: delete relaxation, abstraction, critical paths, and, most recently, landmarks. Previously, these different ideas for deriving heuristic functions were largely unconnected. In my talk, I will show that these heuristics are in fact very closely related. Moreover, I will introduce a new admissible heuristic called the landmark cut heuristic which exploits this relationship. In our experiments, the landmark cut heuristic provides better estimates than other current admissible planning heuristics, especially on large problem instances.

BibTeX - Entry

  author =	{Malte Helmert and Carmel Domshlak},
  title =	{Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?},
  booktitle =	{Graph Search Engineering},
  year =	{2010},
  editor =	{Lubos Brim and Stefan Edelkamp and Erik A. Hansen and Peter Sanders},
  number =	{09491},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Planning, heuristic search, heuristic functions}

Keywords: Planning, heuristic search, heuristic functions
Seminar: 09491 - Graph Search Engineering
Issue date: 2010
Date of publication: 02.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI