LP-based heuristics for cost-optimal planning

Pommerening, Florian and Röger, Gabriele and Helmert, Malte and Bonet, Blai. (2014) LP-based heuristics for cost-optimal planning. In: Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014): [held on June 21-26 in Portsmouth, New Hampshire, USA]. Palo Alto, Calif., pp. 226-234.

[img] PDF - Published Version

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

Downloads: Statistics Overview


Many heuristics for cost-optimal planning are based on linear programming. We cover several interesting heuristics of this type by a common framework that fixes the objective function of the linear program. Within the framework, constraints from different heuristics can be combined in one heuristic estimate which dominates the maximum of the component heuristics. Different heuristics of the framework can be compared on the basis of their constraints. With this new method of analysis, we show dominance of the recent LP-based state-equation heuristic over optimal cost partitioning on single-variable abstractions. We also show that the previously suggested extension of the state-equation heuristic to exploit safe variables cannot lead to an improved heuristic estimate. We experimentally evaluate the potential of the proposed framework on an extensive suite of benchmark tasks.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Pommerening, Florian and Röger, Gabriele 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 13:57
Deposited On:05 Jun 2015 08:52

Repository Staff Only: item control page