Cost-Partitioned Merge-and-Shrink Heuristics for Optimal Classical Planning

Silvan Sievers, Florian Pommerening, Thomas Keller, Malte HelmertIJCAI 2020 · DOI

TL;DR

This paper tackles the challenge of combining multiple heuristic functions in classical AI planning to achieve better performance. They introduce a novel method to integrate "cost partitioning" techniques with "merge-and-shrink" (M&S) abstractions, showing that this combination significantly improves the efficiency of optimal planners on standard benchmarks.

What Problem Does This Paper Address?

Optimal classical planning aims to find the shortest sequence of actions to reach a goal state from an initial state. A common approach uses heuristic functions to estimate the cost to reach the goal, guiding search algorithms like A*. However, individual heuristic functions often only capture part of the problem's complexity. Combining multiple heuristics can lead to better estimates, but doing so admissibly (guaranteeing optimality) is tricky. "Cost partitioning" is a technique to combine admissible heuristics by distributing operator costs among them. "Merge-and-shrink" (M&S) is a powerful framework for generating abstract heuristic functions. While cost partitioning has been successfully applied to other types of abstractions, its integration with M&S has been an open problem. This paper bridges this gap by extending cost partitioning to M&S abstractions.

Methods

The core contribution is the adaptation of cost partitioning concepts, specifically "optimal cost partitioning" (OCP) and "saturated cost partitioning" (SCP), to the merge-and-shrink (M&S) framework.

  • Label Cost Partitioning: They generalize operator cost partitioning to "label cost partitioning," which applies to the labels (actions) within M&S factors, even when these labels don't directly correspond to original operators after M&S transformations.
  • Interaction Analysis: The paper theoretically analyzes how standard M&S transformations (merging, shrinking, label reduction) affect the quality of OCP and SCP heuristics. They prove that merging can improve OCP, while shrinking and label reduction can sometimes decrease it, though exact label reduction and bisimulation shrinking preserve OCP values. For SCP, the interaction is more complex, with transformations potentially leading to incomparable heuristic values.
  • Interleaved SCP Computation: A practical approach is proposed where SCP heuristics are computed during the M&S process, not just at the end. This involves taking "snapshots" of the M&S factors at various stages and computing SCPs over them. This interleaved approach aims to leverage the benefits of cost partitioning on intermediate, potentially more informative, abstractions.
  • Offline SCP Computation: An alternative "offline" approach is also discussed, where factor heuristics from different M&S stages are stored and later combined using SCP.

Datasets

The experiments were conducted on tasks from all optimal tracks of all International Planning Competitions, comprising 1827 tasks across 65 domains. No new benchmarks were introduced.

Key Insights and Ideas

  • M&S + Cost Partitioning is Powerful: The most significant insight is that combining M&S abstractions with cost partitioning (especially SCP) leads to substantially better heuristic values than using M&S abstractions alone (maximized over factors) or even OCP in some cases. This suggests that the structure of M&S abstractions is particularly well-suited for cost partitioning.
  • Interleaving is Key: Computing SCPs during the M&S process, rather than just at the end, is crucial for achieving significant performance gains. This allows for leveraging cost partitioning on intermediate abstractions that might be more informative than the final, highly compressed one.
  • Random Order Surprises: Surprisingly, a simple random order for computing SCPs in the interleaved approach performed best among various tested strategies, including more sophisticated greedy orders. This suggests that diversification of orders is more important than the specific strategy for this combined M&S-SCP approach.
  • Exact Transformations Preserve OCP: The theoretical analysis reveals that certain M&S transformations, when performed "exactly" (e.g., exact label reduction, bisimulation shrinking), preserve the quality of OCP heuristics, providing a theoretical foundation for their use.

Key Results

  • Improved Coverage: The interleaved SCP approach significantly improves the coverage of optimal planners compared to standard M&S heuristics. For example, one configuration achieved a coverage of 933 tasks where standard M&S solved 905.
  • SCP Outperforms Max: Combining M&S factors with SCP consistently outperformed simply maximizing the factor heuristics (hM&S).
  • SCP vs. OCP: SCP heuristics were found to be competitive with OCP heuristics, often achieving similar performance but being computationally much more feasible, especially for large abstractions.
  • Interleaved vs. Offline: The interleaved approach generally outperformed the offline approach, particularly when using a random order for SCP computation.

Limitations and Future Work

  • OCP Scalability: The paper acknowledges that computing OCPs over large abstractions is often infeasible, which is why they focus on SCP for their practical implementation.
  • Order Strategies for SCP: While a random order performed best in experiments, the authors suggest further work on investigating better order strategies for SCPs within the M&S framework.
  • Formalizing Cost Partitioning as M&S Transformation: The paper proposes formalizing cost partitioning itself as a transformation within the M&S framework as a future research direction.
  • Memory Efficiency: The use of "shallow copies" for factored state mappings was crucial for memory efficiency, but further exploration of memory management in M&S could be beneficial.

Summary updated

BibTeX
@inproceedings{sievers2020cost,
  author = {Silvan Sievers and Florian Pommerening and Thomas Keller and Malte Helmert},
  title = {{Cost-Partitioned Merge-and-Shrink Heuristics for Optimal Classical Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/574},
}
Figure