# If the heuristic $h(n)$ is the estimated cost from node $n$ to the goal, then why would we want a heuristic that has a greater cost?

I am currently studying the concept of heuristics in search algorithms. I recently asked this question about the so-called "pathmax modification," $$f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$$, and how it is useful. The user Pål GD commented with the following:

The heuristic will be monotone, and furthermore the higher value (as long as it's admissible) the better. Meaning that if the heuristic value $$(f + g)$$ actually drops from one node to the next, we can just keep the higher value.

Furthermore, I am told the following:

We say that $$h_2$$ dominates $$h_1$$ iff they are both admissible, and $$h_2(n) \ge h_1(n)$$, for all nodes $$n$$.

• i.e., $$h^*(n) \ge h_2(n) \ge h_1(n)$$

If $$h_2$$ dominates $$h_1$$, then $$A^*$$ with $$h_2$$ will usually visit fewer nodes than $$A^*$$ with $$h_1$$.

The "proof" is obvious:

• $$A^*$$ visits all nodes $$n$$ with $$f(n) < f^*$$.
• i.e., it visits all nodes with $$h(n) < f^* - g(n)$$.
• $$f^*$$ and $$g(n)$$ are fixed. So if $$h(n)$$ is bigger, $$n$$ is less likely to be below-the-line.

$$g(n) =$$ actual cost from start to $$n$$.
$$h(n) =$$ estimated cost from $$n$$ to goal.
$$f(n) =$$ estimated total cost from start to goal via n.
$$f^*$$ is the actual cost of the optimal solution.

After studying this, and especially the proof, and then reading Pål GD's comment, it is clear to me that I am not understanding the concept of heuristics.

Clearly, the concept of a dominant heuristic says that the greater heuristic is "superior." And then, in the proof, it says that, since $$f^*$$ and $$g(n)$$ are fixed, for $$h(n) < f^* - g(n)$$, if $$h(n)$$ is bigger, then $$n$$ is less likely to be "below-the-line." But none of this makes sense to me. If the heuristic $$h(n)$$ is the estimated cost from node $$n$$ to the goal, then why would we want a heuristic that has a greater cost? For search problems, aren't we looking for the lowest cost path to the goal? And why would the heuristic that has the greater cost be more likely to visit fewer nodes? Doesn't the fact that it has a greater cost mean that it has taken a more unfavourable path to the goal, thereby leading to greater cost? It seems to me that this misunderstanding is at the core of why I wasn't understanding the usefulness of the "pathmax modification."

For example, suppose that your landscape is a grid (like Manhattan) with some potential road-blocks. Then you can let the heuristic for node $$n$$ to the target $$t$$ be the $$\ell_2$$ distance, i.e. $$h_2(n) = \sqrt{ (n_x - t_x)^2 + (n_y - t_y)^2},$$ but a better heuristic would be the $$\ell_1$$ distance (the Manhattan distance), i.e. $$h_1(n) = (n_x - t_x) + (n_y - t_y)$$.
Notice that $$h_1$$ is always at least as high as $$h_2$$, both are under-estimating, which means that $$h_1$$ is a more accurate cost.
• Thanks for the answer. Isn't the $L_1$ distance the Manhattan distance? en.wikipedia.org/wiki/Taxicab_geometry Commented Oct 27, 2022 at 13:18
• Let $h(n)$ be the true cost of getting from $n$ to the goal $t$. In other words, let $h$ be the heuristic that is as high as possible. Which nodes will be expanded? Commented Oct 27, 2022 at 18:32
• Hmm, that's a good question. I want to say something like "the shortest / lowest cost path of nodes to the goal," but, given that we just established that our goal is not to minimise the value of the heuristic, but to have it as close to the actual cost as possible, I guess I'd now say something like "those nodes that are as close as possible (that is, have minimal deviation from) the optimal path." So, basically, if the true cost is $h^*(n) = 500$, then the path of nodes that results in the smallest deviation from $h^*(n) = 500$ is what will be expanded. [...] Commented Oct 27, 2022 at 19:01