M3-T4 — Heuristics: Admissible, Consistent, Informed

Learning objectives

After this lesson, you should be able to:

• Choose Manhattan, octile or Euclidean distance for a grid given its moves and step costs.
• Check a heuristic for admissibility and consistency with a short argument.
• Explain how tie-breaking changes the number of expanded cells and give two ways to break ties.
• Use weighted A* and state the bound it gives on the cost of the route.

The intuition

Ask four colleagues how far the pharmacy is from the lobby. The first counts corridor blocks east and then north, because she assumes she cannot cut across (Manhattan). The second points at the pharmacy and says 13 m as the crow flies (Euclidean). The third knows the robot can move diagonally and counts the cheapest mix of diagonal and straight moves (octile). The fourth only counts the longer of the two directions (Chebyshev) and ignores the shorter one. If the robot can move diagonally, the first colleague is wrong in the dangerous direction, the second and fourth are right but vague, and the third is exactly right on an empty floor.

A heuristic that is exactly right on an empty floor loses nothing, because walls can only make the real cost larger. A* using it expands the fewest cells it can without risking the answer.

The mathematics

The four distances

For two cells with column difference dx and row difference dy (both taken as absolute values), on a grid with straight steps of cost 1 and diagonal steps of cost √2:

The octile distance counts min(dx, dy) diagonal steps of cost √2 and the |dx − dy| straight steps that remain: min·√2 + (max − min) = max + (√2 − 1)·min.

Admissible and consistent

Admissible: h(n) ≤ h*(n), the true cost to the goal. Consistent: h(n) ≤ c(n, m) + h(m) for every edge. To check consistency of the octile distance it is enough to see that one move changes the octile distance to the goal by at most the cost of that move: a straight move changes dx or dy by one and the octile value by at most 1; a diagonal changes both by one and the value by at most √2. So octile is consistent, and so are Manhattan (on 4-connected grids), Euclidean and Chebyshev on grids where each move costs at least as much as the distance it covers.

Informed

If h₁(n) ≤ h₂(n) ≤ h*(n) for every n, then h₂ is more informed and A* with h₂ expands no more nodes than A* with h₁ (apart from ties). The best admissible heuristic is the largest one: octile on an 8-connected grid is more informed than Euclidean, which is more informed than Chebyshev.

Breaking ties

When many cells share the same f, A* must choose. On an open grid that is a large plateau of cells all with f = C*. Two common rules:

• Prefer the larger g (equivalently the smaller h). The search dives towards the goal along the plateau and typically expands far fewer cells.
• Add a tiny cross-product term to h that prefers cells near the straight line from start to goal; this also removes the zig-zag among equally cheap routes.

Tie-breaking changes how many cells are expanded and which of several equally cheap routes is returned. It never changes the cost.

Weighted A*

Multiply the heuristic by a weight w ≥ 1: f(n) = g(n) + w·h(n). The inflated estimate is no more than w times the true cost, so the route that A* returns costs at most w times the optimum, and in practice usually much less. Weighted A* with w = 1 is A*; as w grows it approaches greedy search.

Anytime variants such as ARA* start with a large w for a quick first answer and lower it while time remains.

A worked example

Four estimates for one pair of cells. Two cells are 12 columns and 5 rows apart on an 8-connected grid with diagonal cost √2.

The true cost on an empty grid is 5 diagonals plus 7 straights: 5 × 1.4142 + 7 = 14.071. Manhattan overestimates by 2.93 (21%), so A* using it can return a route that is not the cheapest. Euclidean and Chebyshev are 7.6% and 14.7% below the truth: safe, and they leave that much of f for the search to burn on cells that are not needed.

Weights in a hall. A hall of the kind used in lab M3-L2 is 20 rows by 32 columns, with a wall that has a gap and some trolleys. The cheapest route from start to goal costs 32.31. Counts of expanded cells, with ties broken by cell order:

Every route is within its bound: 1.077 ≤ 1.5, 1.128 ≤ 2 and 1.208 ≤ 5. The first step, from 558 cells to 226, is the heuristic; the next, to 96 for a 7.7% longer route, is the weight. The gain flattens quickly after w = 2: the returned route and the work barely change, while the worst case grows. Different halls give different numbers, and counts also depend on tie-breaking: the same A* with a different tie rule expands a different number of cells.

Engineering implications and limitations

Match the heuristic to the moves

The commonest heuristic bug is a mismatch between the moves and the formula: Manhattan on an 8-connected grid, or octile on a 4-connected one. The first is inadmissible and gives costly routes; the second is a heavy underestimate and gives a slow search. Write the heuristic next to the neighbour function and test it against a search on an empty grid.

Scale with the costmap

If the step cost is multiplied by a function of the costmap value (lesson M3-T7), a free cell costs 1 per unit and others more. The distance heuristic stays admissible because the cheapest possible cost per unit is 1. If the cost can be lower than 1 anywhere, the heuristic must be scaled down by that minimum.

Better than geometry

Geometric heuristics ignore walls. A heuristic that knows about walls, for example a Dijkstra distance on a coarse version of the map, or distances to a few landmark cells (the ALT idea), is closer to the truth and prunes more. It must still be admissible, and building it costs time.

Choose w by deadline

Weighted A* is a speed knob. Pick w from the time budget and the worst detour you can accept, test it on your own maps, and log the ratio of returned cost to a Dijkstra reference offline. A route 20% longer than the cheapest is acceptable for a hospital hallway and not for a tight dock manoeuvre.

Common misconceptions

Engineering takeaways

1. For an 8-connected grid with diagonal cost √2 use octile distance; for a 4-connected grid use Manhattan.
2. A heuristic must never exceed the true cost (admissible); consistency also makes a closed set safe.
3. A more informed admissible heuristic expands fewer cells; the best one is the largest that is still admissible.
4. Break ties towards larger g, and remember it changes effort and the route returned but never the optimal cost.
5. Weighted A* with f = g + w·h returns a route of cost at most w times the cheapest and expands far fewer cells.

References and further reading

Primary sources on heuristic search and weighted search.

• P. E. Hart, N. J. Nilsson and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107, 1968.
• I. Pohl, “Heuristic Search Viewed as Path Finding in a Graph”, Artificial Intelligence, 1(3-4), 193-204, 1970.
• M. Likhachev, G. Gordon and S. Thrun, “ARA*: Anytime A* with Provable Bounds on Sub-Optimality”, Advances in Neural Information Processing Systems 16, 2003.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: any-angle and fast search: Theta*, jump point search and bidirectional search.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T3: A*: Search with a Heuristic

  Trace A* with f = g + h, and explain why an admissible heuristic keeps it optimal while expanding fewer nodes.

• Lab
  M3-L2: Implement A* with Search Replay

  Make the same route faster: implement A*, then scrub through the search to see what it skipped.