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$

1 Answer 1

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$
1
  • 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
    Commented Feb 28, 2020 at 16:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .