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

Uniform-cost search can find the cheapest route while expanding in every direction. A lower bound on the remaining cost helps prioritize promising states. A sense of direction should save computation without quietly spending the optimality guarantee.

A* does not 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 use the same units as 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^{\ast }(n),$$

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

Consistent (or monotone): for every edge $n\to n^{\prime }$:

$$h(n)\le c(n,n^{\prime })+h(n^{\prime }).$$

Consistency resembles the triangle inequality and makes $f=g+h$ nondecreasing along a path; it does not make $h$ nondecreasing. 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. An A* implementation that supports reopening

This Python 3 fragment (partial) reuses reconstruct from the previous lesson and needs successor, goal, and heuristic functions. States must be hashable and cannot be None; costs must be finite and non-negative. The termination guarantee also requires a zero heuristic at every goal and a finite graph or suitable completeness conditions.

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

Each queue entry stores the value of g when it was enqueued. The search compares that value with best_g when 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.

Terminate when a goal is popped with the current minimum f, rather than when it is first generated. Generation can occur before a cheaper path is expanded.

A small reopening example uses S→A=3, S→B=1, B→A=1, and A→G=3, with h(S)=0, h(A)=0, h(B)=4, and h(G)=0. All estimates are admissible, but B→A violates consistency. A is expanded at g=3, then reopened through B at g=2, producing cost 5. Permanently closing A leaves the cost-6 route. See Berkeley CS 188 on A* for admissibility and reopening.

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 both heuristics are admissible and $h_2(n)\ge h_1(n)$ everywhere, $h_2$ dominates $h_1$. Under suitable conditions, including consistency, the stronger bound can reduce the nodes that must be expanded. Ties at the optimal cost and reopening under inconsistent heuristics affect actual expansion counts, so dominance alone does not establish a runtime improvement.

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),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.