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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
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, 2020 at 16:46