On Weak Stubborn Sets in Classical Planning

Silvan Sievers, Martin WehrleIJCAI 2021 · DOI

TL;DR

This paper revisits the concept of "weak stubborn sets" in classical AI planning, demonstrating that previously proposed methods don't align with the original formal definition. The authors introduce a new, generalized definition of weak stubborn sets that better captures the original intent, leading to potentially more effective pruning strategies in planning search.

What Problem Does This Paper Address?

Classical AI planning aims to find a sequence of actions (a plan) to transform an initial state into a goal state. The search space for these plans can be astronomically large, making efficient search crucial. "Stubborn sets" are a family of techniques designed to prune this search space by identifying sets of actions that are essential for finding an optimal plan. While "strong stubborn sets" have been well-studied, "weak stubborn sets" have received less attention. This paper highlights a discrepancy: recent work has proposed methods labeled "weak stubborn sets" that, according to the authors, don't adhere to the formal definition of weak stubborn sets established by Valmari in 1989. This ambiguity hinders a clear understanding and consistent application of these pruning techniques. The paper aims to resolve this by re-establishing a formal definition of weak stubborn sets for classical planning and exploring its relationship with other stubborn set variants.

Methods

The core of the paper involves:

  • Revisiting and Formalizing Definitions: The authors meticulously re-examine the definitions of interference (weak and strong) and disabling between operators, which are foundational to stubborn sets. They then introduce a new definition for "generalized weak stubborn sets" (GWSS). This definition is analogous to generalized strong stubborn sets (GSSS) previously proposed, but crucially incorporates a relaxed condition for applicable operators.
  • Introducing the "Operator Shifting Property": To better characterize the behavior of pruning techniques, the authors define the "operator shifting property." This property ensures that an operator identified by the pruning technique can be "shifted" to the beginning of a plan without invalidating it, and remains applicable in intermediate states. They show that traditional stubborn sets and GSSS satisfy this property, but previously proposed "weak stubborn sets" (which they rename "compliant stubborn sets" or CSS) do not.
  • Defining Generalized Weak Stubborn Sets (GWSS): The GWSS definition extends the GSSS framework by modifying condition C4. Instead of requiring all interfering operators, GWSS require operators that weakly interfere with applicable operators, or alternatively, all enablers or disablers of specific precondition facts. This choice between enablers and disablers is a key distinction from GSSS and aligns with Valmari's original concept of weak stubborn sets.
  • Theoretical Analysis: The paper provides proofs demonstrating that GWSS are safe pruning functions and that they satisfy the operator shifting property. They also prove that GWSS and CSS are incomparable in their pruning power, meaning neither strictly dominates the other.

Datasets

The paper uses standard planning benchmarks from the International Planning Competitions (IPCs) from 1998 to 2018, comprising 1827 tasks across 65 domains. No new datasets were introduced.

Key Insights and Ideas

  • "Weak Stubborn Sets" Were Misinterpreted: A significant finding is that recent methods labeled "weak stubborn sets" in the literature do not actually conform to Valmari's original formal definition. This clarifies a point of confusion in the field.
  • The Power of Choice: Enablers vs. Disablers: The introduction of GWSS highlights the strategic advantage of allowing a choice between including "enablers" or "disablers" of operator preconditions. This flexibility, absent in GSSS, is key to achieving potentially greater pruning.
  • Orthogonal Pruning Power: The paper establishes that GWSS and CSS have "orthogonal pruning power." This means that while both are effective pruning techniques, they excel in different scenarios, and neither is universally superior. This suggests that the choice of pruning technique might depend on the specific characteristics of the planning problem.
  • Operator Shifting Property as a Key Differentiator: The operator shifting property proves to be a crucial concept for understanding the theoretical guarantees of stubborn set variants. Its absence in CSS explains why they might offer less predictable behavior compared to GWSS.

Key Results

  • Formal Definition of GWSS: The paper provides a precise, generalized definition of weak stubborn sets for classical planning.
  • Theoretical Guarantees: GWSS are proven to be safe pruning functions, meaning they do not discard optimal solutions. They also satisfy the operator shifting property.
  • Incomparability of GWSS and CSS: Theoretical proofs demonstrate that GWSS and CSS have incomparable pruning power.
  • Empirical Validation: Experiments on IPC benchmarks show that GWSS generally achieve more pruning than GSSS. The comparison between GWSS and CSS also confirms their orthogonal pruning power, with GWSS often showing a slight advantage.

Limitations and Future Work

  • Syntactic vs. Semantic Interference: The paper notes that while GWSS are defined using semantic (state-based) interference, practical implementations often rely on syntactic approximations (like mutexes). The paper's evaluation uses mutex-based interference for GSSS and GWSS to allow for a fair comparison, but acknowledges that this might limit the full potential of GWSS.
  • Operator Shifting Property Relaxation: The authors suggest that further research could explore relaxing the operator shifting property even more, potentially leading to more powerful pruning techniques. This could involve identifying situations where operators that disable others might be safely excluded from the pruning set.
  • Investigating Enabler/Disabler Choice: The paper hints that more sophisticated strategies for deciding when to include all enablers or disablers could further enhance pruning power.

Summary updated

BibTeX
@inproceedings{sievers2021weak,
  author = {Silvan Sievers and Martin Wehrle},
  title = {{On Weak Stubborn Sets in Classical Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/573},
}
Figure