Lagrangian Decomposition for Optimal Cost Partitioning

Pommerening, Florian and Röger, Gabriele and Helmert, Malte and Cambazard, Hadrien and Rousseau, Louis-Martin and Salvagnin, Domenico. (2019) Lagrangian Decomposition for Optimal Cost Partitioning. In: Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), 29. pp. 338-347.

[img] PDF - Accepted Version

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

Downloads: Statistics Overview


Optimal cost partitioning of classical planning heuristics has been shown to lead to excellent heuristic values but is often prohibitively expensive to compute. Lagrangian decomposition and Lagrangian relaxation are classical tools in mathematical programming that apply to optimization problems with a special block structure. We analyze the application of Lagrangian decomposition to cost partitioning in the context of operator-counting heuristics and interpret Lagrangian multipliers as cost functions for the combined heuristics. This allows us to view the computation of an optimal cost partitioning as an iterative process that can be seeded with any cost partitioning and improves over time. We derive an any-time algorithm to compute an optimal non-negative cost partitioning of abstraction heuristics without involving an LP solver. In each iteration, the computation reduces to independent shortest path problems in all abstractions. Finally, we discuss the extension to general cost functions.
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:03 Sep 2021 07:05
Deposited On:28 Jan 2020 10:17

Repository Staff Only: item control page