3
$\begingroup$

Imagine that we have a set of heuristic functions $\{h_i\}_{i=1}^N$, where each $h_i$ is both admissible and consistent (monotonic). Is $\sum_{i=1}^N h_i$ still consistent or not?

Is there any proof or counterexample to show the contradiction?

$\endgroup$
5
$\begingroup$

No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1.

s --1-- g

Assume that $h_0$ and $h_1$ are perfect heuristics. Then $h_0(s) = 1$ and $h_1(s) = 1$. In this case the heuristic is inadmissible because $h_0(s)+h_1(s) = 2 > d(s, g)$. Similarly, as an undirected graph the heuristic will be inconsistent because $|h(s)-h(g)| > d(s, g)$.

If you'd like to understand the conditions for the sum of heuristics to be consistent and admissible, I would look at the work on additive PDB heuristics.

$\endgroup$
2
  • 2
    $\begingroup$ For a more extreme version of this answer, consider taking a single admissible, consistent heuristic, and then adding up an infinite number of copies of them. For any base heuristic value $> 0$, this sum is going to end up being $\infty$, which is generally not admissible. $\endgroup$ – Dennis Soemers Feb 28 '20 at 16:46
  • $\begingroup$ @MostafaGhadimi You should accept this answer if it answers your question. $\endgroup$ – nbro Feb 7 at 3: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.