DROPS

Document

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

Authors: Malte Helmert and Carmel Domshlak

Published in: Dagstuhl Seminar Proceedings, Volume 9491, Graph Search Engineering (2010)

Abstract

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.

Cite as

Malte Helmert and Carmel Domshlak. Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?. In Graph Search Engineering. Dagstuhl Seminar Proceedings, Volume 9491, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{helmert_et_al:DagSemProc.09491.3,
  author =	{Helmert, Malte and Domshlak, Carmel},
  title =	{{Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?}},
  booktitle =	{Graph Search Engineering},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9491},
  editor =	{Lubos Brim and Stefan Edelkamp and Erik A. Hansen and Peter Sanders},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09491.3},
  URN =		{urn:nbn:de:0030-drops-24324},
  doi =		{10.4230/DagSemProc.09491.3},
  annote =	{Keywords: Planning, heuristic search, heuristic functions}
}

Search Results

Documents authored by Helmert, Malte

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

Abstract

Cite as

Thanks for your feedback!

Could not send message