Incremental LM-Cut

Pommerening, Florian and Helmert, Malte. (2013) Incremental LM-Cut. In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013) : [held 10 - 14 June 2013 in Rome, Italy]. Palo Alto, Calif., pp. 162-170.

[img] PDF - Published Version

Official URL: http://edoc.unibas.ch/dok/A6212202

Downloads: Statistics Overview


In heuristic search and especially in optimal classical planning the computation of accurate heuristic values can take up the majority of runtime. In many cases, the heuristic computations for a search node and its successors are very similar, leading to significant duplication of effort. For example most landmarks of a node that are computed by the LM-cut algorithm are also landmarks for the node's successors. We propose to reuse these landmarks and incrementally compute new ones to speed up the LM-cut calculation. The speed advantage obtained by incremental computation is offset by higher memory usage. We investigate different search algorithms that reduce memory usage without sacrificing the faster computation, leading to a substantial increase in coverage for benchmark domains from the International Planning Competitions.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Pommerening, Florian and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:16 Oct 2018 15:58
Deposited On:23 May 2014 08:34

Repository Staff Only: item control page