Operator Mutexes and Symmetries for Simplifying Planning Tasks

Daniel Fiser, Álvaro Torralba, Alexander ShleyfmanAAAI 2019 · DOI

TL;DR

This paper introduces "operator mutexes" – sets of operators that cannot all appear in the same optimal plan – and demonstrates how they can be used with structural symmetries to safely remove redundant operators from planning tasks. This simplification can significantly speed up planning by reducing the search space, offering a novel approach to task preprocessing.

What Problem Does This Paper Address?

Classical AI planning systems often struggle with large, complex tasks. While many techniques exist to optimize planners, a key challenge is simplifying the planning task itself before planning begins. This paper tackles the problem of identifying and removing "redundant" operators – those whose removal doesn't prevent finding at least one optimal plan. The authors propose a novel way to achieve this by identifying operator mutexes and leveraging symmetries within the planning task's structure.

Methods

The core of the paper revolves around two main concepts:

  • Operator Mutexes (Op-Mutexes): The authors define a "strong operator mutex" as a set of operators that cannot all be present in any strongly optimal plan (an optimal plan with the minimum number of operators). They propose several methods to infer these op-mutexes:
  • Abstractions: Using abstract versions of the planning task to detect operators that are mutually exclusive in the abstract state space.
  • Operators-as-Facts Compilation: Transforming the problem by creating a new fact for each operator, allowing existing fact-mutex inference techniques to be applied to find operator mutexes.
  • Critical-Path Heuristics: Adapting existing heuristic computation methods to identify operators that are unlikely to be reachable together.
  • Operators with Irreversible Add Effects: Identifying operators that add facts which cannot be deleted by any operator, and grouping operators with identical irreversible add effects as mutexes.
  • Symmetries: The paper leverages symmetries in the planning task's transition system. A symmetry is essentially a permutation of states and actions that preserves the task's structure. The key insight is that if a set of operators forms an op-mutex, and there's a symmetry that maps one part of the mutex to another, then one of those sets of operators can be safely removed. They also propose a fixpoint computation algorithm (Algorithm 1) that iteratively identifies and removes redundant operators while trying to preserve existing symmetries, which can help discover more redundancies in subsequent steps.

Datasets

The authors evaluated their methods on the International Planning Competition (IPC) benchmarks from 2006-2018, specifically the optimal track. They note that they compiled away conditional effects and grounding to fit their STRIPS-based approach.

Key Insights and Ideas

  • Op-mutexes are a powerful tool for redundancy: The core idea that a set of operators being mutually exclusive in strongly optimal plans directly implies that at least one operator in that set is redundant is a key insight.
  • Symmetries amplify redundancy detection: Simply finding op-mutexes isn't enough; symmetries are crucial for identifying which operators can be safely removed. If a symmetry maps operators from one side of a mutex to the other, it provides a strong signal for removal.
  • Preserving symmetries is beneficial for iterative pruning: The proposed fixpoint algorithm's strategy of preserving symmetries in each pruning step is motivated by the observation that this can lead to the discovery of more redundant operators over time.
  • Different inference methods have varying strengths: The experimental results highlight that different op-mutex inference methods (fam, Пр, 2-h², iadd) excel in different domains and offer varying trade-offs between the number of mutexes found and computational cost.

Key Results

  • Significant Op-Mutex Discovery: The methods successfully inferred a substantial number of op-mutex pairs across many domains (34 out of 83 tested) within reasonable time limits (5 minutes).
  • Operator Reduction: Combining op-mutexes with symmetries and the proposed fixpoint algorithm led to significant reductions in the number of operators in several domains (e.g., childsnack, agricola, trucks, barman).
  • Пp Method Dominance: The Пp method (based on h² reachability analysis of the op-fact compilation) generally found the most op-mutexes and contributed to the best operator reductions.
  • Limited Impact on Planner Performance (in this study): While operator reduction was significant, the paper notes that this reduction did not translate into substantial gains for the tested heuristic search planners, suggesting that further research is needed to bridge this gap.

Limitations and Future Work

  • Impact on Planner Performance: The authors acknowledge that the significant operator reduction achieved did not consistently lead to faster planning times for the tested planners. This suggests that the benefits of task simplification might be more pronounced for different types of planners or require further integration strategies.
  • NP-Hardness: Finding the maximal redundant set using Theorem 16 is NP-Hard, leading the authors to propose a greedy algorithm. Future work could explore more sophisticated methods for finding larger redundant sets.
  • Fixpoint Algorithm's Greedy Nature: The greedy selection steps in Algorithm 1 might not always find the globally optimal set of redundant operators.
  • Future Directions: The paper opens avenues for research on how to better leverage operator mutexes and symmetries to simplify planning tasks, potentially leading to more efficient planning systems. Further investigation into how task simplification impacts different planner architectures is also suggested.

Summary updated

BibTeX
@inproceedings{fiser2019operator,
  author = {Daniel Fiser and Álvaro Torralba and Alexander Shleyfman},
  title = {{Operator Mutexes and Symmetries for Simplifying Planning Tasks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017586},
}
Figure