Lagrangian Decomposition for Classical Planning (Extended Abstract)

Florian Pommerening, Gabriele Röger, Malte Helmert, Hadrien Cambazard, Louis-Martin Rousseau, Domenico SalvagninIJCAI 2020 · DOI

TL;DR

This paper introduces Lagrangian decomposition as an efficient method for computing optimal cost partitioning of operator-counting heuristics in classical AI planning. By reformulating the problem as an iterative process, they significantly reduce the computational cost compared to solving large linear programs, enabling faster and more scalable heuristic computation.

What Problem Does This Paper Address?

Classical AI planning aims to find the cheapest sequence of actions to reach a goal state. Heuristics are crucial for guiding search algorithms like A* to find optimal plans efficiently. While combining multiple admissible heuristics (like pattern database heuristics) can improve performance, simply taking their maximum often results in a weak heuristic. Cost partitioning offers a way to combine heuristics by splitting their costs, leading to stronger admissible heuristics. However, computing the optimal cost partitioning typically involves solving a large linear program (LP), which can be computationally prohibitive, especially when dealing with many component heuristics. Operator-counting heuristics, while more compact than their cost partitioning counterparts, still require solving LPs that can be too expensive. This paper addresses the challenge of efficiently computing optimal cost partitioning for these operator-counting heuristics.

Methods

The core contribution of this paper is the application of Lagrangian decomposition to the problem of optimal cost partitioning for operator-counting heuristics. Lagrangian decomposition is a technique from mathematical programming that breaks down a large LP with a block structure into smaller, independent subproblems.

Here's how it applies:

  • Operator-Counting Heuristics as LPs: The paper first frames operator-counting heuristics as linear programs. Each constraint in the LP corresponds to a component heuristic, and variables represent how often each operator is used.
  • Lagrangian Decomposition: They then apply Lagrangian decomposition to the LP that combines multiple operator-counting heuristics. This splits the problem into subproblems, each associated with a "Lagrangian multiplier."
  • Interpretation of Multipliers: Crucially, the paper shows that these Lagrangian multipliers correspond to cost functions for the individual component heuristics. This means the decomposition naturally leads to a cost partitioning.
  • Iterative Improvement: The process becomes an iterative one. Starting with an initial cost partitioning, the algorithm repeatedly solves the subproblems (which are essentially finding optimal plans under modified costs) and uses the solutions to update the Lagrangian multipliers (cost functions). This is akin to a subgradient optimization method.
  • Specialization for Abstraction Heuristics: For non-negative cost partitioning of abstraction heuristics, they demonstrate a specialization that avoids the need for an LP solver altogether. Instead, it relies on solving shortest path problems in abstract state spaces, making it significantly more efficient.

Datasets

Not discussed in the paper. The experiments were conducted on instances from the international planning competitions (IPC 1998–2018), specifically using projections to 1 or 2 variables relevant to non-negative cost partitioning.

Key Insights and Ideas

  • Lagrangian Multipliers as Cost Partitions: The most significant insight is the direct correspondence between Lagrangian multipliers in the decomposed LP and the cost functions used in cost partitioning. This provides a powerful theoretical link.
  • Iterative Optimization is Efficient: The paper demonstrates that an iterative approach (subgradient optimization) can effectively find near-optimal or optimal cost partitions without solving a single monolithic LP. This is a major computational advantage.
  • LP Solver Avoidance for Abstraction Heuristics: The specialization for non-negative cost partitioning of abstraction heuristics is a key practical breakthrough. By replacing LP solving with shortest path computations, they achieve substantial speedups.
  • Anytime Algorithm: The subgradient method naturally yields an "anytime" algorithm. This means that at any point during its execution, the algorithm can be stopped, and it will provide a valid (though potentially suboptimal) cost partitioning and heuristic.

Key Results

  • Significant Speedup: The proposed method, especially the specialization for abstraction heuristics, is shown to be 10–200 times faster than using an LP solver for computing optimal cost partitioning.
  • Improved Heuristic Quality: The subgradient algorithm consistently improves heuristic quality over time, often reaching at least 90% of the optimal cost partitioning quality within the first 200 iterations.
  • Scalability: The method is more scalable than monolithic LP approaches, particularly for instances with many component heuristics. In some cases, the monolithic LP exceeded resource limits, while the subgradient method could still compute a value.
  • Comparison of Seeding Methods: Experiments showed that while starting from a better initial cost partitioning (seed) generally leads to better results, even suboptimal seeds can be improved to high quality.

Limitations and Future Work

  • Convergence Speed: While the subgradient method guarantees convergence, it can take many iterations to reach high accuracy, especially in domains with high action costs. The paper suggests that more elaborate choices for gradient and step length could improve convergence speed.
  • LP Solver Overhead: The paper notes that for very small abstract state spaces, the overhead of an LP solver can be high, reinforcing the value of the LP-free specialization.
  • Future Work: The authors suggest exploring more sophisticated optimization techniques from nondifferentiable optimization literature to further enhance convergence speed and performance. They also hint at rich possibilities for extensions based on this framework.

Summary updated

BibTeX
@inproceedings{pommerening2020lagrangian,
  author = {Florian Pommerening and Gabriele Röger and Malte Helmert and Hadrien Cambazard and Louis-Martin Rousseau and Domenico Salvagnin},
  title = {{Lagrangian Decomposition for Classical Planning (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/663},
}
Figure