State Space Search, UCS & A* Heuristic Admissibility

Uninformed search algorithms suffer from exponential state expansion because they blindly explore all directions. Informed (heuristic) search guides exploration using domain-specific knowledge.

The A Algorithm: A selects for expansion the frontier node that minimizes the estimated total solution cost:

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

Where:

• g(n) is the exact path cost incurred from the start state s_0 to node n.

• h(n) is the heuristic estimate of the remaining path cost from node n to the nearest goal state.

• f(n) represents the estimated total cost of the cheapest solution path passing through node n.

Definition (Admissibility): A heuristic function h(n) is admissible if it never overestimates the true cost to reach the goal: 0 ≤ h(n) ≤ h^*(n) for all nodes n, and h(G) = 0 for any goal state G.

Theorem: A* Tree Search is guaranteed to return an optimal solution if h(n) is admissible.

Proof by Contradiction:

1. Let G_2 be a sub-optimal goal state generated during search, with path cost g(G_2) > C^, where C^ is the optimal path cost.

2. Since G_2 is a goal, h(G_2) = 0, so f(G_2) = g(G_2) + h(G_2) = g(G_2) > C^*.

3. Now consider an optimal goal path. At any point before finding G_2, there must exist at least one unexpanded node n on the frontier that lies on this optimal path.

4. For this node n on the optimal path:

$f(n) = g(n) + h(n) ≤ g(n) + h^(n) = C^$

(Since h(n) ≤ h^(n) by admissibility, and g(n) + h^(n) = C^* by definition of an optimal path).

5. Therefore, f(n) ≤ C^* < f(G_2).

6. Since A* always selects the node with the lowest f-value, node n will always be selected for expansion before G_2 could ever be selected for expansion.

7. This holds for every node along the optimal path, culminating in the optimal goal G^* being selected before G_2. Contradiction! Hence, sub-optimal goal G_2 can never be selected.

In Graph Search, an explored set (closed list) prevents re-visiting already expanded states. If a heuristic is admissible but inconsistent, the first path found to a state n might NOT be the cheapest. If n is discarded on subsequent encounters, A* can return a sub-optimal solution.

Definition (Consistency / Monotonicity):

A heuristic h(n) is consistent if, for every node n and every successor n' generated by action a:

$h(n) ≤ c(n, a, n') + h(n')$

This is the form of the classical Triangle Inequality: the estimated cost from n to goal cannot exceed the step cost to n' plus the estimated cost from n' to goal.

Consequences of Consistency:

1. Non-decreasing f-costs: f(n') = g(n') + h(n') = g(n) + c(n, a, n') + h(n') ≥ g(n) + h(n) = f(n).

2. First Expansion Optimality: Whenever A* selects a state for expansion in graph search, the path to that state is guaranteed to be optimal. No closed-list state ever needs to be re-opened!

3. Consistency strictly implies Admissibility (by induction along the path to goal, where h(G) = 0).