Lecture 05: Heuristic Functions and Optimality

In the previous lecture, we established that Informed Search algorithms use a heuristic function $h(n)$ to estimate the cheapest path from node $n$ to a goal node.

But what makes a good heuristic? How do we mathematically guarantee that our heuristic will lead A* to the optimal solution?

Conditions for Optimality

For A* to be perfectly optimal, the heuristic function $h(n)$ must satisfy specific conditions depending on the underlying search algorithm (Tree-Search vs. Graph-Search).

1. Admissibility (Optimistic Heuristics)

An admissible heuristic is one that never overestimates the true cost to reach the goal. If $h^*(n)$ is the true, exact cost to reach the goal from $n$, then: $h(n) \le h^*(n)$

Because the heuristic is always optimistic, it thinks the goal is closer than it actually is.

• Result: If $h(n)$ is admissible, A* using Tree-Search is guaranteed to be optimal.
• Example: Straight-line distance is admissible because a straight line is mathematically the shortest distance between two points; therefore, the straight-line distance can never be greater than the actual road distance.

2. Consistency (Monotonicity)

A heuristic is consistent (or monotonic) if it satisfies the triangle inequality. For every node $n$ and each successor node $n'$ generated by any action $a$: $h(n) \le c(n, a, n') + h(n')$

This means the estimated cost from node $n$ to the goal is never greater than the step cost $c$ to get to $n'$ plus the estimated cost from $n'$ to the goal.

• Result: Consistency ensures that heuristic values decrease monotonically along any path to the goal.
• If $h(n)$ is consistent, A* using Graph-Search is optimal without any extra bookkeeping. (Note: Every consistent heuristic is also admissible, but not all admissible heuristics are consistent).

---

Evaluating Heuristics: The 8-Puzzle

The 8-puzzle consists of a 3x3 grid with 8 numbered tiles and one empty space. The goal is to slide tiles into the empty space until the numbers are in numerical order. To someone who hasn't seen this before, the "actions" in this state space are the movements of the empty tile (Up, Down, Left, or Right).

Here is an example of what the initial search tree looks like when expanding from a start state:

• Average solution length: 22 moves (the shortest path for the specific start state above is 26 actions).
• Branching factor: $\approx 3$ (as shown in the diagram, the empty tile can move to 2, 3, or 4 positions depending on whether it is in a corner, an edge, or the center).
• Search complexity: A naive search up to depth 22 explores $\approx 3.1 \times 10^{10}$ states. Graph search reduces this to $181,440$ reachable distinct states.

Common Admissible Heuristics for the 8-Puzzle

We can formulate two different admissible heuristics for this problem:

1. $h_1$ (Misplaced Tiles): The number of tiles that are not in their goal position. For the start state above, $h_1 = 8$. (Admissible because every misplaced tile must move at least once).
2. $h_2$ (Manhattan Distance): The sum of the horizontal and vertical distances of all tiles from their goal positions. For the start state above, $h_2 = 3+1+2+2+2+3+3+2 = 18$. (Admissible because each tile must move at least its Manhattan distance, assuming no other tiles are in the way).

---

The Effect of Heuristic Accuracy: Dominance

One way to characterize the quality of a heuristic is the Effective Branching Factor ($b^*$). If A* generates $N$ nodes to find a solution at depth $d$, then $b^*$ is the branching factor a uniform tree of depth $d$ would need to contain $N+1$ nodes: $N + 1 = 1 + b^* + (b^*)^2 + ... + (b^*)^d$ A well-designed heuristic will have a $b^*$ close to 1.

Dominance ($h_2 \ge h_1$)

When evaluating $h_1$ (misplaced) vs $h_2$ (Manhattan) across 1200 random puzzles:

• $A^*(h_1)$ generated thousands of nodes.
• $A^*(h_2)$ generated significantly fewer nodes (often an order of magnitude less).

If $h_2(n) \ge h_1(n)$ for all $n$ (and both are admissible), we say that $h_2$ dominates $h_1$.

• $h_2$ is more informed than $h_1$ and is strictly better for searching.
• Implication: A* using $h_2$ will never expand more nodes than A* using $h_1$. Every node that A* with $h_1$ expands will also be expanded by $A^*(h_2)$, but $h_1$ will cause additional useless nodes to be expanded that $h_2$ correctly avoids.

---

Where do Heuristics come from?

1. Generating heuristics from Relaxed Problems

If we remove restrictions from a problem, the state-space graph of this relaxed problem becomes a super-graph of the original. Because there are more valid edges (shortcuts), the optimal solution to the relaxed problem is always an admissible heuristic for the original problem.

• Original 8-puzzle rule: A tile can move to square B if B is adjacent and B is blank.
• Relaxed rule 1: A tile can move to square B if B is adjacent. (This generates the Manhattan distance $h_2$).
• Relaxed rule 2: A tile can move to any square B. (This generates the misplaced tiles $h_1$).

2. Pattern Databases

Instead of generating a heuristic for the whole board, we can store the exact solution cost of subproblems. For example, we create a database of the exact number of moves required to get just tiles 1, 2, 3, and 4 into their correct positions. Combining heuristics from multiple pattern databases (by taking their maximum value) can reduce the nodes generated in a 15-puzzle by a factor of 1000 compared to Manhattan distance alone.

3. Learning from Experience

"Experience" means having the agent solve lots of 8-puzzles. Each optimal solution provides training examples mapping a state to its exact cost to the goal. Using Machine Learning techniques (Neural Networks, Decision Trees, Reinforcement Learning), the agent can effectively learn the $h(n)$ function dynamically.