Pareto Dominance Pruning for Multi-Objective Search

187 concepts136 papers2 proposals

When navigating a map using standard shortest-path algorithms like A*, the decision-making process at any given intersection is straightforward: if you find a shorter path to a specific landmark, you keep it and discard the longer one. However, real-world planning rarely involves just one goal. Whether routing an autonomous vehicle to balance travel time, energy consumption, and safety risk, or optimizing database queries for memory usage and execution time, we live in a multi-objective world.

In multi-objective search, a single node no longer has a single "best" cost. Instead, it maintains a Pareto frontier—a set of solutions representing optimal trade-offs where no single objective can be improved without degrading another. This introduces a severe combinatorial explosion: as an algorithm explores a graph, the number of non-dominated partial paths at each node can grow exponentially, paralyzing the search.

To make multi-objective search tractable, researchers rely on dominance pruning. The core intuition is simple: if a partial path $A$ reaches a state having spent more time, more money, and more energy than an alternative partial path $B$ at that same state, path $A$ is strictly inferior. Because any future extension to path $A$ will accumulate the same additional costs as an extension to path $B$, path $A$ can never catch up to become part of a globally optimal trade-off. By identifying and discarding these dominated paths early, algorithms can aggressively shrink the search space.

Overcoming the Dominance Check Bottleneck

While pruning eliminates unnecessary node expansions, the act of checking for dominance introduces its own computational bottleneck. In a naive implementation, every time the algorithm discovers a new partial path, it must perform a pairwise vector comparison against every single path already stored in that node's frontier. As the frontier grows, this linear scan becomes incredibly expensive.

To bypass this bottleneck, researchers have shifted from exhaustive set-based comparisons to structural and scalar-based indexing. Carlos Hernández Ulloa et al. introduced Bi-Objective A (BOA), demonstrating that by exploiting the properties of consistent heuristics, the multi-objective dominance check can be reduced from a linear-time search to a constant-time operation. Instead of scanning an entire list, the algorithm compares the new path's cost against a single scalar value representing the best-known boundary of the frontier.

When scaling beyond two objectives, maintaining this efficiency requires smarter data structures. Han Zhang et al. developed bucket-based indexing arrays that organize the frontier structurally. This optimization slashes the number of required vector comparisons by up to 95%, allowing multi-objective search to scale effectively to large real-world road networks.

Proactive and Goal-Directed Pruning

Pruning does not have to be a reactive process that only triggers when two paths collide at the same intermediate node. By incorporating heuristic estimates of the remaining journey, algorithms can prune paths based on their projected final costs at the destination.

As surveyed by Oren Salzman et al., goal-directed pruning uses lower-bound heuristics to project a partial path's ultimate trajectory. If a partial path's optimistic final cost vector is already dominated by an actual, fully completed solution at the destination, the partial path is discarded immediately. To generate the tight lower bounds necessary for this to work, Nathan R. Sturtevant et al. utilize independent backward single-objective searches for each cost dimension, ensuring the heuristic estimates are as accurate as possible.

Furthermore, multi-objective problems can be solved hierarchically. Emma Rollon et al. demonstrated that maintaining frontiers of cost vectors from smaller, nested subproblems provides powerful multi-value lower bounds. These subproblem frontiers act as a collective shield, dominating and eliminating suboptimal search paths in larger problem instances much more effectively than any single-value bound could.

Approximations and Budget Constraints

In many complex domains—such as multi-agent pathfinding where multiple robots must coordinate without colliding—the exact Pareto frontier remains too dense to compute efficiently. In these scenarios, researchers relax the strictness of Pareto optimality to achieve massive performance gains.

Zhongqiang Ren et al. and Fangji Wang et al. utilize $\epsilon$-dominance pruning. Instead of keeping every single unique trade-off, the algorithm discards new paths unless they offer a significant improvement (by a factor of $\epsilon$) over an existing path. This effectively discretizes the frontier, merging paths that are nearly identical and preventing the exponential explosion of the solution set while guaranteeing that the final options remain highly representative.

Strict Dominance:  Keep path if it is better in at least one dimension.
[Path A: 10 mins, $5] vs [Path B: 11 mins, $4] -> Keep both.

Epsilon-Dominance: Keep path only if it improves a dimension significantly.
[Path A: 10 mins, $5] vs [Path B: 10.1 mins, $4.9] -> Prune Path B (marginal gain).

Finally, the nature of the search changes entirely when users have hard constraints. In everyday navigation, we often have strict budgets (e.g., "I must arrive within 30 minutes and spend less than $15"). Shawn Skyler et al. showed that applying these thresholds directly to the search allows for immediate pruning of any partial path that breaches any single objective bound. This shifts the algorithm from an exhaustive, open-ended frontier discovery into a highly focused satisficing search, isolating the computation to a strict "budget rectangle" in the cost space and delivering speedups of up to two orders of magnitude.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 127 papers
  2. Version 1 · 2026-10-04 · 164 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_multi_objective_path_pruning_11e649f2,
  title = {multi-objective path pruning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-objective-path-pruning/rdr_11e649f2876949f291234f99fc2d6e00},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_multi_objective_path_pruning_11e649f2_v2,
  title = {multi-objective path pruning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-objective-path-pruning/rdr_11e649f2876949f291234f99fc2d6e00/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake