Lagrangian Decomposition for Classical Planning (Extended Abstract)

Pommerening, Florian and Röger, Gabriele and Helmert, Malte and Cambazard, Hadrien and Rousseau, Louis-Martin and Salvagnin, Domenico. (2020) Lagrangian Decomposition for Classical Planning (Extended Abstract). In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020). pp. 4770-4774.

[img] PDF - Accepted Version

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

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. We analyze the application of Lagrangian decomposition, a classical tool in mathematical programming, to cost partitioning of operator-counting heuristics. This allows us to view the computation as an iterative process that can be seeded with any cost partitioning and that improves over time. In the case of non-negative cost partitioning of abstraction heuristics the computation reduces to independent shortest path problems and does not require an LP solver.
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:International Joint Conferences on Artificial Intelligence
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
Identification Number:
edoc DOI:
Last Modified:29 Sep 2020 07:25
Deposited On:29 Sep 2020 07:25

Repository Staff Only: item control page