In graph search and automated planning, the standard way to avoid redundant work is duplicate detection. If an algorithm encounters a state it has already visited at a lower or equal cost, it discards the new state.
But what if two states are not identical, yet one is clearly worse than the other?
Imagine a vehicle routing problem where State A reaches a specific intersection at time $t=10$ with 5 gallons of fuel remaining, while State B reaches the exact same intersection at time $t=10$ with 8 gallons of fuel remaining. These two states are distinct, so standard duplicate detection will keep both. However, State B dominates State A. Because fuel consumption is monotonic, any valid path to the goal from State A can also be executed from State B, likely with more flexibility or lower total cost. We can safely throw State A away.
This is the core intuition behind dominance pruning: generalizing search elimination from strict mathematical identity to a partial order of utility. By proving that one state is "at least as good as" another, search algorithms can prune massive subtrees of logically valid but strictly inferior paths.
The Formalism of State Domination
The idea of using dominance to streamline search has deep roots. Nau et al. demonstrated that classical heuristic search algorithms (like A*) and Operations Research techniques (like Branch and Bound) can be unified under a single framework where pruning relies on generalized dominance relations rather than simple scalar cost bounds. Instead of evaluating states in isolation, search spaces can be structured to expose these relationships. For instance, Wellman and the authors of contemporary planning frameworks organized plans into a "specialization lattice." By deriving dominance relations across this hierarchy, a planner can eliminate entire classes of suboptimal paths before they are ever explicitly expanded.
Formally, a state $s_1$ dominates $s_2$ (written $s_1 \succeq s_2$) if:
- The cost to reach the goal from $s_1$ is guaranteed to be less than or equal to the cost from $s_2$.
- The transition capabilities and resource availability of $s_1$ encompass or exceed those of $s_2$.
Traditional heuristic search evaluates each state independently by estimating its remaining distance to the goal, $h(s)$. As Torralba argues, this independent evaluation misses structural properties of the search space. By shifting to contrastive analysis—directly comparing pairs of states—we can uncover dominance relationships that independent heuristics are blind to.
Why It Works: Resource and Progress Trade-offs
Dominance pruning is exceptionally powerful in domains with multi-dimensional constraints, where states track both a path cost and resource budgets.
Consider the Gas Station Problem investigated by Nandy et al., where an agent must navigate a graph while managing fuel levels and stops. A state is defined by a vertex, accumulated cost, remaining fuel, and the number of refueling stops. A sophisticated dominance rule allows the algorithm to discard a state if another active state has reached the same vertex with lower cost, more fuel, and fewer stops.
We see the same mechanism in real-time traffic scheduling. In the ERIS system developed by Goldstein et al., the search space for lane-based traffic signals is pruned by comparing schedules. If Schedule A has served fewer vehicles than Schedule B but has accumulated a higher total delay, Schedule A is strictly inferior and is immediately discarded.
The Hidden Pitfalls: Alignment and Overhead
While dominance pruning sounds like a guaranteed win, implementing it introduces two major challenges: heuristic alignment and computational overhead.
1. Heuristic Inconsistency
You might assume that adding dominance pruning to an optimal search algorithm like A can only make it faster. However, Torralba proved that if the heuristic and the dominance relation are unaligned, the search can actually become less efficient. If a heuristic gives a better estimate to a dominated state than to its dominating counterpart, A can be misled into expanding more states. To maintain optimal efficiency, the heuristic must be "consistent" with the dominance relation (i.e., if $s_1 \succeq s_2$, then $h(s_1) \le h(s_2)$), which surprisingly requires a reversal of traditional tie-breaking rules.
2. The $O(N^2)$ Comparison Bottleneck
Checking every newly generated state against every previously visited state creates a massive computational bottleneck. If you have $N$ states in memory, pairwise comparison takes $O(N^2)$ time.
To alleviate this, Gnad demonstrated that we can exploit the transitive property of dominance. If $s_1 \succeq s_2$ and $s_2 \succeq s_3$, then $s_1 \succeq s_3$. By maintaining only a minimal frontier of non-dominated states and bypassing redundant checks, the time spent on dominance verification can be cut nearly in half. Other approaches, such as the frontier-based pruning proposed by Torralba et al. for decoupled search, limit comparisons exclusively to specific leaf states that actively contribute to reaching the goal, avoiding unnecessary memory overhead.
Advanced Paradigms: From Nogoods to Novelty
The philosophy of dominance pruning can be used to supercharge other popular search reduction techniques.
Nogood Dominance Pruning (NDP)
In combinatorial optimization problems like bin packing or the knapsack problem, solvers use "nogood" pruning to record assignments that failed to yield a solution. Fukunaga et al. extended this concept into Nogood Dominance Pruning. Instead of only avoiding exact matches to failed states, NDP recognizes when a current set of items is strictly weaker (e.g., heavier or less valuable) than a previously explored set that failed. This allows the solver to discard massive subtrees that standard identity-based nogood pruning would miss.
Dominance-Aware Novelty
Novelty-based search is a powerful heuristic category that prunes states if they do not exhibit new feature combinations. However, as Groß et al. point out, standard novelty search fails catastrophically in domains with decreasing resources because every reduction in a resource (e.g., losing 1 unit of fuel) is technically a "novel" state. By framing novelty as an approximate form of dominance, they introduced dominance-aware novelty detection. This framework evaluates whether a state's facts are dominated by previously encountered facts, preventing the search from chasing wasteful, resource-depleting paths.
Standard Novelty:
State(Fuel=9) -> Unique? Yes (Keep)
State(Fuel=8) -> Unique? Yes (Keep) -> Leads to infinite exploration of wasting fuel
Dominance-Aware Novelty:
State(Fuel=9) -> Unique? Yes (Keep)
State(Fuel=8) -> Dominated by State(Fuel=9)? Yes -> Prune!
Continuous and Symbolic Spaces
The concept also extends beyond discrete state spaces. In infinite temporal planning with priced timed automata, Johansen et al. apply domination rules to symbolic "priced zones," discarding entire continuous regions that cost more across all valuations. Similarly, in Robust Markov Decision Processes (RMDPs), Ho et al. accelerate Bellman updates by identifying and eliminating dominated states—those with both higher values and higher weights—ensuring that the search for worst-case scenarios is restricted to a relevant subset of the state space.
Key Foundational Work
A General Paradigm for A.I. Search Procedures (1982) — contributed 2 concept elements to this direction.
66) (1987) — contributed 2 concept elements to this direction.
Dominance and Subsumption in Constraint-Posting Planning (1987) — contributed 1 concept elements to this direction.