Introduction
In the field of cost-optimal planning, the primary objective is to identify the least expensive sequence of actions to reach a goal state. However, planners frequently encounter the "state explosion problem," where the state space grows exponentially with the number of variables. While heuristics guide the search, pruning techniques are essential to discard redundant states. This paper introduces a general, automated approach to dominance pruning by adapting simulation relations from model checking.
Behavioral Dominance via Simulation
Traditional dominance pruning often relies on hard-coded, domain-specific rules. In contrast, this work utilizes simulation relations to identify when one state $t$ is behaviorally "at least as good as" another state $s$. Formally, $t$ simulates $s$ if every action possible in $s$ can be matched by $t$, leading to successor states that maintain the simulation relationship.
The authors extend this with label dominance, allowing the simulating state to use a "better" action than the original. For instance, a "no-op" might dominate an action that moves a package to an irrelevant location.
Compositional Approach and Implementation
Computing simulation relations on a global state space is computationally prohibitive. To address this, the authors propose a compositional approach:
- Orthogonal Projections: Compute simulations on small subsets of variables (abstractions).
- Composition: Combine these local relations to form a global dominance relation.
- BDD Integration: To minimize search overhead, Binary Decision Diagrams (BDDs) are used for fast membership testing. This allows the planner to quickly determine if a newly reached state is dominated by a previously explored one.
Experimental Evaluation
The proposed method was evaluated on STRIPS benchmarks from the International Planning Competitions (IPC). The results demonstrate significant reductions in the number of states explored.
As shown in the results table, the pruning method leads to a massive reduction in state evaluations in several domains. For example, in the Gripper domain, state evaluations dropped by a factor of over 50,000 using a blind heuristic. This reduction often translates to increased coverage—the total number of problems solved within time and memory limits—particularly in domains like Floortile, NoMystery, and VisitAll.
Insights and Limitations
A key insight of this work is that simulation-based pruning is orthogonal to other techniques like Partial-Order Reduction (POR). While POR focuses on action interleaving, simulation focuses on state equivalence, allowing them to be combined for additive benefits.
However, the method's effectiveness is sensitive to the choice of initial abstractions. If abstractions are too coarse, pruning opportunities are missed; if too fine, pre-computation becomes a bottleneck. Additionally, while the pruning is highly effective with simple heuristics, its impact can be less pronounced when paired with advanced heuristics like LM-cut, which may already implicitly account for some redundancies.
Conclusion
By bridging the gap between model checking and automated planning, this paper provides a robust framework for automated dominance pruning. The use of label dominance and BDDs makes behavioral state comparison a practical tool for scaling optimal planners to more complex domains.
Summary updated