A* and the heuristic

Guessing what is left to pay, why the guess must never be too high, and why greedy best first is not A*.

U9.4PlanningUniversity40 min

Dijkstra searches outwards in every direction equally, because it has no idea where the goal is. On the map in this module it expands about a thousand cells to find a path that visits sixty. Most of that work is spent exploring the wrong half of the mat.

A* fixes that with one change: order the queue by

f(n) = g(n) + h(n)

where g(n) is the cost actually paid to reach n, and h(n) is an estimate of what is left to pay from n to the goal. Everything else is Dijkstra, line for line. Set h to zero and you have Dijkstra back, which is the honest way to describe the relationship: A* is Dijkstra that has been told roughly which way the goal is.

Admissible

h must never overestimate the true remaining cost. A heuristic with that property is called admissible, and it is exactly the condition under which A* still returns an optimal path.

The reason is worth following. Suppose the goal is about to be popped with a suboptimal cost f = g, since h(goal) = 0. Somewhere in the queue there must be a node n on the true optimal path, with f(n) = g(n) + h(n). If h never overestimates, then f(n) is at most the true optimal cost, which is less than g. So n would have been popped first, and the goal would not have been popped early after all. Admissibility is precisely what makes that argument go through.

Overestimate, and A* becomes fast and wrong: it will happily return a route that is longer than necessary, and it will do it confidently.

Consistent

A stronger condition, sometimes called the triangle inequality or monotonicity:

h(a) <= cost(a, b) + h(b)     for every edge a to b

Consistency implies admissibility. What it buys is that f never decreases along a path, so the first time a node is popped its g is already final and it never needs reopening. Without consistency A* still finds the optimal answer, but it may have to put nodes back on the queue after improving them, which costs time and complicates the code.

Every heuristic in the table below is consistent on a grid, which is why grid implementations of A* can use the simple never-reopen form.

The octile distance is the exact cost of the cheapest eight-connected path on an empty grid, so it is the tightest admissible choice here: as large as it can be without ever exceeding the truth. Euclidean is admissible too, and it is slightly smaller, so it is slightly weaker, and A* expands slightly more cells with it.

A heuristic is stronger the closer it is to the truth from below. h = 0 expands everything. A perfect h walks straight to the goal. Everything useful is in between.

Why greedy best first is not A*

Drop g and order the queue by h alone. That is greedy best first search. It is fast, it is often a great deal faster than A, and it is not optimal and not complete on an infinite graph*. It goes straight for the goal and, on this map, dives into the dead end beside the first wall, backs out the way any queue-based search does, and returns a route noticeably longer than the best one.

The difference is exactly the g term. g is the part that remembers what has already been spent, and it is what stops the search from preferring a route that looks promising and is expensive.

On this map: A* returns a 331 cm path having expanded about 680 cells. Greedy returns a 410 cm path having expanded about 250. Greedy did a third of the work and produced a route a quarter longer. Whether that is a good trade is a real engineering question, and the answer for a robot that will drive the route hundreds of times is usually no.

Weighted A*

Between the two sits f = g + w * h with w greater than 1. The heuristic is inflated, so it may overestimate, so the result may be suboptimal, but by a bounded amount: the path is never worse than w times optimal. On this map w = 3 finds a 343 cm path with 366 expansions, which is 3 percent longer for half the work.

That bound is the thing worth taking away. Weighted A* is not a hack; it is a knob with a guarantee on it, which is why anytime planners are built out of it: run with a large w to get a route immediately, then rerun with smaller w while the robot is already moving, and improve the plan as the time allows.

from bugbot import *
import math
connect()

CELL = 5.0
goal = (34, 34)

def octile(c):
    dx, dy = abs(c[0] - goal[0]), abs(c[1] - goal[1])
    return CELL * (max(dx, dy) + (math.sqrt(2) - 1) * min(dx, dy))

def euclid(c):
    return CELL * math.hypot(c[0] - goal[0], c[1] - goal[1])

# on an empty grid, octile is exactly right and euclidean is an underestimate
for c in ((6, 6), (20, 34), (30, 20), (34, 30)):
    print(c, "octile", round(octile(c), 1), "euclid", round(euclid(c), 1))

Run this in the simulator

Octile is never smaller, and never larger than the truth. That is what "as tight as possible while still admissible" looks like.

Task: the same answer, less work

Run both searches over the same grid, eight neighbours, plain step costs of 5 cm and 5 root 2 cm, and print cost: (which should be identical either way), dijkstra: and a star:, the number of cells each expanded.

from bugbot import *
import heapq
import math
connect()

CELL = 5.0
N = 40
INFLATE = 8.0
WALLS = [(70.0, 0.0, 8.0, 115.0), (125.0, 85.0, 8.0, 115.0)]

Challenges

1. Add greedy best first as a third search and print its path length and its expansions. Confirm the numbers quoted above.
2. Multiply the octile heuristic by 1.5 and by 3. Plot expansions against cost and show the curve the weight traces out.
3. Use h = 10 * octile. The path will be far from optimal. Work out, from the bound, how far it is allowed to be.