The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost).

In the benchmark they use a culling heuristic equal to the $f$-cost: $c(n) = f(n)$. And I actually can't think of a valid reason to do otherwise. Ever. Are there really cases where having a culling heuristic different from the $f$-cost is useful? Or have the authors just not thought this through?

In my understanding, pruning a node that doesn't maximize the $f$-cost can only lead to more node re-expansion than necessary. Indeed, we always expand the open node with the smallest $f$-cost and progress by expanding nodes with an $f$-cost monotonically increasing. Therefore if $f(n_1) \lt f(n_2)$ and $c(n_1) \gt c(n_2)$, we prune $n_1$. Then we will re-expand $n_1$ before considering expanding $n_2$, even if $n_2$ is more interesting according to the culling heuristic. While if we had $c(n_1) \lt c(n_2)$ we would prune $n_2$ and then we would only re-expand $n_2$ after we've exhausted all the nodes with a smaller $f$-cost. And if the goal is found in the meantime, we never re-expand $n_2$.

It seems to me that if we have some domain knowledge, we should put it in the heuristic $h(n)$ and never choose a culling heuristic other than $c(n) = f(n)$.


Your Answer

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

Browse other questions tagged or ask your own question.