Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning

Martin Wehrle, Malte Helmert, Alexander Shleyfman, Michael KatzIJCAI 2015

Abstract

State-space explosion remains a primary challenge in cost-optimal classical planning. This paper presents a novel integration of two prominent pruning techniques: Partial Order Reduction (POR) and Symmetry Elimination. By defining Symmetrical Strong Stubborn Sets (SSSS), the authors provide a framework that leverages the orthogonal strengths of both methods. Experimental evaluation on International Planning Competition (IPC) benchmarks demonstrates that this integration significantly increases problem coverage and reduces state-space exploration, often by multiple orders of magnitude.

Introduction

In classical planning, the objective is to identify a sequence of actions that transitions an initial state to a goal state at minimum cost. Despite advancements in heuristic search, the exponential size of state spaces often renders problems intractable. Pruning techniques are essential to mitigate this. Partial Order Reduction (POR) identifies and ignores redundant action orderings, while Symmetry Elimination maps equivalent states to a single representative. While both are effective, their combined application has historically been under-explored. This paper investigates whether these techniques can be integrated safely to preserve optimality while enhancing pruning power.

Methods

The authors introduce two integration levels. The first, Direct Integration (o/s), applies Strong Stubborn Sets (SSS) to determine a subset of necessary actions and then uses Orbit Space Search (OSS) to map the resulting successors to their canonical forms. The second, Symmetrical Strong Stubborn Sets (SSSS), is a deeper integration where symmetries are incorporated directly into the stubborn set's fixed-point computation. By utilizing canonical operators, SSSS can identify symmetries even among actions that are not currently applicable, potentially leading to more aggressive pruning than the sequential approach.

Results and Discussion

The proposed methods were tested on 1,396 instances from 44 IPC domains using the LM-Cut heuristic. The direct integration (o/s) achieved a total coverage of 859 solved problems, a significant improvement over the 805 solved by SSS alone and 828 by OSS alone.

Table 1: Comparison of coverage and state expansions for various pruning configurations across IPC domains.

The synergy between POR and symmetry elimination is domain-dependent but often substantial. In domains like Gripper, symmetry elimination dominates, whereas POR is more effective in Parcprinter. The combined approach excels in both. Furthermore, the SSSS variant demonstrates the ability to reduce the number of expanded states by several orders of magnitude compared to standard SSS in many instances.

Figure 1: Scatter plot comparing state expansions of Symmetrical SSS against standard Strong Stubborn Sets (SSS).

Conclusion

The integration of POR and symmetry elimination represents a significant advancement in cost-optimal planning. The formal proofs provided ensure that these combined techniques remain "strongly safe," preserving the ability to find optimal solutions. While computational overhead for SSSS can be a limiting factor in some domains, the overall increase in coverage and state-space reduction underscores the value of combining these orthogonal pruning strategies. Future research will explore further coupling and applications in satisficing planning.

Summary updated

BibTeX
@inproceedings{wehrle2015integrating,
  author = {Martin Wehrle and Malte Helmert and Alexander Shleyfman and Michael Katz},
  title = {{Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure