Lagrangian Decomposition for Classical Planning (Extended Abstract)
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Sister Conferences Best Papers. Pages 4770-4774. https://doi.org/10.24963/ijcai.2020/663
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.
Planning and Scheduling: Search in Planning and Scheduling
Planning and Scheduling: Theoretical Foundations of Planning
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Combinatorial Search and Optimisation