Where the landmarks stand

An estimate borrowed from an easier problem measured why A*'s usual estimate fails on rough ground. The straight-line count of cells to the goal is admissible on a grid where steps cost between one and nine, because every step costs at least one, and it is nearly useless there, because it believes every step costs one. Guided by it, a search across a weighted grid expanded 1,550 cells where Dijkstra, with no estimate, expanded 1,572.

The repair measured in that essay is a table. Pick a few cells as landmarks, and store the exact distance from each landmark to every cell. For any cell $v$ and goal $t$, the triangle inequality says the distance from $v$ to $t$ is at least the difference between their distances from any landmark $L$, so

$$h(v) = \max_L \bigl|\,d(L, t) - d(L, v)\,\bigr|$$

is an estimate that never overestimates and, unlike the straight-line count, knows what the terrain costs. With four landmark tables the same search expanded 252 cells.

That essay chose its landmarks one way — each as far as possible from those already chosen — and did not ask whether the choice mattered. The estimate’s quality depends entirely on where the landmarks stand relative to the cells being searched between, so the choice should matter a great deal. This page measures how much.

The estimate that was already measured #

The landmark estimate cut the search by a factor of six, and it charged for it before the first query: four full searches, one from each landmark, 6,328 cell reads between them. Those tables are then reused for every query, which is what makes the trade worth considering at all — a preparation that costs four complete searches of the map, repaid by every later query that expands a sixth of what it otherwise would. The precondition on a function the caller writes measured the first estimate supplied to this search, and found that its guarantee holds only while the function never overestimates. A landmark estimate meets that condition by construction, whatever cells are chosen, so the choice of cells is free to be made for speed alone — and speed is all this page measures.

A query from corner to corner is also the easiest kind for landmarks placed far apart, since the two ends of the query are themselves near the edges of the map. The rest of this page asks random queries — each a pair of reachable cells drawn uniformly — so that the placements are compared on the queries a system would actually receive.

Why placement should matter #

The estimate for a cell $v$ is good when some landmark makes $|d(L,t) - d(L,v)|$ close to the true distance from $v$ to $t$. That happens when $L$ lies roughly behind $t$ as seen from $v$, or behind $v$ as seen from $t$ — when the shortest route from $L$ to one of them passes close to the other, so the two distances from $L$ differ by nearly the whole distance between them.

A landmark near the centre of the map is behind almost nothing. For most pairs of cells, the centre is somewhere between them or off to one side, and the distances from the centre to the two cells are similar, so the difference is small and the estimate is weak. A landmark in a corner is behind every pair of cells lined up with that corner, and four corners cover pairs lined up in four directions.

That argument predicts an order — corners best, centre worst — and not the size of the gap.

The query a landmark is exact for #

The argument has an extreme case that makes it concrete. Put a landmark exactly on the goal. Then $d(L, t)$ is zero and the estimate for every cell is its exact distance to the goal — the best estimate there can be. A* with an exact estimate expands only cells that lie on a shortest route and stops; there is nothing left to search.

Move the landmark a little beyond the goal, so that the goal lies between the landmark and most of the map. For a cell $v$ whose shortest route to the landmark passes through or near $t$, the difference $d(L, v) - d(L, t)$ is almost exactly the distance from $v$ to $t$, and the estimate is nearly exact again. Move the landmark to one side of the line from $v$ to $t$, and the two distances from it grow similar, and the estimate shrinks towards zero.

So a landmark is a partial answer to “how far is everything from the goal”, correct for the goals that lie between it and the cells being searched. Four landmarks at the corners answer that question well for every query that runs roughly towards one of the corners, which on a square map is nearly every long query. Four near the centre answer it only for queries that run towards the middle and stop there. The first plate’s corner-to-corner query is the friendliest case of all for farthest-first, whose first landmark is placed at the far corner — right behind that query’s goal.

Four landmarks placed four ways #

The placements compared are: no landmarks, which is Dijkstra; four near the centre, the open cells nearest four points a few cells from the middle; four at random, open cells drawn from a seed; farthest-first, the standard construction, starting from the cell farthest from the origin and adding each time the cell farthest from every landmark so far; and the corners, the open cells nearest the four corners of the map. On each of eight maps, the same 150 random queries are asked of every placement, and every search is checked to stop on the true distance.

The order is the predicted one, and the spread is a factor of 3.4 between the best and worst placements of the same number of tables at the same preparation cost. Four landmarks near the centre still halve Dijkstra’s work — any table knows something about the terrain — but four at the corners cut it by a factor of seven.

The dots show that the ranking is not an average hiding disagreement. On every one of the eight maps the corners beat farthest-first, farthest-first beats random, and random beats the centre. The per-map means for the corners run from 114 to 147 and for farthest-first from 128 to 150; the two ranges overlap, but on each individual map the corners come out ahead.

What farthest-first actually chooses #

Farthest-point selection is designed to spread landmarks out, and the corners are as spread out as a square map allows, so the result that they beat it needs an explanation. The map shows it.

Farthest-first’s first three landmarks are on the edges of the map: the far corner from the origin, a point along the bottom edge, and the top-right corner. Its fourth is at (23, 29) — near the middle. That is not a malfunction. After three landmarks along the edges, the cell farthest from all three, measured in weighted distance around the obstacles, is an interior cell that the three edge landmarks are all some way from. Farthest-first adds it, because it is designed to cover the map, and an interior landmark is exactly the kind that helps least.

The rule optimises the wrong quantity. Coverage — no cell far from every landmark — is what a nearest-landmark scheme needs. The landmark estimate does not use the nearest landmark; it uses the one behind the query, and a landmark is useful in proportion to how many queries it lies behind, which favours the periphery regardless of coverage. The corners have no coverage argument at all and they win because every one of them is peripheral.

The random placement’s spread tells the same story from the other direction. Its four landmarks on this map include (49, 0), a corner, and (2, 40), near an edge, alongside two interior cells, and its mean of 209 sits between the placements that are all peripheral and the one that is all central.

More landmarks, or better-placed ones #

With a single landmark the two rules are almost the same — farthest-first’s first choice is itself a corner, the one opposite the origin, and the corner rule’s first choice is the origin’s own corner — and they expand 400 and 405 cells. With two, farthest-first is slightly ahead. From four onwards the corners and edge midpoints are ahead, because that is where farthest-first starts placing landmarks in the interior.

The plate also prices the alternative to placing landmarks well, which is placing more of them. Doubling farthest-first’s landmarks from four to eight takes it from 141 cells to 101, a saving of 29%, and doubles the preparation and the memory. Moving four random landmarks to the corners takes 209 cells to 126, a saving of 40%, at no cost at all. Moving four central landmarks to the corners saves 70%.

Where the tables stand is worth more than how many there are, over the whole range drawn. That matters because the number of landmarks is the parameter a system exposes and tunes, and their placement is usually a fixed rule inside the implementation that nobody revisits.

What each table costs #

Doubling the landmarks on this query saves fifteen cells, from 252 to 237, and doubles the preparation, from 6,328 reads to 12,656. That is the same diminishing return the count plate showed across many queries, seen on one: each table adds a bound that the estimate takes the maximum over, and once a query already has a landmark behind it, another landmark behind it adds almost nothing.

There are two further costs no plate on this page charges. Memory: each table holds a distance for every cell, so eight tables are eight copies of the map’s size, and on a road network of millions of junctions that is the binding constraint. The space the model does not see is the site’s general warning about a cost a count of operations never shows, and landmark tables are a clean case: they appear in no count of expanded cells.

Evaluation: the estimate is a maximum over every table, recomputed for every cell the search considers, so a search with eight tables does twice the arithmetic per cell of one with four. The plates give enough to price that roughly, as cells expanded times tables consulted. Farthest-first comes to about 400 table lookups a query with one table, 419 with two, 566 with four and 806 with eight: going from four to eight saves 29% of the cells and spends 42% more lookups. The corners come to 405, 442, 505 and 740. Every table added costs more arithmetic than the cells it saves, at every count on the plate.

That does not make one table the right number, because a lookup is not the whole cost of a cell. Expanding a cell also reads up to four neighbours, evaluates the estimate for each one it reaches, and moves entries in the queue, so the rough price above undercounts lookups and ignores everything else a cell costs. Cells saved are worth more than a table’s lookups while that other work dominates. Where the balance falls depends on that ratio, which is a property of the implementation and the machine rather than of the map. What does not depend on it is the comparison at a fixed count: at four tables, the corners expand 11% fewer cells than farthest-first for exactly the same lookups per cell, and no ratio can make that a worse trade.

The frontier between time and space is the site’s standing picture of this shape of trade, with time on one axis and memory on the other. Better placement is a move towards the corner of that picture that costs nothing on either axis, which is the rarest kind of move the frontier has.

The estimate is a potential, and placement shapes it #

An estimate is a reweighting showed that A* with a consistent estimate is Dijkstra on arcs repriced by it. A landmark estimate is consistent — the difference of two distances from one landmark changes by at most an arc’s cost across that arc, and a maximum of consistent functions is consistent — so every search on this page is Dijkstra on a repriced map, and the placements are four different repricings of the same terrain.

A good repricing makes arcs leading towards the goal cost nearly nothing and arcs leading away cost nearly double, so the search runs downhill to the goal. A landmark behind the goal as seen from a cell makes the route towards the goal cheap in exactly that way; a landmark beside the route prices both directions nearly the same and leaves the terrain nearly as it was. The cells-expanded counts are therefore a measure of how steep each placement makes the repriced map along the routes random queries take, and the corners make it steepest.

That view also says what to expect when landmarks combine with the other speed-up measured on these grids. Where two searches should stop showed two-ended search saving about a third of the cells on these grids with no estimate at all. Two estimates that must agree found that searching from both ends needs a single potential shared by both searches, built from the forward and backward estimates. With landmark tables both estimates come from the same tables, and a placement good for one direction is good for the other, since a landmark behind the goal as seen from the source is behind the source as seen from the goal.

What the model leaves out #

Square maps with random obstacles. A map whose corners are unreachable, or whose useful routes all run along one corridor, would favour a different placement, and the corner rule has no way to notice. The finding is that placement matters by a factor of 3.4 on these maps and that the periphery is where good landmarks stand, not that corners are always right.

Uniform random queries. A system whose queries cluster — most from one district, most to one hub — would do best with landmarks behind the clusters, and could learn where those are from its query log. None of the four rules here uses the queries.

No placement search. Better rules exist in the literature on this estimate, which chooses landmarks to avoid regions already well covered by the landmarks so far, measured on sample queries. They are more expensive to compute and are not measured here.

Terrain that does not change. A table is exact only for the costs it was built on. If a stretch of terrain becomes dearer, every table’s distances through it are too small — still admissible, since a lower bound on a cheaper map is a lower bound on a dearer one — and the estimate quietly weakens. If a stretch becomes cheaper, the tables can overestimate, and A* stops guaranteeing a shortest path. Which placements degrade most gracefully under updates is a question these plates do not reach.

A rule is a constant somebody chose. Farthest-first selection is written into implementations as a fixed rule, and the threshold somebody chose found that fixed constants in sorting code were not optima when swept. The placement rule is the same kind of object, and the corner rule beating it on every map here is the same kind of finding.

Still open: landmarks chosen from the queries #

Every rule on this page chooses landmarks from the map alone. But the quantity that decides whether a landmark is useful — how many queries it lies behind — depends on the queries, and a system that has answered some queries knows something about the ones to come.

The measurement that follows chooses landmarks greedily from a sample of past queries: start with none, and repeatedly add the candidate cell whose table most reduces the total cells expanded on the sample, stopping at four. It then asks how many sample queries the greedy choice needs before it beats the corners on fresh queries, how far below 126 cells it can go, and what the choice costs to compute — since each candidate must be evaluated by rerunning the sample, the preparation is a search over searches, and it may cost more than the queries it saves.