Introduction
In automated planning, the "state-space explosion" remains a primary challenge. Fork-decoupled search offers a significant optimization by partitioning planning tasks into a "center" component (e.g., a transport vehicle) and multiple "leaf" components (e.g., packages). Instead of exploring every global state, the search tracks the center's path and maintains a pricing function for each leaf. However, this method often suffers from "irrelevant distinctions," where the search retains redundant history that does not impact future goal achievement. This paper introduces advanced state-dominance criteria to prune these redundant branches, achieving exponential efficiency gains.
Advanced Dominance Criteria
The authors propose three primary dominance relations that extend the basic comparison ($\preceq_B$) used in earlier work. These criteria identify when one decoupled state is functionally superior to another, allowing the inferior state to be discarded without sacrificing optimality.
- Frontier-Based Dominance ($\preceq_F$): This criterion filters out leaf states that are "dead ends" or irrelevant to the goal, focusing only on those on the "frontier" that can contribute to future cost reductions.
- Effective-Price Dominance ($\preceq_E$): Utilizing a backwards-chaining algorithm, this method identifies "effective prices." It recognizes that if a leaf can reach a goal-contributing state from its current position at a certain cost, any other position reaching that same "staging area" at a higher cost is redundant.
- Simulation-Based Dominance ($\preceq_S$): Drawing from formal verification, this uses leaf simulation. If leaf state $A$ can perform all actions available to state $B$ at an equal or lower cost, $A$ is said to "simulate" $B$, allowing for the pruning of $B$.
These relations can be combined into a unified criterion, $\preceq_{ES}$, which integrates both effective prices and simulation for maximum pruning power.
The theoretical hierarchy of these relations demonstrates that while some criteria are strictly stronger than others, others—like frontier-based and simulation-based dominance—are incomparable, targeting different types of redundancy.
Experimental Evaluation and Results
The proposed methods were evaluated on standard International Planning Competition (IPC) benchmarks, including domains such as Logistics, Miconic, and NoMystery. The results demonstrate that these criteria are not merely incremental improvements but can provide exponential reductions in the search space.
For instance, in the Logistics98 domain, the new criteria reduced the number of expanded states by a factor exceeding 1,200x. In terms of coverage (the number of problems solved within time limits), the advanced criteria showed marked improvements over the baseline.
As shown in the experimental data, the combined $\preceq_{ES}$ criterion consistently achieves the highest total coverage. In the Miconic domain with a blind heuristic, coverage increased from 36 to 45 instances. Even when using the more powerful LM-cut heuristic, the advanced dominance criteria provided a significant boost, solving 275 total instances compared to 267 for the baseline.
Conclusion
By formalizing dominance relations that account for leaf frontiers, effective prices, and simulation, this research provides a robust framework for mitigating the state-space explosion in fork-decoupled search. While some computational overhead is involved in checking these relations, the resulting exponential pruning often leads to dramatic speedups and increased problem-solving capacity. Future work may explore how these dominance criteria interact with different factoring strategies to further optimize planning performance.
Summary updated