Revisiting Dominance Pruning in Decoupled Search

Daniel GnadAAAI 2021 · DOI

Introduction

Classical AI planning faces a fundamental challenge known as the state-explosion problem. As the number of variables in a planning task increases, the number of possible states grows exponentially, making exhaustive search infeasible for complex problems. Decoupled search offers a powerful alternative by partitioning a planning task into a "center" component and several "leaf" components that interact only through the center (a star topology). Instead of searching through individual explicit states, decoupled search operates on "decoupled states," each representing a set of explicit states.

The Bottleneck: Dominance Pruning

While decoupled search significantly reduces the state space, it introduces a new computational hurdle: dominance pruning. In standard search, duplicate pruning is straightforward—if a state has been visited, it is ignored. In decoupled search, because a node represents a set of states, the algorithm must determine if a newly reached set is "covered" or dominated by a previously visited one. Prior to this research, dominance checking was a major bottleneck, often accounting for up to 60% of total runtime and frequently failing to identify all possible pruning opportunities.

Advanced Pruning Methods

This paper introduces several algorithmic improvements to make dominance pruning both stronger (pruning more nodes) and faster (reducing computational overhead):

  1. All-Costs Dominance ($\preceq_G$): Previous methods checked path costs ($g$-values) and leaf state prices independently. The new $\preceq_G$ relation allows for cost "trading." If a new state is more expensive in one leaf but significantly cheaper in another or has a lower center cost, the algorithm can now recognize it as dominated.
  2. g-Value Adaptation: This transformation moves the minimum cost required to reach leaf states into the center's $g$-value. This "unhides" costs, providing better guidance for $A^*$ heuristics like $h^{LM-cut}$.
  3. Efficiency Optimizations:
    • Transitivity Exploitation: By leveraging the transitive nature of dominance, the algorithm only compares new states against a subset of "non-dominated" visited states. This optimization alone can reduce dominance checking time by 40% to 60%.
  4. Invertible Leaf Spaces: For non-optimal planning, reversible leaf actions allow the algorithm to bypass complex reachability checks.
  5. Exact Duplicate Hashing: A fast hashing method for exact state matches provides a computationally cheap alternative to full dominance checks in specific domains.
Runtime ratios for blind search and unsolvability tasks, showing the impact of the transitivity optimization.

Experimental Evaluation

The proposed methods were evaluated using the International Planning Competition (IPC) benchmarks (1998–2018) and unsolvability benchmarks from the UIPC 2016. The results confirm that the logical power of a pruning rule is only half the battle; the data structures and algorithmic optimizations used to implement it are what make it viable for real-time search.

Key Results and Insights

The combination of stronger dominance relations and $g$-adaptation led to substantial improvements across several metrics:

  • Increased Coverage: The number of problems solved (coverage) increased across nearly all benchmark domains.
  • Reduced Search Effort: In domains such as Elevators and Transport, the number of state expansions and total runtime were reduced by several orders of magnitude.
  • Heuristic Visibility: Moving costs to the $g$-value makes standard heuristics much more effective by making more of the total plan cost visible to the search algorithm earlier.
Comparison of expansions and runtime for blind search, demonstrating significant reductions in search effort.

The "trading" principle is perhaps the most significant insight: in optimal planning, only the total cost matters. By summing maximal price differences across leaves and comparing them against $g$-value differences, the algorithm can prune states previously considered incomparable.

Conclusion and Future Work

This work demonstrates that the efficiency of decoupled search depends heavily on the implementation and logical strength of its pruning rules. While currently optimized for star-topology factoring, future work may explore extending these methods to more general topologies and further investigating the interaction between decoupled search and complex heuristics.

Summary updated

BibTeX
@inproceedings{gnad2021revisiting,
  author = {Daniel Gnad},
  title = {{Revisiting Dominance Pruning in Decoupled Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17403},
}
Figure