1.2 A* and Heuristics: The Estimate Must Speak the Same Language as the Cost Model

Uniform-cost search can find the lowest-cost path, but it expands in all directions. In the Developer Workshop's map, the destination lies to the east. If we can estimate "how much cost remains from here to the destination," the search can prioritize states that appear more promising.

A* doesn't arbitrarily prune bad paths. Instead, it reorders expansion using $f(n) = g(n) + h(n)$; its optimality depends on the heuristic, termination conditions, and how repeated states are handled.

Learning Objectives

• Distinguish between cumulative cost $g$, heuristic $h$, and priority $f$;
• Determine whether a heuristic is admissible and consistent;
• Implement A* that handles outdated queue entries and reopens nodes;
• Evaluate the heuristic benefit and the trade-offs of optimality in Weighted A*.

1. The Three Components of A*

• $g(n)$: the known lowest cost from the start node to node $n$;
• $h(n)$: an estimated remaining cost from node $n$ to the goal;
• $f(n) = g(n) + h(n)$: an estimated total cost of the path through node $n$ to the goal.

When $h(n) = 0$, A* reduces to Uniform Cost Search (UCS). If $h$ exactly matches the true remaining cost, the search becomes highly direct; otherwise, when the actual cost is unknown, a heuristic is required.

The heuristic must be consistent with edge costs. For instance, if $g$ represents time, $h$ cannot simply add up distances in kilometers, unless those distances are converted into time lower bounds using a speed bound.

2. Admissible and Consistent

Admissible:

$$ 0 \le h(n) \le h^*(n), $$

meaning the heuristic does not overestimate the true minimum remaining cost.

Consistent (or monotone): for every edge $n \to n'$:

$$ h(n) \le c(n, n') + h(n'). $$

Consistency is analogous to the triangle inequality and guarantees that the heuristic value does not decrease along any path. For A* on a graph, a consistent heuristic ensures that once a node is extracted from the priority queue with the best $g$-value, it can be safely marked as closed. While an admissible but inconsistent heuristic may still find an optimal solution, the implementation must allow better paths to re-open previously expanded nodes.

3. A* Algorithm Implementation with Stability

import heapq
from itertools import count

def a_star(edges, start, is_goal, heuristic):
    tie = count()
    best_g = {start: 0.0}
    parent = {start: None}
    frontier = [(heuristic(start), 0.0, next(tie), start)]

    while frontier:
        _, g, _, state = heapq.heappop(frontier)
        if g != best_g.get(state):
            continue                    # Better path has been enqueued, old entry invalidated
        if is_goal(state):
            return reconstruct(parent, state), g

        for next_state, step_cost in edges(state):
            if step_cost < 0:
                raise ValueError("A* requires non-negative edge costs")
            new_g = g + step_cost
            if new_g < best_g.get(next_state, float("inf")):
                best_g[next_state] = new_g
                parent[next_state] = state
                new_f = new_g + heuristic(next_state)
                heapq.heappush(
                    frontier,
                    (new_f, new_g, next(tie), next_state),
                )

    return None

The queue saves the enqueue time of g, compares it with best_g upon popping, and skips stale entries. There is no permanent closed set, so states are reprocessed if a lower cost is discovered, making it suitable for inconsistent heuristics.

The goal is to terminate when the current minimum f is popped, rather than terminating on the first generation. The latter might return prematurely, before the cheaper path has been expanded.

4. Grid Heuristics Must Match the Actions

When movement is allowed in four directions, each step has unit cost, and there are no teleportations, the Manhattan distance:

$$ h = |x - x_g| + |y - y_g| $$

provides a natural lower bound. When diagonal moves are allowed at unit cost, Manhattan overestimates the true cost; in such cases, Chebyshev distance may be considered. When diagonal movement costs $\sqrt{2}$, the octile distance is appropriate.

Obstacles typically make the actual path longer, but they do not violate these lower bounds. However, teleportation, varying terrain costs, or negative costs can alter the validity of these assumptions. A heuristic is not automatically valid simply because its name includes "distance."

5. Constructing Heuristics from Relaxed Problems

Remove some constraints from the original problem to obtain a relaxed version that is easier to solve; the optimal cost of this relaxed problem typically serves as a lower bound for the original problem.

Examples:

• Ignore walls, resulting in grid geometric distance;
• In the sliding puzzle, allow tiles to pass through one another, yielding the number of misplaced tiles or the Manhattan sum;
• In route planning, ignore traffic congestion and use theoretical minimum travel time.

Pattern databases can also be precomputed. However, the heuristic computation itself incurs cost: running an expensive optimizer at each node may be slower than simply expanding more nodes.

6. Comparing Heuristic Dominance

If two heuristics are both admissible and satisfy $h_2(n) \geq h_1(n)$ for all nodes $n$, then $h_2$ is stronger (dominates) $h_1$. It typically expands no more nodes than $h_1$, but may incur higher computational cost.

Evaluation should report:

• Final path cost;
• Number of nodes expanded, generated, or reopened;
• Peak frontier size;
• Heuristic computation time;
• Total runtime and memory usage.

Comparing only path-finding speed may incorrectly classify a heuristic that returns suboptimal solutions as "better."

7. Inadmissible Heuristics and Weighted A*

Weighted A* uses:

$$ f(n) = g(n) + w \cdot h(n),\qquad w > 1. $$

It leans more toward the goal, often reducing search space, but typically sacrifices strict optimality. Under specific conditions, it can provide bounded-suboptimal guarantees, however, such guarantees must be explicitly tied to the algorithm version and assumptions; one cannot simply state "inadmissible heuristics are faster" in general.

In real-time systems, anytime algorithms can be employed: a feasible solution is returned immediately, and the solution bound is progressively tightened over time. The choice depends on the allowable suboptimality ratio, response time constraints, and the cost of failure.

8. Tie-breaking Affects Actual Cost

Many nodes may have the same f. Breaking ties by choosing the larger g, the smaller h, or insertion order does not alter the optimal cost under satisfying constraints, but it significantly changes the number of expansions and the resulting search paths. It is essential to ensure that the heap maintains a stable tie counter even when state objects are not comparable.

Common Misconceptions

• A* will prune all suboptimal directions: It primarily adjusts the priority of expansions, not eliminates them outright.
• Manhattan or straight-line heuristics are always acceptable: This depends entirely on the action and cost model.
• You can return to the goal as soon as it's first encountered: At generation time, it's not guaranteed that the g value is minimal.
• Having a visited set makes the algorithm more efficient: Permanent closure can cause inconsistent heuristics to miss better paths.

Exercise

1. Determine whether Manhattan distance is admissible for four-directional, eight-directional, and teleportation grids.
2. Construct an admissible but inconsistent heuristic and observe the effect on node re-expansion.
3. Compare the number of nodes expanded and heuristic computation time for $h=0$, Manhattan distance, and stronger lower bounds.
4. Run Weighted A* with different weights $w$, and plot curves of execution time versus suboptimality ratio.

Summary

The guarantees of A* stem from its lower-bound property and correct graph-search implementation, not from the heuristic appearing "closer to the goal." The heuristic must align with state, action, and cost representations, and must evaluate paths using both total cost and expansion cost.

The next lesson replaces the search space with a decision tree of opponents' responses: when the environment reacts to your actions, the goal becomes a dynamic path rather than a fixed one.