16
$\begingroup$

When using A* (or any other best path finding algorithm), we say that the heuristic used should be admissible, that is, it should never overestimate the actual solution path's length (or moves).

How does an admissible heuristic ensure an optimal solution? I am preferably looking for an intuitive explanation.

If you want you can explain using the Manhattan distance heuristic of the 8-puzzle.

$\endgroup$
  • 2
    $\begingroup$ @Ashwin Intuitively because when the algorithm finds a path of length $k$, it has already tried every other path which can possibly be of length at most $k$. That's why your heuristic function must never overestimate the cost to the goal. Try it yourself by making a heuristic function that might overestimate. $\endgroup$ – Pål GD Oct 14 '13 at 11:24
7
$\begingroup$

While Anton's answer is absolutely perfect let me try to provide an alternative answer: being admissible means that the heuristic does not overestimate the effort to reach the goal, i.e., $h(n) \leq h^*(n)$ for all $n$ in the state space (in the 8-puzzle, this means just for any permutation of the tiles and the goal you are currently considering) where $h^*(n)$ is the optimal cost to reach the target.

I think the most logical answer to see why $A^*$ provides optimal solutions if $h(n)$ is admissible is becauase it sorts all nodes in OPEN in ascending order of $f(n)=g(n)+h(n)$ and, also, because it does not stop when generating the goal but when expanding it:

  1. Since nodes are expanded in ascending order of $f(n)$ you know that no other node is more promising than the current one. Remember: $h(n)$ is admissible so that having the lowest $f(n)$ means that it has an opportunity to reach the goal through a cheaper path that the other nodes in OPEN have not. And this is true unless you can prove the opposite, i.e., by expanding the current node.
  2. Since $A^*$ stops only when it proceeds to expand the goal node (as oppossed to stop when generating it) you are sure (from the first point above) that no other node leads through a cheaper path to it.

And this is, essentially, all you will find in the original proof by Nilsson et al.

Hope this helps,

$\endgroup$
  • 3
    $\begingroup$ Thanks. It helped. You were referring to some proof by Nilsson et al. Who is that? And where can I find the proof? $\endgroup$ – Ashwin Nov 9 '13 at 11:19
  • 1
    $\begingroup$ @Ashwin See the book "Principles of Artificial Intelligence" (around page 80) by Nils J. Nilsson (1982). $\endgroup$ – nbro Feb 24 at 10:59
11
$\begingroup$

If the heuristic function is not admissible, than we can have an estimation that is bigger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that we are searching for), the algorithm will not explore it and it may find another (not least cost) path to the goal.

Look at this simple example.

enter image description here

Let $A$ and $G$ be respectively the starting and goal nodes. Let $h(N)$ be an estimate of the path's length from node $N$ to $G$, $\forall N$ in the graph. Moreover, let $c(N, X_{i})$ be the step cost function from node $N$ to its neighbour $X_i$, $\forall N$ and $i=1..m$, where $m$ is the number of neighbours of $N$ (i.e., a function that returns the cost of the edge between node $N$ and one of its neighbours).

Let the heuristics be

  • $h(B) = 3$

  • $h(C) = 4$

This heuristics function $H$ is not admissible, because $$h(C) = 4 > c(C, G) = 2$$

If the $A^*$ algorithm starts initially from node $A$, it will select next node $B$ for expansion and, after this, it will reach node $G$ from there. And the path will be $A \rightarrow B \rightarrow G$ with cost $4$, instead of $A \rightarrow C \rightarrow G$ with cost $3$. If the heuristic function was admissible this would not have happened.

$\endgroup$
  • $\begingroup$ Ok. But how does an admissible heuristic ensure an optimal solution? $\endgroup$ – Ashwin Oct 14 '13 at 11:21
  • $\begingroup$ It can happen that - h(b)<h(c) with both h(b)and h(c) being admissible, but actual_cost(b)>actual_cost(c) right? So b will be chosen as the next path where as in reality c would have given the best path. $\endgroup$ – Ashwin Oct 14 '13 at 11:25
  • $\begingroup$ For the 1st comment:admissible heuristics ensures to find the shortest path.The solution itself is optimal if the heuristic is consistent. $\endgroup$ – Anton Oct 14 '13 at 12:05
  • $\begingroup$ For the 2nd comment: if the heuristic is admissible A->B can be chosen for the next node to expand, but after that the A* will chose A->C and not A->B->G. And at the end it will end up with A->C->G. $\endgroup$ – Anton Oct 14 '13 at 12:08
  • 1
    $\begingroup$ Because A* works like this. It expands the node with least sum of distance to that node + heuristic estimation from that node. d(A,G) + h(G) = 4 + 0 = 4 and d(A,C) + h(C) = 1 + something<=2 (because it is admissible). So C hase lower sum and the A* will chose it. The same way it will than expand G and find the least path. $\endgroup$ – Anton Oct 14 '13 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.