Abstract
Classical AI planning is frequently hampered by the "state space explosion" problem, where the number of reachable states grows exponentially with the complexity of the problem. This paper introduces Decoupled Strong Stubborn Sets (DSSS), a novel pruning technique that integrates structural decomposition (fork-decoupling) with partial order reduction (strong stubborn sets). By adapting stubborn set theory to the reformulated state space of decoupled search, the authors achieve significant search space reductions. Theoretical analysis proves the exponential separation of the two base methods, while empirical results on International Planning Competition (IPC) benchmarks demonstrate that DSSS often outperforms both individual techniques, particularly in domains like Logistics.
1. Introduction
In classical AI planning, the primary challenge is the exponential growth of the state space as the number of objects and actions increases. Two distinct techniques have been developed to address this: Fork-Decoupled Search, which exploits structural dependencies between a "center" component and several "leaf" components, and Strong Stubborn Sets (SSS), a form of partial order reduction that prunes redundant action sequences. This paper proposes a combination of these methods, termed DSSS, to leverage their complementary strengths and address the gap where neither method alone is sufficient.
2. Background
2.1 Fork-Decoupled Search
Fork-decoupling identifies a structure where a center component (e.g., a truck) provides preconditions for multiple leaf components (e.g., packages). Instead of searching through all combinations of center and leaf states, decoupled search explores only the paths of the center component, tracking the possible states and costs for each leaf independently. This effectively removes the combinatorial explosion caused by leaf interactions.
2.2 Strong Stubborn Sets (SSS)
SSS is a partial order reduction technique that identifies sets of actions that are independent or commutative. By ensuring the search only explores a subset of possible action orderings without losing completeness or optimality, SSS significantly reduces the branching factor in the state space.
3. Decoupled Strong Stubborn Sets (DSSS)
The authors develop DSSS by redefining the core components of SSS to function within a decoupled state space. This involves extending the definitions of action applicability and "necessary enabling sets" to account for the pricing functions used in decoupled search.
A key theoretical insight is the exponential separation between decoupled search and SSS. The authors prove that there are problem classes where decoupling provides an exponential reduction while SSS does not, and vice versa. This justifies the integration, as the combined method can handle problems that are intractable for either base method.
A unique challenge in this integration is handling goal states. In decoupled search, reaching a goal state in the center does not necessarily mean the optimal plan has been found, as additional center actions might enable cheaper leaf goal states. To maintain optimality, the authors introduce Frontier Actions—leaf actions that are not currently applicable but could be enabled by center actions to reduce total plan cost. These serve as landmarks to keep the stubborn set focused on cost reduction even after a center goal is reached.
4. Experimental Evaluation
The method was implemented in the Fast Downward framework and tested on 12 IPC domains where fork structures could be automatically identified. The evaluation compared DSSS against standard A*, SSS, and decoupled search (DS) using both blind and LM-cut heuristics.
4.1 Key Results
- Search Reduction: In domains like Logistics, DSSS reduced the number of expanded states by up to two orders of magnitude compared to standard decoupled search. This demonstrates a "sum is greater than its parts" effect, where decoupling removes leaf-state blow-up and SSS prunes the remaining center-action blow-up.
- Coverage: DSSS generally increased the number of problems solved. For example, with the LM-cut heuristic, total coverage across the 12 domains rose from 267 (DS) to 274 (DSSS).
- Robustness: DSSS rarely performed worse than its individual components. While computing stubborn sets adds some per-state overhead, it is typically negligible compared to the time saved by pruning the search space, especially when using expensive heuristics like LM-cut.
5. Conclusion and Future Work
DSSS represents a powerful synthesis of structural decomposition and partial order reduction. By pruning the center actions in a decoupled search space, it provides exponential reductions in structured domains. Future work will explore extending this technique to more general structural decompositions, such as star-topology decoupling, and combining it with other reduction methods like symmetry pruning. To mitigate overhead in simple problems, the authors also suggest a "safety belt" mechanism to dynamically disable DSSS if no significant pruning is observed.
Summary updated