How is this different from front-to-end?

Front-to-end estimates distance to a fixed start or goal; front-to-front uses estimates between states that can lie on the evolving frontiers.

Does the heuristic need to know exact connecting distances?

No. Useful admissible estimates can be cheaper than exact distances, although stronger estimates may cost more to compute.

Does the first frontier connection finish an optimal search?

Not necessarily. The algorithm must establish that no cheaper solution remains possible under its stopping conditions.

AI Glossary / Graphs and symbolic AI / Advanced

Front-to-front

Definition

Front-to-front describes bidirectional heuristic search that uses estimated distances between states on opposing search frontiers. The heuristic can respond to where the other search has progressed, rather than estimating only the distance to the original start or goal.

What it means

A bidirectional search grows one exploration from the start and another from the goal. Each frontier contains discovered states awaiting further exploration. Front-to-front information estimates the gap between these changing sets of states.

This can offer more targeted guidance than a heuristic aimed only at a fixed endpoint. It also creates work: a frontier can contain many states, and comparing candidates across both sides may be expensive.

The term describes a class of heuristics and search designs, not one complete algorithm. A valid implementation still needs path-cost accounting, duplicate handling, an expansion policy and a stopping condition that supports its claimed solution quality.

How it works

A pairwise heuristic h(u,v) estimates the cost of going from forward-frontier state u to backward-frontier state v in the original problem direction. For an admissible pairwise heuristic, that estimate must not exceed the actual shortest connecting cost.

One way to describe the gap to the opposite frontier is to take the minimum pairwise estimate over its states. Algorithms may combine such estimates with discovered prefix and suffix costs or use more specialized pair-selection bounds. Those quantities have different meanings and should not be substituted casually for one another.

As frontier membership changes, relevant pairwise values or summaries may need updating. A naive comparison of every forward state with every backward state has cost proportional to the product of the frontier sizes. Efficient data structures and stronger assumptions can change that implementation tradeoff.

Three practical examples

Puzzle search: A heuristic estimates how far a partially explored forward configuration is from configurations discovered from the goal.
Geometric pathfinding: Pairwise distance estimates help relate two growing sets of candidate positions.
Search research: Researchers study whether richer pairwise information reduces enough node expansions to justify its evaluation and maintenance cost.

Think of it this way

Think of two groups surveying a route from opposite ends and comparing their current positions, rather than only measuring toward the other group's original starting point. The analogy explains moving targets. It does not mean the physically nearest pair produces the cheapest complete route, because each group has already accumulated travel cost.

Worked example

Suppose a forward candidate U has a discovered prefix cost gF(U) = 2. The backward frontier contains V1 and V2. Their discovered suffix costs to the goal are gB(V1) = 3 and gB(V2) = 8.

Let the pairwise heuristic estimates be h(U,V1) = 4 and h(U,V2) = 1. Looking only at the estimated gap favors V2: its estimated distance from U is 1 rather than 4.

However, combining the displayed prefix, gap estimate and suffix gives 2 + 4 + 3 = 9 through V1, compared with 2 + 1 + 8 = 11 through V2. The closest-looking frontier state does not necessarily give the best estimated complete route.

Neither value establishes an actual path unless the missing connecting segment has been found. Also, these sums are not automatically global lower bounds if the stored prefix or suffix costs are not known to be optimal. A search algorithm's proof must state exactly which costs and bounds it uses.

Now imagine 200 forward candidates and 300 backward candidates. Evaluating every pair requires 60,000 heuristic calls for one complete pairwise sweep. That is only a count of comparisons, not a runtime prediction, but it shows why a reduction in expanded nodes can still be offset by pairwise bookkeeping.

Illustrative case study

Fictional case: Birch Search compares two bidirectional planners on a set of synthetic navigation graphs. One uses fixed-endpoint heuristics; the other evaluates distances between opposing frontier states.

The second planner expands fewer nodes on several cases but spends more time scanning frontier pairs. The team adds instrumentation for heuristic calls and frontier updates instead of concluding from node counts alone that it is faster.

A correctness review also finds a shortcut that treats the smallest pairwise gap as a complete route cost. The team restores the required prefix and suffix accounting and verifies returned routes against a baseline. The case illustrates the distinction between stronger information, correct use of that information and efficient implementation.

Common misconceptions and mistakes

Front-to-front means selecting the nearest geometric pair. The heuristic may represent non-geometric costs, and complete-route accounting still matters.
A low pairwise estimate proves a connection exists. It is an estimate and may ignore obstacles or other constraints.
Fewer expansions guarantee lower runtime. Pairwise evaluations and data-structure maintenance can dominate.
Any pairwise lower bound can be dropped into any stopping test. The algorithm's assumptions and bound derivation must match.

Business use

Front-to-front methods are relevant when pairwise estimates are informative and their cost can be controlled. They can be attractive in domains where both search directions expose useful structure that fixed-endpoint estimates miss.

Assess the cost of building and querying the heuristic as well as the search itself. Test directed graphs with the correct u-to-v orientation, and separate discovered route costs from proven distance bounds. Benchmark across frontier sizes and problem families rather than relying on one favorable instance.

Check your understanding

Candidate V1 is closer to U according to the pairwise heuristic, but has a much more expensive known suffix to the goal. Must V1 provide the better complete route?

Answer: No. Gap distance alone omits the prefix and suffix costs, and the gap may not yet correspond to a discovered connection.

Related terms

Bidirectional search
Front-to-end
Heuristic function
search frontier
admissibility
node expansion
lower bound
pairwise distance

Learn next

Change the suffix cost of V2 in the worked example from 8 to 2 and recompute the displayed route estimates. Then explain which additional facts would be needed to turn either estimate into a verified complete path and a justified optimality claim.

Sources

Siag and colleagues define and compare front-to-front and front-to-end heuristic information: https://ojs.aaai.org/index.php/SOCS/article/download/27296/27069/31340

Eckerle and colleagues analyze sufficient expansion conditions for both approaches: https://ojs.aaai.org/index.php/ICAPS/article/view/13825

Kaindl and Kainz examine bidirectional heuristic search more broadly: https://arxiv.org/abs/cs/9712102

The pairwise arithmetic and Birch Search case are original illustrations. The example distinguishes heuristic estimates, discovered costs and valid global bounds.

Previous: Front-to-end Next: Frontier