Lecture 05: Heuristic Functions and Optimality

In informed search strategies, the search space is navigated using problem-specific knowledge to select nodes for expansion. Rather than searching blindly, an algorithm uses an evaluation function $f(n)$ to estimate the cost of reaching the goal through node $n$, expanding the node with the lowest evaluation first.

In algorithms like Greedy Best-First Search and $A^*$ Search, the evaluation function depends directly on a heuristic function $h(n)$:

• $h(n)$: The estimated cost of the cheapest path from state $n$ to a goal state.
• Domain-Specific Knowledge: $h(n)$ is calculated purely from the description of state $n$ using domain-specific rules (e.g., straight-line distance in map routing, or tile distances in puzzle solving).

---

Conditions for Optimality

For $A^*$ search to guarantee finding the optimal (lowest-cost) solution, its heuristic function $h(n)$ must satisfy specific mathematical properties depending on whether search is performed on a Tree or a Graph.

1. Admissibility (Optimistic Heuristics)

An admissible heuristic is one that never overestimates the true cost to reach the goal.

If $h^*(n)$ represents the actual, true cost of the optimal path from node $n$ to the goal state: $h(n) \le h^*(n) \quad \forall n$

Because $h(n)$ is optimistic, it assumes the goal is closer or cheaper to reach than it actually is.

• Optimality Guarantee: If $h(n)$ is admissible, $A^*$ using TREE-SEARCH is guaranteed to return an optimal solution.
• Example: Straight-line distance (Euclidean distance) between two cities on a map is admissible because the shortest path between any two spatial coordinates is a straight line. Physical roads can only bend or curve, making the actual road distance $h^*(n)$ greater than or equal to the straight-line distance $h(n)$.

2. Consistency (Monotonicity)

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

This condition dictates that the estimated cost from $n$ to the goal cannot exceed the step cost $c(n, a, n')$ of moving from $n$ to $n'$ plus the estimated cost from $n'$ to the goal.

• Monotonic Decreasing: Consistency ensures that the estimated total path cost $f(n) = g(n) + h(n)$ is non-decreasing along any path.
• Optimality Guarantee: If $h(n)$ is consistent, $A^*$ using GRAPH-SEARCH is optimal without needing complex node re-opening logic.
• Relationship to Admissibility: Every consistent heuristic is admissible, but not every admissible heuristic is consistent. If a heuristic is admissible but not consistent, extra bookkeeping (such as Path-Max equation or re-expanding nodes in closed lists) is necessary to ensure optimality in graph search.

---

Evaluating Heuristics: The 8-Puzzle

The 8-puzzle consists of a 3x3 board with 8 numbered tiles and one blank space. The goal is to reach a target arrangement by sliding adjacent tiles into the blank space.

State-Space Complexity & Parity Constraints

• Average Solution Depth: A typical 8-puzzle instance requires about 22 moves (the shortest solution for the start state above is 26 actions).
• Branching Factor: The blank tile can move in 2, 3, or 4 directions depending on whether it sits in a corner, edge, or center position, giving an average branching factor $b \approx 3$.
• Tree Search Complexity: A naive tree search to depth 22 explores approximately $3^{22} \approx 3.1 \times 10^{10}$ states.
• Graph Search Complexity: The 8-puzzle board has $9! = 362,880$ total tile permutations. However, exactly half of these configurations are unreachable due to parity constraints (inversion counts remaining invariant under valid moves). Thus, graph search reduces the state space to: $\frac{9!}{2} = 181,440 \text{ reachable distinct states}$

Common Admissible Heuristics

1. $h_1$ (Misplaced Tiles): The number of tiles that are not in their target goal position.
   • Admissibility: Every misplaced tile must move at least once to reach its destination.
   • Start State Evaluation: For the start state shown above, all 8 tiles are out of place, so $h_1(S) = 8$.
2. $h_2$ (Manhattan Distance / City Block Distance): The sum of the horizontal and vertical grid distances of each tile from its goal position.
   • Admissibility: Assuming no other tiles were blocking the path, a tile requires at least its Manhattan distance in moves.
   • Start State Evaluation: Summing individual tile distances for the start state: $h_2(S) = \underbrace{3}_{\text{tile 1}} + \underbrace{1}_{\text{tile 2}} + \underbrace{2}_{\text{tile 3}} + \underbrace{2}_{\text{tile 4}} + \underbrace{2}_{\text{tile 5}} + \underbrace{3}_{\text{tile 6}} + \underbrace{3}_{\text{tile 7}} + \underbrace{2}_{\text{tile 8}} = 18$ Notice that $h_2(S) = 18 \le 26$ (the true optimal cost $h^*(S)$).

---

Step-by-Step $A^*$ Search Execution Example

Below is the search tree generated by $A^*$ using $h_1$ (Misplaced Tiles) on an 8-puzzle instance, expanding nodes by lowest evaluation $f(n) = g(n) + h(n)$:

---

Effect of Heuristic Accuracy: Dominance & Efficiency

Effective Branching Factor ($b^*$)

One standard metric to evaluate heuristic performance is the Effective Branching Factor ($b^*$).

If $A^*$ generates $N$ total nodes while finding a solution at depth $d$, then $b^*$ is defined as the branching factor that a uniform tree of depth $d$ would need to contain $N+1$ nodes: $N + 1 = 1 + b^* + (b^*)^2 + (b^*)^3 + \dots + (b^*)^d$

• Ideal Target: A perfectly accurate heuristic has $b^* \approx 1$.
• Numerical Example: If $A^*$ generates $N = 51$ nodes to reach a solution at depth $d = 5$, we solve for $b^*$: $52 = 1 + b^* + (b^*)^2 + (b^*)^3 + (b^*)^4 + (b^*)^5 \implies b^* \approx 1.92$

Dominance ($h_2 \ge h_1$)

If two admissible heuristics $h_1$ and $h_2$ satisfy: $h_2(n) \ge h_1(n) \quad \forall n$ we say that $h_2$ dominates $h_1$.

• Search Efficiency: $h_2$ is more informed than $h_1$.
• Node Expansion Theorem: $A^*$ using $h_2$ will never expand more nodes than $A^*$ using $h_1$. Every node expanded under $h_2$ will also be expanded under $h_1$, but $h_1$ will expand additional non-promising nodes that $h_2$ successfully prunes.

Empirical Comparison: AIMA 8-Puzzle Benchmarks

The table below (adapted from AIMA Fig 3.29) shows search performance averaged over 100 random 8-puzzle instances of varying solution depth $d$, comparing Iterative Deepening Search (IDS), $A^*(h_1)$, and $A^*(h_2)$:

[!IMPORTANT] Key Takeaway: At depth $d = 12$, uninformed IDS expands 3,644,035 nodes, whereas $A^*(h_2)$ expands only 73 nodes—making $A^*(h_2)$ over 50,000 times more efficient!

• Computation Overhead Tradeoff: Although $h_2$ strictly dominates $h_1$, calculating $h_2$ requires slightly more CPU cycles per node. A dominating heuristic is preferred provided its computation time does not outweigh the savings in node expansions.

---

Generating Admissible Heuristics

Where do good heuristics come from? Designing admissible heuristics requires constructing simplified models of the problem.

1. Relaxed Problems & Super-Graphs

A relaxed problem is created by removing constraints from the original problem definition.

• Super-Graph Property: Removing restrictions adds new edges to the state-space graph, turning it into a super-graph of the original state space.
• Admissibility Theorem: The cost of an optimal solution to a relaxed problem is guaranteed to be an admissible heuristic for the original problem.

Formal Language Example (8-Puzzle)

Suppose the original 8-puzzle movement rule is formally stated as:

"A tile can move from square A to square B if square A is adjacent to square B AND square B is blank."

By removing one or both conditions, we automatically construct three distinct relaxed problems:

1. Relaxation (a): "A tile can move from square A to square B if A is adjacent to B." (Ignores whether B is blank $\implies$ yields Manhattan Distance $h_2$).
2. Relaxation (b): "A tile can move from square A to square B if B is blank." (Ignores adjacency).
3. Relaxation (c): "A tile can move from square A to square B." (Ignores both adjacency and blank status $\implies$ yields Misplaced Tiles $h_1$).

2. Pattern Databases

Rather than estimating whole-board costs, pattern databases store exact solution costs for disjoint subproblems (e.g., placing only tiles 1, 2, 3, and 4 into their goal positions).

• During search, the exact cost to solve the subproblem is retrieved from a precomputed lookup table.
• Taking the maximum across disjoint pattern databases preserves admissibility while drastically pruning search spaces (e.g., reducing 15-puzzle node expansions by a factor of 1,000+ compared to Manhattan distance alone).

3. Learning from Experience

An agent can learn $h(n)$ by solving thousands of random instances offline. Each solved instance generates pairs of (state, true_cost_to_goal). Machine Learning techniques (e.g., deep neural networks, regression trees, or reinforcement learning) are used to approximate $h(n)$ dynamically.