Proof of A* algorithm's optimality when heuristics always underestimates

Question

I understand why A* algorithm always gives the most optimal path to a goal state when the heuristic always underestimates, but I can't create a formal proof for it.

As far as I understand, for each path considered as it goes deeper and deeper the accuracy of f(n) increases until the goal state, where it is 100% accurate. Also, no incorrect paths are ignored, as estimation is less than the actual cost; thus leading to the optimal path. But how should I create a proof for it?

Solution 1

The main idea of the proof is that when A* finds a path, it has a found a path that has an estimate lower than the estimate of any other possible paths. Since the estimates are optimistic, the other paths can be safely ignored.

Also, A* is only optimal if two conditions are met:

1. The heuristic is admissible, as it will never overestimate the cost.

2. The heuristic is monotonic, that is, if h(n_i) < h(n_{i + 1}), then real-cost(n_i) < real-cost(n_{i + 1}).

---

You can prove the optimality to be correct by assuming the opposite, and expanding the implications.

Assume that the path give by A* is not optimal with an admissible and monotonic heuristic, and think about what that means in terms of implications (you'll soon find yourself reaching a contradiction), and thus, your original assumption is reduced to absurd.

From that you can conclude that your original assumption was false, that is, A* is optimal with the above conditions. Q.E.D.

Solution 2

Consider that last step, the one that completes the optimal path.

Why must A* choose that path? Or, put another way, why must A* avoid choosing a sub-optimal path that reaches the goal?

Hint: this is the reason the heuristic needs to be admissible. Note that it is ok to choose a sub-optimal path, so long as it doesn't complete the path (why?).

That should give you some idea of how to fashion a proof.

Comments

[user972616]

I think when it's monotonic you can run the algorithm more efficiently but it's not a necessity. Can you tell me the source you got their information from?

[pcalcao]

It's a necessity if you're applying A* to a Closed Set. From wikipedia (there are other sources): "If the heuristic function is admissible, meaning that it never overestimates the actual minimal cost of reaching the goal, then A* is itself admissible (or optimal) if we do not use a closed set. If a closed set is used, then must also be monotonic (or consistent) for A* to be optimal."

[Carlos Linares López]

Sorry pcalcao, but according to your definition, a heuristic is monotonic if $h(n_1) < h(n_2)$ implies $h^*(n_1) < h^*(n_2)$ where $h(n)$ and $h^*(n)$ are the heuristic estimate and true optimal cost. Where do this definition come from? Usually, monotonicity is defined saying that $h(n) \leq c(n,n') + h(n')$ for all $n'$ which is a descendant of any node $n$ in the state space. And I do not see a necessary implication from this definition to yours. All that can be done is to generalize this definition to consistency and then, to admissibility, but not to your property as far as I can say.

[Noble Mushtak]

Monotonic/consistent heuristic does not mean h(a) < h(b) implies realCost(a) < realCost(b), and there are in fact consistent heuristics which violate this property. As Carlos said, it means h(a) <= c(a, b) + h(b). The reason this condition is called "monotonic" because this property holds if and only if for any path v0 -> v1 -> ... -> vn, the cost function f(vi)=g(vi)+h(vi) (where g(vi) is the distance from the source vertex v0 to vi along the path v0 -> v1 -> ... -> vi) is monotonic along the path, i.e. for any 0 <= i <= j <= n, f(vi) <= f(vj).

[Noble Mushtak]

Here is my source on the "if and only if" statement in my comment (scroll down to where it says "theorem 1.1" and "equivalence of consistent and monotone heuristics"): sciencedirect.com/topics/computer-science/consistent-heurist‌​ic