Two estimates that must agree

Two ideas for making a shortest-path query cheaper have been measured separately. The precondition on a function the caller writes added an estimate of the remaining distance to Dijkstra’s priority key and cut a search across a grid from 1,582 expanded cells to 405. Where two searches should stop ran one search forward from the source and one backward from the goal, and found that the obvious rule for stopping them is wrong — stopping at the first cell both have finished returned a longer path on some grids — while the rule that tracks the best route seen across any arc and stops when the two frontiers’ smallest keys together reach it is always right.

The natural combination is two A* searches, one from each end, each guided by an estimate towards the other. That essay closed by predicting why it would break. An estimate is a reweighting had shown that A* is Dijkstra on arcs repriced by the estimate, so a forward A* guided towards the goal and a backward A* guided towards the source are two Dijkstra searches on two different graphs. The stopping rule adds a forward key to a backward key and compares the sum with a route’s cost, which only means something if both keys price the same arcs.

This page measures the naive combination, the rule that is correct whatever the estimates, and the repair — and then checks how much the repair costs.

The rule that was correct, and where it came from #

The correct rule’s argument is short, and the whole of this page turns on one step of it. Let $\mu$ be the cheapest route found so far that crosses from a cell the forward search has reached to a cell the backward search has reached. Any route not yet found must leave the forward search’s finished cells through some cell $u$ still on its frontier and enter the backward search’s finished cells through some $v$ still on the other frontier, so it costs at least the forward distance to $u$ plus the backward distance from $v$. Those distances are at least the two frontiers’ smallest keys. So once the two smallest keys add up to $\mu$ or more, no unfound route can beat $\mu$, and stopping is safe.

The step that matters is “those distances are at least the smallest keys”. For Dijkstra a key is a distance, so it holds trivially.

Why separate estimates break it #

Give the forward search the straight-line estimate of the distance to the goal, $h_t$, and the backward search the straight-line estimate of the distance from the source, $h_s$. Each is a correct A* on its own: the forward key of a cell $u$ is its distance from the source plus $h_t(u)$, never more than the length of the best route through $u$.

Now add a forward key to a backward key. The sum is the forward distance to $u$, plus $h_t(u)$, plus the backward distance from $v$, plus $h_s(v)$. The two estimates are estimates of different stretches of the same route — $h_t(u)$ of everything after $u$, $h_s(v)$ of everything before $v$ — and when $u$ and $v$ lie near each other in the middle of the grid, those two stretches overlap almost completely. The sum counts the middle of the route twice. It can reach $\mu$ while a cheaper route through the middle still exists, and the search stops before finding it.

On weighted terrain the separate estimates with the sum rule are the cheapest search on the plate at 1,002 cells, and wrong on twelve of the forty grids. The prediction holds, and it holds more often than the meeting rule’s failure did on the earlier plate — twelve in forty against five — because the double-counted middle is a systematic overestimate rather than an occasional unlucky ordering.

On unit steps none of the forty grids goes wrong. That is not a guarantee. On a grid where every step costs one, the straight-line estimate is nearly exact in open ground, and a search guided by a nearly exact estimate from either end walks almost straight to the other end’s frontier; there is little middle for the two estimates to double-count before the searches meet. The rule is still unjustified there, and the plate records that on these forty grids the unjustified rule happened not to fail.

One grid, taken apart #

On this grid the separate estimates stop fifteen cells sooner than the repaired search and return a path ten units longer than the shortest — about three per cent. The route the early stop missed runs through the middle of the grid, exactly the region where the forward key’s estimate of the rest of the route and the backward key’s estimate of its beginning cover the same ground.

The size of the error is worth keeping in proportion. Three per cent is small, and on the other eleven grids that went wrong the excess ranges from one unit to ten. A search that returns a slightly longer path is not useless. But it is not the search it claims to be — every method on this plate is described as returning a shortest path — and the failure is invisible from the output, which is a path of plausible length that nothing flags.

It would also be hard to catch in testing, for exactly the reason the unit-step grids show. A test suite for a path-finder is usually built on grids where the right answer is easy to check by eye, and those are grids with unit steps, where the straight-line estimate is nearly exact and the double-counted middle almost never matters. On the forty unit grids here the incorrect rule returned the right answer every time. It is on the terrain that a real system is built for — steps of different costs, estimates that understate them — that it fails, and it fails by a few per cent at a time. The adversary who hides the edge makes the general point about arguments of this kind: a procedure that has only been shown easy inputs has been shown nothing about the hard ones, and a check has to be built from the inputs that break the claim.

The rule that is correct whatever the estimates are #

There is a stopping rule that survives separate estimates, and it follows from the property that makes each A* correct on its own. The forward key of a frontier cell is at most the length of the best route through that cell. So when the forward frontier’s smallest key reaches $\mu$, every route through any unfinished forward cell costs at least $\mu$, and every route not yet found passes through such a cell. Stopping then is safe. The same holds for the backward frontier.

So stopping when either frontier’s smallest key alone reaches $\mu$ is always correct, and the plate shows the price: 3,491 cells on weighted terrain, three times the incorrect search and twice A* from one end. The rule throws away the reason for searching from both ends. It waits until one search, on its own, has covered enough of the grid to prove the answer — which is roughly what a one-ended A* has to do — while the other search expands cells in parallel that contribute nothing to the proof. Two searches doing the work of one, plus a second one.

Making the two estimates agree #

The repair is to stop the two searches working on different graphs. Give the forward search the potential

$$p(v) = \tfrac{1}{2}\bigl(h_t(v) - h_s(v)\bigr)$$

and the backward search its negative. Reprice every arc from $u$ to $v$ by $w + p(v) - p(u)$. The backward search walks arcs in reverse, and repricing a reversed arc by its own potential, $-p$, gives $w + (-p)(u) - (-p)(v)$, which is the same number. So both searches now run Dijkstra on one repriced graph.

The repriced arcs are never negative when both estimates are consistent — when each estimate changes by no more than an arc’s cost across that arc. Half of $h_t(v) - h_t(u)$ is at least $-w/2$, and half of $h_s(u) - h_s(v)$ is at least $-w/2$, so $w + p(v) - p(u)$ is at least $w - w/2 - w/2 = 0$. Two-ended Dijkstra on a graph with non-negative arcs is exactly the case the correct stopping rule was proved for. And the constant by which repricing shifts every route’s cost cancels in the rule: the forward key carries $p$ at the goal’s end of the route and the backward key carries $-p$ at the same place, so the sum rule on the keys is the sum rule on the repriced distances with nothing added.

The cost of the repair is in the strength of the estimate. The forward search is now guided by half the distance-to-goal estimate, offset by half the distance-from-source estimate, which is a weaker pull towards the goal than $h_t$ alone. Each search is less directed, and should expand more.

The averaged potential never costs more than 8% over the incorrect search on any grid, and 4% on average. Against the correct alternatives it is the cheapest by a wide margin: 1,041 cells against 1,171 for two-ended Dijkstra, which uses no estimate at all, and against 3,491 for the rule that tolerates separate estimates.

That makes the result unusually clean. The incorrect search is only slightly cheaper than the correct one, and the correct one is substantially cheaper than every other correct search on the plate. There is no trade here to agonise over. The four per cent is the price of a guarantee, and it is a small price.

Why the straight-line estimate helps two ends and not one #

The weighted plate has a second finding that is not about stopping at all. A* from one end expands 1,748 cells and two-ended Dijkstra 1,171: on weighted terrain, searching from both ends with no estimate beats searching from one end with an estimate.

An estimate borrowed from an easier problem explained the first number. The straight-line estimate counts cells as though every step cost one, and on terrain where steps cost one to nine it underestimates the remaining cost by a factor of about five, so it barely directs the search. Two-ended search helps for a geometric reason that has nothing to do with the estimate: two discs of half the radius hold about half the area of one disc of the whole radius, so two frontiers that meet in the middle have expanded about half the cells one frontier needs.

On unit steps the same comparison runs the other way, 473 cells for one-ended A* against 1,403 for two-ended Dijkstra, because there the estimate is nearly exact and a one-ended search guided by it is already close to a straight line. A second search from the other end adds cells and removes almost none.

The combinations inherit both effects. On weighted terrain the averaged potential, at 1,041, gains from the two ends and a little from the estimate. On unit steps every two-ended A* expands 469 cells, four fewer than one-ended A* — the estimate did the work, and the second end was carried along.

On unit steps the separate estimates and the averaged potential expand exactly the same cells on this grid, and both find the shortest path. When the estimate is close to exact from both ends, averaging the two potentials loses almost nothing, because each half-estimate still points almost straight at the other end — and the double-counting that broke the sum rule on weighted terrain has almost no middle to act on.

What the three rules teach about combining guarantees #

Each of the two techniques combined here came with a guarantee and a condition. A* returns a shortest path if its estimate never overestimates. The two-ended stopping rule returns a shortest path if the keys it adds are distances in one graph. The naive combination kept each technique’s condition satisfied on its own terms — both estimates were admissible, both searches were correct A* searches — and violated the condition of the combination, which neither technique’s statement mentions because neither was written with the other in mind.

That is the general hazard in composing algorithms that carry preconditions, and the bound with a precondition found its simplest form: Dijkstra’s guarantee is conditioned on non-negative arcs, and on four vertices with one negative arc it is wrong. Here the condition that failed is subtler, since every arc was non-negative and every estimate admissible. What failed was an implicit condition of the stopping rule — that the two keys measure the same thing — which only becomes a condition at all once there are two estimates to disagree.

The repair has a shape worth recognising too. Rather than weakening the rule to tolerate the disagreement, which is what the either-key rule does at three times the cost, it removes the disagreement by construction, so the original rule’s proof applies unchanged. An estimate is a reweighting is what made that possible: once an estimate is seen as a potential that reprices arcs, two estimates can be combined into one potential, and the question “do these keys agree” becomes the question “is this one graph”, which has a yes-or-no answer.

The checks hold the combination to both halves: on twenty weighted grids the averaged potential must return the shortest path every time, and the separate estimates with the sum rule, offered as a search that returns shortest paths, must be refused — which they are, on the second grid, with a path of 376 where the shortest is 375.

With a stronger estimate #

Every search on this page used the straight-line count of cells, which on weighted terrain is weak enough that most of the saving comes from searching from two ends. Where the landmarks stand measured a much stronger estimate on the same grids — tables of exact distances from a few chosen cells — which cuts a one-ended search by a factor of six or more.

A landmark estimate is consistent, so the averaged potential applies to it unchanged, and the argument above says what should happen. With a strong estimate the forward search alone already runs almost straight to the goal, so a second search from the other end has less to save, and averaging the two estimates halves a pull that was doing most of the work. The prediction is that the two-ended repair loses its advantage over one-ended A* as the estimate strengthens, which the unit-step grids already show in miniature: there the straight-line estimate is nearly exact, and every two-ended search expanded 469 cells to one-ended A*'s 473. The combination of the two techniques is worth most when the estimate is weak and the terrain is hard, which is exactly the case in which the naive combination fails.

What the model leaves out #

One estimate family. Every search here uses the straight-line count of cells, which is consistent on these grids. With an admissible estimate that is not consistent, the averaged potential’s arcs can go negative and the repair no longer applies; an estimate is a reweighting measured what an inconsistent estimate does to a single search, and the two-ended case would inherit that failure in both directions.

Corner-to-corner queries only. A query between two cells close together, or between a cell and one behind an obstacle, gives the two searches much less room to overlap, and the separate estimates’ rate of failure would move. Twelve in forty is a figure about long diagonal queries.

Expansions, not time. The averaged potential evaluates two estimates per cell where a separate search evaluates one, which the count of expanded cells does not charge. On straight-line estimates that is two subtractions; on the landmark tables of the earlier essays it is two passes over every table.

Still open: stopping earlier without giving up the guarantee #

The averaged potential pays four per cent for correctness because its keys are weaker than the separate estimates’ keys, and the sum rule has to wait for weaker keys to add up to $\mu$. But the separate estimates’ keys are still valid lower bounds for their own searches, even when they cannot be added.

That suggests a rule that uses both. Stop when the averaged keys’ sum reaches $\mu$ — which is always safe — or when either separate key alone reaches $\mu$ — which is also always safe — whichever happens first. On grids where the averaged search reaches its stop first nothing changes; on grids where one search’s own estimate proves the answer sooner, the combined rule stops earlier and remains correct. The measurement that follows runs both searches’ keys side by side and asks how many of the forty grids stop sooner under the combined rule, by how many cells, and whether the bookkeeping for two sets of keys costs more than the cells it saves.