Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?

I'm reading through the RMIT course notes on state space search. Consider a state space $S$, a set of nodes in which we look for an element having a certain property. A heuristic function $h:S\to\mathbb{R}$ measures how promising a node is.

$h_2$ is said to dominate (or to be more informed than) $h_1$ if $h_2(n) \ge h_1(n)$ for every node $n$. How does this definition imply that using $h_2$ will lead to expanding fewer nodes? - not only fewer but subset of the others.

In Luger '02 I found the explanation:

This can be verified by assuming the opposite (that there is at least one state expanded by $h_2$ and not by $h_1$). But since $h_2$ is more informed than $h_1$, for all $n$, $h_2(n) \le h_1(n)$, and both are bounded above by $h^*$, our assumption is contradictory.

But I didn't quite get it.

• Please give some context and explain what you're talking about. It appears h2 and h1 are heuristic functions, and that you use them to explore some kind of search space. Is that right? – Alex ten Brink Apr 29 '12 at 19:58
• Yes @AlextenBrink please go to cs.rmit.edu.au/AI-Search/Courseware/Slides1/07ImprovedMethods/… to understand my question better. – Alexander Suraphel Apr 29 '12 at 20:08
• The question you have is quite a good one (as a hint: $h_1$ and $h_2$ both need to be admissible before you can talk about how many nodes you expand). However, I only knew what your question was after you supplied the link and Gilles edited the question. For the future: if you don't provide enough context, people won't be able to understand and therefore answer your questions. The more notions you explain, the broader your audience and the more likely it is you'll get an answer. – Alex ten Brink Apr 29 '12 at 22:32
• In your edit, what is $h^*$? And please give a link or title for Luger '02. – Gilles 'SO- stop being evil' Apr 30 '12 at 14:58
• @AlextenBrink title: Artificial Intelligence: Structures and Strategies for complex problem solving 4th ed by George F. Luger – Alexander Suraphel Apr 30 '12 at 15:43

So it seems you are intrigued about the relationship between the informedness of a heuristic function and its pruning power.

This is a well-known relationship established in the literature from the 80s (see for example Pearl, Judea. Heuristics, Addison-Wesley, 1984 who, by the way, has been awarded this year with the Alan Turing award).

As you already mentioned, $h_1$ is said to be more informed than $h_2$ if and only if $h_1(n)\geq h_2(n), \forall n$ in the state space. Now, provided that the heuristic function is also admissible (i.e., $h_1(n)\leq h^*(n)$ so that it never overestimates the effort to reach the goal, where $h^*(n)$ is the optimal cost to reach the goal state from node $n$), $h_2(n)$ is admissible as well since $h^* (n) \geq h_1 (n)$ by definition and $h_1(n)\geq h_2(n)$ by hipothesis, so that $h^* (n) \geq h_2 (n)$.

When considering that both heuristics are admissible, the following result applies to all $A^*$-like search algorithms: $f (n)<h^*(n)$ is a sufficient condition for expansion so that they expand all nodes meeting this property ---other algorithms expanding them as well include IDA$^*$ and RBFS. Since $f (n) = g(n) + h (n)$ where $g(n)$ is the (known) cost from the start state $s$ to node $n$ and $h(n)$ is your heuristic function (either $h_1$ or $h_2$) so that $f(n)$ is the estimated cost of the path $s-t$ when going through $n$, it immediately follows that there are, at least, as many nodes meeting this propertiy when $h_2$ is used instead of $h_1$.

The property mentioned above was already demonstrated in the original paper of the A$^*$ search algorithm and it is quite simple. In response to your comment, I posted a proof at the end of this message.

Hope this helps, this is my first post in this site,

Theorem: $f(n) < h^*(n)$ is a sufficient condition for expansion of node $n$ in A$^*$-like search algorithms provided that $h(n)$ is an admissible heuristic function.

Proof: I will proof this by induction on the number of steps of the A$^*$ search algorithm. Since the proof relies on the monotonicity of $f(n)$ I will first prove it.

$f(n) = g(n) + h(n)$ is a monotonically increasing function (when solving minimization problems). Recall the definitions of $g(n)$ and $h(n)$ provided above.

If $h(n)$ is a consistent heuristic function (i.e., a heuristic function is said to be consistent if it satisfies the triangular inequality $|h(n) - h(m)| \leq c(n,m)$ where $c(n,m)$ is the cost of the operator from $n$ to $m$), then the $f$-value of a node $m$ which is a descendant of node $n$ lies in the interval $[g(n)+c(n,m)+h(n)-c(n,m), g(n)+c(n,m)+h(n)+c(n,m)]=[g(n)+h(n), g(n)+h(n)+2c(n,m)]\geq g(n)+h(n) = f(n)$.

Incidentally, the wikipedia says: "If $h(n)$ is consistent then the value of $h(n)$ for each node along a path to goal node are non decreasing" but this is not strictly speaking true, this is just a result of the original definition provided above.

If $h(n)$ is an $inconsistent$ heuristic function (so that it that does not satisfy the aforementioned property) then $f(m)$ can be arbitrarily smaller than $f(n)$. However, since $h(n)$ is an admissible heuristic function, $max\{h(n)-c(n,m), h(m)\}$ is an admissible heuristic function for node $m$ and using it the same interval results.

Now, bearing in mind that $f(n)$ increases along a path to the goal and that $h(n)$ never overestimates the effort to reach the goal state, it is straightforward to prove the theorem by induction

Base case: the start node $s$ is introduced in the OPEN list and it is selected for expansion. Since $f(s)=g(s)+h(s)=h(s) \leq h^*(s)$ (by hypothesis of the admissibility of $h(\cdotp)$) the theorem has been proved for the base case.

Induction step: at each iteration of the A$^*$ search algorithm the first node $n$ in OPEN is selected for expansion. By induction, it is assumed that $f(n) \leq h^*(n)$. If $n = t$ (the target state), the search immediately terminates and $f(n)=g(n)+h(n)=g(n)$ is the optimal cost of the path $s-t$. Otherwise, the descendants of node $n: n_1, n_2, ... n_k$ are inserted into the OPEN list in increasing order of $f(\cdotp)$. I will now proof that the expansion of $n$ leaves the OPEN list in such a state that the first node $m$ has $f(m) \leq h^*(m)$, because it will be expanded in the next iteration this would proof the theorem by induction. Two cases might arise:

Case 1: one of the descendants of node $n, n_i$ has an $f$-value $f(n_i) = f(n)$ (recall that $f(n)$ is a monotonically increasing function). In this case, it would be ranked first (maybe along with other nodes in case of a tie), since it has the same $f$-value of its ancestor which was already first in the OPEN list.

Case 2: all the descendants of node $n, n_i, \forall i=1, \ldots k$ have $f(n_i) > f(n)$. In this case, these nodes would be arranged in OPEN after the second state in OPEN when $n$ was selected for expansion. Since $f(n_i)\leq h^* (n_i)$, but they are larger than the second best node in OPEN, node $m$ has to verify that $f(m) \leq h^*(m)$ and this concludes the proof.

• Well, the answer to the second question (but in reversed order, the nodes expanded by $h_1$ are a subset of those expanded with $h_2$) is trivial: If $h_1 (n)\geq h_2 (n)$ then all nodes expanded by A$^*$ when using $h_1$ are also expanded by $h_2$. There are a few, however, which are not expanded with $h_1$ since for these $h_1 (n) > h_2(n)$ and the difference is large enough to make $g+h_1(n) > h^*$ so that they are generated but never expanded, whereas $g+h_2(n) < h^*$ so that they are expanded – Carlos Linares López May 1 '12 at 20:33

Every descendant of n that is reachable from n by a—wrt h2 strictly C*-bounded path will also be expanded by A2* and possibly not by A1*. h*>=h2>=h1 A2* algorithm A* using h2 A1* algorithm A* using h1

Do you have an example for that and its a statement from judea pearl only. For the Answer to original question i think A2* will dominate A1* strictly only when h2>h1, not allowing equality between the heuristics functions.

• It seems like the second part of your answer is a new question – can you clarify? – Yuval Filmus Jun 24 '17 at 18:18
• I can't understand what you are trying to say in the first paragraph. What does "by a---wrt h2 C*-bounded path" mean? What does "h*>=h2>=h1 A2* algorithm A* using h2 A1* algorithm A* using h1" mean? I suggest using full sentences. Can you edit your answer to clarify? As for the second paragraph, if you have a new question, please post that by using the 'Ask Question' button on the upper-right -- please don't use the 'answer' box to ask new questions or follow-up questions. Thank you. – D.W. Jun 25 '17 at 4:00