Lagrangian Decomposition for Classical Planning (Extended Abstract)

Florian Pommerening, Gabriele Röger, Malte Helmert, Hadrien Cambazard, Louis-Martin Rousseau, Domenico Salvagnin

IJCAI 2020 pp. 4770-4774

doi:10.24963/IJCAI.2020/663 /ijcai/2020/pommerening2020ijcai-lagrangian/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Pommerening et al. "Lagrangian Decomposition for Classical Planning (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/663

Markdown

[Pommerening et al. "Lagrangian Decomposition for Classical Planning (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/pommerening2020ijcai-lagrangian/) doi:10.24963/IJCAI.2020/663

BibTeX

@inproceedings{pommerening2020ijcai-lagrangian,
  title     = {{Lagrangian Decomposition for Classical Planning (Extended Abstract)}},
  author    = {Pommerening, Florian and Röger, Gabriele and Helmert, Malte and Cambazard, Hadrien and Rousseau, Louis-Martin and Salvagnin, Domenico},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {4770-4774},
  doi       = {10.24963/IJCAI.2020/663},
  url       = {https://mlanthology.org/ijcai/2020/pommerening2020ijcai-lagrangian/}
}