1
$\begingroup$

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."

$\endgroup$

1 Answer 1

1
$\begingroup$

Remember that the heuristic is always under-estimating the cost from a node to the target, which means that a higher cost (closer to the true value) is always a more accurate cost.

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.

$\endgroup$
8
  • $\begingroup$ Thanks for the answer. Isn't the $L_1$ distance the Manhattan distance? en.wikipedia.org/wiki/Taxicab_geometry $\endgroup$ Oct 27, 2022 at 13:18
  • $\begingroup$ Indeed it is. I stand corrected. $\endgroup$
    – Pål GD
    Oct 27, 2022 at 16:38
  • $\begingroup$ Ok, so I understand what you're saying here: a heuristic is always under-estimating the cost, and so a greater heuristic more accurately estimates the cost. But there's still one point I'm not clear on: why would the heuristic that has the greater cost be more likely to visit fewer nodes? If a heuristic is always underestimating the cost, and so a greater heuristic more accurately estimates the cost, then how does it make sense that the more accurate heuristic, which has a greater cost, be more likely to visit fewer nodes? Still, it seems that greater cost means more nodes visited, no? $\endgroup$ Oct 27, 2022 at 17:35
  • $\begingroup$ 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? $\endgroup$
    – Pål GD
    Oct 27, 2022 at 18:32
  • $\begingroup$ 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. [...] $\endgroup$ Oct 27, 2022 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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